STL-setmap(1) (1).pdf

CSCI 340 DATA STRUCTURES AND ALGORITHM ANALYSIS STL – SORTED ASSOCIATIVE CONTAINERS Set/multiset, map/multimap Minmei Hou, Dept. Computer Science, NIU 1 ASSOCIATIVE CONTAINERS Sorted Unsorted set...

CSCI 340 DATA STRUCTURES AND ALGORITHM ANALYSIS STL – SORTED ASSOCIATIVE CONTAINERS Set/multiset, map/multimap Minmei Hou, Dept. Computer Science, NIU 1 ASSOCIATIVE CONTAINERS Sorted Unsorted set unordered_set multset unordered_multiset map unordered_map multmap unordered_multimap Elements (or keys) Not sorted are sorted Internally organized Internally height as hash table balanced binary search tree Minmei Hou, Dept. Computer Science, NIU 2 set : elements are sorted map : each element is a according to their own key/value pair. Key is values. Each element used for sorting elements. occurs only once Each key occurs only once Sorted Associative Containers multiset : similar to set, multimap : similar to map, except that it allows except that it allows duplicates duplicates Minmei Hou, Dept. Computer Science, NIU 3  SORTED ASSOCIATIVE CONTAINERS Sorted collections – Sorted according to a certain sorting criterion By default it’s operator < You can provide your own sorting criterion – Internally implemented as a self-balancing binary search tree – red-black tree – The advantage is not for sorting, but for searching The order of insertion does not matter – The order of data depends on their values (or keys) vector v; set s; v.push_back( 5 ); s.insert( 5); v.push_back( 1 ); s.insert( 1 ); v.push_back( 2 ); s.insert( 2 ); showCont( v ); showCont( s ); Minmei Hou, Dept. Computer Science, NIU 4  A TYPE: PAIR Treat two values as a single unit #include It’s a struct type – All members are public: first, second std::pair nameOfPair; – E.g. std::pair p1; std::pair p2; … cout = key – upper_bound (key) : the position of first element whose key > key – equal_range (key) : the range of elements whose key == key The return value is a pair Minmei Hou, Dept. Computer Science, NIU 17  MAP & MULTIMAP Iterator functions – begin – end – rbeg – rend Element access – Through subscript operator with a key Minmei Hou, Dept. Computer Science, NIU 18  MAP & MULTIMAP Inserting and removing elements – insert( elem ) The return type for map is pair The second field indicates the insertion is successful or not (since an element may already exists) – insert( pos, elem) – insert( beg, end ) – erase (elem ) – erase ( pos ) Note that in sequence containers, erase returns the position after the removed element, but in associative containers, erase does not return such position because it needs to traverse to find successor. – erase ( beg, end ) – clear ( ) Minmei Hou, Dept. Computer Science, NIU 19  MAP & MULTIMAP Other operations similar to sequence containers – Constructors You can specify optional sorting criterion – Destructor – Size related operations size, empty, max_size – Assignments =, swap 20 Minmei Hou, Dept. Computer Science, NIU  MAP FOR MAP ONLY: M[K] - RETURNS A REFERENCE TO THE VALUE OF THE ELEMENT WITH KEY K - INSERTS AN ELEMENT WITH K IF IT DOES NOT YET EXIST Minmei Hou, Dept. Computer Science, NIU 21 CSCI 340 DATA STRUCTURES AND ALGORITHM ANALYSIS STL - FUNCTOR Minmei Hou, Dept. Computer Science, NIU 1  FUNCTION OBJECTS (FUNCTOR) ⚫ OBJECTS THAT BEHAVE LIKE FUNCTIONS demoFunctionPointer.cc ⚫ FUNCTOR ⚫ FUNCTION BEHAVIOR – YOU CAN CALL BY USING PARENTHESES AND PASSING ARGUMENTS ⚫ EXAMPLE: ⚫ A CLASS IMPLEMENTATION WITH OPERATOR ( ) DEFINED class PrintIntClass { public: void operator( ) (int elem) const { cout