Set and Map in C++ with Examples

cosc 2030

STL: set, map, and pair

Java Set: TreeSet

plus python set and map

std:set

•

sets are containers that store unique elements following a specific

order.

•

maps are normally implemented as binary search trees, specifically Red-Black

trees

•

But NOT required.  So not all implementations are trees.

•

There is also a multiset, that doesn't require unique elements.

•

otherwise everything works the same.

set usage.

•

include <set>

•

operations:

•

constructor:

•

std::set<int> myset;

•

bool empty() and clear()

•

myset.empty();

•

size_type size()

•

basically int size, but more specific more other data structures.

•

myset.size();

•

iterator insert ( value)

•

myset.insert(10);

•

iterator find(value)

•

iterator myset.find(10);

set usage (2)

•

iterators and the find

•

so if declared

•

set<string>

•

then

•

set<string>:: iterator it;

•

it = dict.insert(word);

•

find sets the iterator to end if false.

•

it = dict.find(word);

•

if (it != dict.end)  //found.

set example code.

#include <iostream>

#include <set>

using namespace std;

// set store only the keys and unique keys

int main () {

  set<int> myset;

  set<int>:: iterator it;

  for (int i=0; i<5; ++i) myset.insert(i);

  std::cout << "elements: ";

  for (it=myset.begin(); it!=myset.end(); ++it)

     cout << ' ' << *it;

  cout << endl;

  it = myset.find(2);

  cout <<" find of 2 is "<<*it<<endl;

it = myset.find(2);

  cout <<" find of 2 is "<<*it<<endl;

  it = myset.find(20);

  if (it == myset.end())

    cout <<" find of 20 is end marker\n";

  myset.erase(1);

  it = myset.find(3);

  if (it != myset.end())

    myset.erase(it);

  std::cout << "elements now: ";

  for (it=myset.begin(); it!=myset.end(); ++it)

     cout << ' ' << *it;

  cout << endl;  return 0;

output:

elements:  0 1 2 3 4

 find of 2 is 2

 find of 20 is end marker

elements now:  0 2 4

std:map

•

Maps are associative containers that store elements formed by a

combination of a key value and a mapped value, following a specific

order.

•

ie it requires a pair

•

pair<KEY, value>

•

example

•

pair<string,int>

•

like maps, normally implemented as Red-Black trees, but this is not

required.

map usage.

•

include <map>

•

operations:

•

constructor:

•

std::map<char, int> mymap;  //where char is the key, and int is the value.

•

bool empty() and clear()

•

mymap.empty();

•

size_type size()

•

basically int size, but more specific more other data structures.

•

mymap.size();

•

iterator insert ( pair value)

•

mymap.insert(pair<char,int>('d', 4));

•

iterator find(value)

•

iterator mymap.find('b');

map usage (2)

•

like the set, the iterator is actually a pair value.

•

so  map<char,int> mymap;

•

needs   map<char,int>:: iterator it;

•

But map (unlike set) has [] operators

•

so we can use array style code

•

mymap['a'] = 12;

example code

#include <iostream>

#include <map>

using namespace std;

int main ()  {

  map<char,int> mymap;

  map<char,int>:: iterator it;

  mymap['a'] = 1;

  mymap['b'] = 2;

  mymap['c'] = 3;

  mymap.insert(pair<char,int>('d', 4));

  mymap['b'] = 5;

  std::cout << "elements: \n";

  for (it=mymap.begin(); it!=mymap.end(); ++it)

     cout << it->first<<": "<<it->second<<endl;

 it = mymap.find('b');

  cout <<"find of b is "<<it->second<<endl;

  it = mymap.find('e');

  if (it == mymap.end())

    cout <<"find of e is end marker\n";

  mymap.erase('a');

  it = mymap.find('b');

  mymap.erase(it);

  std::cout << "elements now: \n";

  for (it=mymap.begin(); it!=mymap.end(); ++it)

     cout << it->first<<": "<<it->second<<endl;

  return 0;

output:

elements:

a: 1

b: 5

c: 3

d: 4

find of b is 5

find of e is end marker

elements now:

c: 3

d: 4

Java Collection

•

Previous

•

List and Queue

•

This time is the TreeSet and

TreeMap.

TreeSet

•

Contains only unique elements

•

doesn't allow for a null element.

•

maintains ascending order

•

CompareTo function is  required if use your own object.

•

access and retrieval times are pretty fast, as you would expect.

•

treeSet is not thread safe

•

use Collections.synchronizedSet( ) for thread safety.

•

Internal

•

it's a binary search tree, implemented self-balancing by requirements.

Normally implemented as a Red-Black tree.

TreeSet (2)

•

standard methods

•

add(object), addall( objects), contains(object), isEmpty(), remove (object), clear(),

size()

•

specific to TreeSet

•

first(), pollFirst()  returns the first (lowest) element in the sorted set

•

left most node.

•

last(), pollLast() returns the last (highest) element in the sorted set.

•

right most node.

•

Lower( object) return the closet least element in the sorted set or null if there is

nothing smaller

•

higher( object) returns the closet greater element in the sorted set or null if there is

nothing higher.

•

You can also returns the subset(object1, object2),  all object greater then

tailSet(object), and all object less then  headSet(object).

TreeSet code

TreeSet<String> myTree=new TreeSet<String>();

myTree.add("Jim");

myTree.add("Fred");

myTree.add("Jake");

myTree.first();  //returns Fred

myTree.last(); //returns Jim

myTree.contains("Allyson"); //returns false.

Java TreeMap

•

a TreeMap is the same idea as a TreeSet, except it a key value map

•

the key is then used for sorting.  using the Map.Entry<key, value>

•

code:

TreeMap<Integer,String> map=new TreeMap<Integer,String>();

map.put(100,"Jim");

map.put(102,"Fred");

map.pollFirstEntry(); //returns the Map.Entry<100, "Jim">

map.containsKey("100"); //returns true

map.containsValue("Allyson"); //return false

python

•

It has a set

•

also includes a data type for

sets

. A set is an unordered collection with no

duplicate elements.

•

which implemented as a hash

•

not to be confused with dictionary variable.

•

you can install a ordered-set (from PyPi)

•

but actually be a double linked list on top of a dictionary, instead of a tree.

•

https://pypi.org/project/ordered-set/

•

There does not appear to a c++ style map function in python.

numbers = {

# using add() method

numbers.add(

print

'Updated Set:'

, numbers)

output: {32, 34, 12, 21, 54}

Slide Note

Embed Share

Download

C++ provides powerful data structures like set and map, which allow you to store unique elements in a specific order and key-value pairs, respectively. Sets are implemented using Red-Black trees, while maps store elements based on a key-value combination. This article covers the usage of sets and maps with detailed examples and operations like insert, find, empty, clear, and size.

spartacu Follow

Uploaded on Dec 12, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

cosc 2030 STL: set, map, and pair Java Set: TreeSet plus python set and map

std:set sets are containers that store unique elements following a specific order. maps are normally implemented as binary search trees, specifically Red-Black trees But NOT required. So not all implementations are trees. There is also a multiset, that doesn't require unique elements. otherwise everything works the same.

set usage. include <set> operations: constructor: std::set<int> myset; bool empty() and clear() myset.empty(); size_type size() basically int size, but more specific more other data structures. myset.size(); iterator insert ( value) myset.insert(10); iterator find(value) iterator myset.find(10);

set usage (2) iterators and the find so if declared set<string> then set<string>:: iterator it; it = dict.insert(word); find sets the iterator to end if false. it = dict.find(word); if (it != dict.end) //found.

set example code. #include <iostream> #include <set> using namespace std; // set store only the keys and unique keys it = myset.find(2); cout <<" find of 2 is "<<*it<<endl; it = myset.find(20); if (it == myset.end()) cout <<" find of 20 is end marker\n"; myset.erase(1); it = myset.find(3); if (it != myset.end()) myset.erase(it); std::cout << "elements now: "; for (it=myset.begin(); it!=myset.end(); ++it) cout << ' ' << *it; cout << endl; return 0; } int main () { set<int> myset; set<int>:: iterator it; for (int i=0; i<5; ++i) myset.insert(i); std::cout << "elements: "; for (it=myset.begin(); it!=myset.end(); ++it) cout << ' ' << *it; cout << endl; it = myset.find(2); cout <<" find of 2 is "<<*it<<endl; output: elements: 0 1 2 3 4 find of 2 is 2 find of 20 is end marker elements now: 0 2 4

std:map Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. ie it requires a pair pair<KEY, value> example pair<string,int> like maps, normally implemented as Red-Black trees, but this is not required.

map usage. include <map> operations: constructor: std::map<char, int> mymap; //where char is the key, and int is the value. bool empty() and clear() mymap.empty(); size_type size() basically int size, but more specific more other data structures. mymap.size(); iterator insert ( pair value) mymap.insert(pair<char,int>('d', 4)); iterator find(value) iterator mymap.find('b');

map usage (2) like the set, the iterator is actually a pair value. so map<char,int> mymap; needs map<char,int>:: iterator it; But map (unlike set) has [] operators so we can use array style code mymap['a'] = 12;

example code it = mymap.find('b'); #include <iostream> cout <<"find of b is "<<it->second<<endl; #include <map> it = mymap.find('e'); output: elements: a: 1 b: 5 c: 3 d: 4 using namespace std; if (it == mymap.end()) int main () { cout <<"find of e is end marker\n"; map<char,int> mymap; mymap.erase('a'); map<char,int>:: iterator it; it = mymap.find('b'); mymap['a'] = 1; mymap.erase(it); mymap['b'] = 2; std::cout << "elements now: \n"; mymap['c'] = 3; find of b is 5 find of e is end marker elements now: c: 3 d: 4 for (it=mymap.begin(); it!=mymap.end(); ++it) mymap.insert(pair<char,int>('d', 4)); cout << it->first<<": "<<it->second<<endl; mymap['b'] = 5; return 0; std::cout << "elements: \n"; } for (it=mymap.begin(); it!=mymap.end(); ++it) cout << it->first<<": "<<it->second<<endl;

Java Collection Previous List and Queue This time is the TreeSet and TreeMap.

TreeSet Contains only unique elements doesn't allow for a null element. maintains ascending order CompareTo function is required if use your own object. access and retrieval times are pretty fast, as you would expect. treeSet is not thread safe use Collections.synchronizedSet( ) for thread safety. Internal it's a binary search tree, implemented self-balancing by requirements. Normally implemented as a Red-Black tree.

TreeSet (2) standard methods add(object), addall( objects), contains(object), isEmpty(), remove (object), clear(), size() specific to TreeSet first(), pollFirst() returns the first (lowest) element in the sorted set left most node. last(), pollLast() returns the last (highest) element in the sorted set. right most node. Lower( object) return the closet least element in the sorted set or null if there is nothing smaller higher( object) returns the closet greater element in the sorted set or null if there is nothing higher. You can also returns the subset(object1, object2), all object greater then tailSet(object), and all object less then headSet(object).

TreeSet code TreeSet<String> myTree=new TreeSet<String>(); myTree.add("Jim"); myTree.add("Fred"); myTree.add("Jake"); myTree.first(); //returns Fred myTree.last(); //returns Jim myTree.contains("Allyson"); //returns false.

Java TreeMap a TreeMap is the same idea as a TreeSet, except it a key value map the key is then used for sorting. using the Map.Entry<key, value> code: TreeMap<Integer,String> map=new TreeMap<Integer,String>(); map.put(100,"Jim"); map.put(102,"Fred"); map.pollFirstEntry(); //returns the Map.Entry<100, "Jim"> map.containsKey("100"); //returns true map.containsValue("Allyson"); //return false

python It has a set also includes a data type for sets. A set is an unordered collection with no duplicate elements. which implemented as a hash not to be confused with dictionary variable. numbers = {21, 34, 54, 12} # using add() method numbers.add(32) print('Updated Set:', numbers) output: {32, 34, 12, 21, 54} you can install a ordered-set (from PyPi) but actually be a double linked list on top of a dictionary, instead of a tree. https://pypi.org/project/ordered-set/ There does not appear to a c++ style map function in python.

QA &

Set and Map in C++ with Examples

Download Presentation

Presentation Transcript

Related

More Related Content