Understanding Set and Map in C++ with Examples
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.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
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 &
