Multiset

Since the only difference between set and multiset is whether or not duplicates are allowed, we'll focus only for a moment about the implications this brings to multisets. Like set, you use a multiset by including <set>.

Because elements are ordered by their key with sorted associative containers, we need someway of dealing with duplicate elements regarding multiset. The concept of looking for duplicate elements is fairly simple; to look at the first element of a set of duplicates, we make a call to lower_bound(e), which finds the first occurrence of element e. Finding the upper bound is done by calling upper_bound(e), which points past the last occurrence of element e ¹. Both methods return an iterator to the position of element e with some multiset m. Let's take a look at some examples of using a multi set:

     /* multiset1.cc
        Compiled using g++ multiset1.cc Address.cc -o multiset1 */
     #include <set>
     #include "AddressRepository.hh"
     
     int main()
     {
       multiset<Address> mset1;
       mset1.insert(addr1);
       mset1.insert(addr2);
       mset1.insert(addr3);
       mset1.insert(addr4);
       mset1.insert(addr5);
     
       Address addr("Jane", "33 Trimpley Close", "Kidderminster", 997331);
       mset1.insert(addr);
       std::multiset<Address>::iterator pos;
       cout << "Found " << mset1.count(addr4) << " elements with name "
            << addr4.getName() << endl;
       for(pos = mset1.lower_bound(addr4);
           pos != mset1.upper_bound(addr4);
           ++pos)
         {
           cout << "Found: ";
           pos->print();
         }
       exit(0);
     }
     

     Example 3.13: multiset1.cc
     

This example isn't really different from set2.cc, except that we're now using upper_bound and lower_bound, two functions which are only useful when we're dealing with duplicate elements. Address objects addr1 and addr4 are considered duplicates because the names are the same, and we've added a new Address object to be a duplicate with addr1 and addr4 also. The net result is that we end up with a multiset with 6 Address objects, three of them duplicates with the name variable set to "Jane".

The section

       for(pos = mset1.lower_bound(addr4);
           pos != mset1.upper_bound(addr4);
           ++pos)
         {
           cout << "Found: ";
           pos->print();
         }
     

enables us to loop move through the multiset, from the first occurence of an Address object with the name "Jane", to the last occurrence of an object with the name of "Jane". Once again, the output is fairly obvious:

     Found 3 elements with name Jane
     Found: Name: Jane, Street: 12 Small St., City: Worcs, Phone: 225343
     Found: Name: Jane, Street: 55 Almond Terrace, City: Worcs, Phone: 242783
     Found: Name: Jane, Street: 33 Trimpley Close, City: Kiddy, Phone: 997331
     

Note that upper_bound returns an iterator to the position past the last element e. We could have used find in place of lower_bound in the for loop, since find returns an iterator to the first element found, if it exists within the container.