Lecture Notes for SE 598, Data Structures and Algorithms

19 July 2000 - STL Sets and Multisets

1. sorted associative containers - the second type of container

   1. sorted - shifts costs around a bit; also have to indicate the sort order

   2. associative - associating one thing with another; a concept more relevant for maps and multimaps

2. sets and multisets - mathematical behavior

   1. an unordered collection of objects

   2. objects are not duplicated (sets) or are duplicated (multisets, bags)

   3. an object is a member of a set or not

   4. the number of objects is the cardinality

   5. the empty set

3. sets and multisets - stl behavior

   1. sets-multisets store values in sorted order

   2. sets remove duplicate values; multisets count them

   3. grows and shrinks; don't need to be sized - like dequeues and lists

   4. writing is more restricted than reading

4. a set-multiset is a template class

   1. with template <class T, class Compare = less<T>, class Allocator = allocator>

   2. T is the type of the values stored in the set - a single type

   3. Compare determines sorting order and equality

      1. exactly one of Compare(v1, v2), Compare(v2, v1), or v2 == v1 must be true for any v1 and v2

      2. equality - if neither of Compare(v1, v2) or Compare(v2, v1), are true, than v2 == v1 must be true

      3. < is acceptable, <= is not

5. set-multiset constructors

   1. the default constructor - set<T> s(const Compare & c = Compare())

      1. declarations like set<int,less<int> > intset(greater<int>) are legal but not proper

   2. the copy constructor - set<T> set1(set2);

   3. the segment-copy constructor set<T> tset(start, end); - also the optional compare parameter

   4. multiset constructors are the same as the set constructors, except with multiset instead of set

6. growing and shrinking sets

   1. no reserve() and capacity() member functions

   2. no d.push_back(v), d.pop_back(), d.push_front(v), and d.pop_front() member functions

   3. insert() and erase()

      1. set s.insert(v) - no iterator

         1. inserts v into s if s doesn't already contain v

         2. returns pair<iterator,bool>

            1. in the utility include file - usually included by other include files

            2. template 
               struct pair {
                 T1 first;
                 T2 second;
                 pair();
                 pair(const T1 & a, const T2 & b);
                 template 
                   pair(const pair & p);
                 }
               

         3. p.second is true if v was inserted into s; false otherwise

         4. p.first is an iterator to v in s always

      2. multiset ms.insert(v)

         1. always inserts v into ms

         2. returns an iterator to the newly inserted value

      3. set and multiset insert(i, v)

         1. maintains compatibility with other inserters

         2. the iterator i is a hint as to where v might go - can be useful in speeding up lots of insertions

         3. return an iterator to v - actual insertion not indicated for sets

      4. set and multiset insert(start, end) - no iterator

         1. insert the values denoted by the iterator range start,end into the set or multiset

         2. return nothing - actual insertions not indicated

      5. set and multiset erase(i) - delete the value referenced by the iterator i; in multisets, only one value is deleted, not all of them; returns nothing

      6. set s.erase(v) - delete the value v from the set s; returns 1 if v was a member of s and 0 otherwise

      7. multiset ms.erase(v) - delete all values v from the multiset ms; returns the number of values deleted

      8. set and multiset erase(s, e) - delete the values denoted by the iterator range s,e; returns nothing

   4. size(), max_size(), and empty() member functions

   5. set and multiset count(v) member function - return the number of times the value v appears

7. set relation operators - set equality and lexicographic less-than

   1. set equality - the same number of the same elements

8. iterators

   1. all set and multiset iterators are constant; there are no writable set and multiset iterators

      1. no efficient iterator writes in a sorted data structure

   2. set and multiset iterators are bidirectional iterators

      1. no jumping around, no distance measurement no inequality relations

   3. the usual member functions

9. reading and writing values

   1. no reading via [] or at() - iterators only

   2. no writing via anything - constant iterators

   3. range member functions - set and multiset

      1. lower_bound(v) - return an iterator to the first (or leftmost) value no less than v; return end() for no such value

      2. upper_bound(v) - return an iterator to the last (or rightmost) value no more than v; return end() for no such value

      3. equal_range(v) - return the pair (lower_bound(v), upper_bound(v))

10. other member functions

    1. set and multiset find(v) - return an iterator to v or end()

    2. set and multiset count(v)

    3. don't forget the set-oriented generic algorithms

This page last modified on 1 August 2000.