Set

Sets enable you to declare store data collections as individual items, although no duplicate elements are allowed (all elements must be unique). Unlike our previous examples of sequence containers (vector, deque and list), we can retrieve elements from a set (as we can from all sorted associative containers) rapidly - in logaritmic time - in comparisson with sequence containers, which are much slower. You use a set in your code by including <set>.

Inserting elements into a set is a little different to normal; a pair object is returned from an insertion, the first parameter being an iterator and the second being a boolean value, which determines if there were any duplicates or not. If there were, then the element is not inserted (only unique elements are allowed). Here's a simple example:

     /* set1.cc
        Compiled using g++ set1.cc Address.cc -o set1 */
     #include <set>
     #include "AddressRepository.hh"
     
     int main()
     {
       set<Address> set1;
       if (!set1.insert(addr1).second)
             cout << "Failed to insert addr1" << endl;
       if (!set1.insert(addr2).second)
             cout << "Failed to insert addr2" << endl;
       if (!set1.insert(addr3).second)
             cout << "Failed to insert addr3 " << endl;
       if (!set1.insert(addr4).second)
             cout << "Failed to insert addr4 " << endl;
     
       std::multiset<Address>::iterator pos;
       cout << "set1 now contains: " << endl;
       for (pos=set1.begin(); pos!=set1.end(); ++pos)
         {
           pos->print();
         }
       exit(0);
     }
     

     Example 3.11: set1.cc
     

The program produces the following output:

     $ ./set1
     Failed to insert addr4
     set1 now contains:
     Name: Adam, Street: 23 Big St., City: Worcs, Phone: 443098
     Name: Edith, Street: 91 Glib Terrace, City: Shrops, Phone: 858976
     Name: Jane, Street: 12 Small St., City: Worcs, Phone: 225343
     

Notice that elements are printed ascending alphabetically. This is because the default sorting criterion for a set uses < (Some Predefined Function Objects discusses how to change this ordering). Obviously, the Address object with the name Jane is not inserted. It's not because addr1 and addr4 have identical values such as street address, phone number etc.; this is incidental. Recall from Preliminaries that we defined a < operator for class Address, which tests only for names. Thus, when addr4 is about to be inserted, the insert operation finds that "Jane" already exists within the set and as a consequence addr4 is not inserted. The pair objects values can be accessed using the member variables first and second. As mentioned previously, when used with insert, first returns the iterator from the inserted element, and second returns whether the element was inserted or not.

Like list, set provides a number of searching methods that enable you to perform logarithmic-time complexity operations. This is in preference to the linear-time complexity of the searching algorithms provided by generic algorithms (see Generic Algorithms and Function Objects).

We'll only use a few searching methods with set; the others are easier used with multiset.

     /* set2.cc
        Compiled using g++ set2.cc Address.cc -o set2 */
     #include <set>
     #include "AddressRepository.hh"
     
     int main()
     {
       set<Address> set2;
       set2.insert(addr1);
       set2.insert(addr2);
       set2.insert(addr3);
       set2.insert(addr4);
       set2.insert(addr5);
     
       std::set<Address>::iterator pos;
       cout << "Found " << set2.count(addr4) << " elements with name \""
            << addr4.getName() << "\"" << endl;
       pos = set2.find(addr4);
       if (pos != set2.end())
         {
           cout << "Found: ";
           pos->print();
         }
       else
         {
           cout << "Could not find ";
           pos->print();
         }
        exit(0);
     }
     

     Example 3.12: set2.cc
     

Notice to start with that count takes an element of the set as an argument; it looks through the set and counts how many occurrences there are of that element. So set2.count(addr4) returns how many occurrences of addr4 there are in set2. Obviously in our case we'll only find one, because sets do not allow duplicates. Finding the element addr4 is easy, and can be achieved in logarithmic time using find. Although trivial for this example, it is extremely useful for much larger collections of objects to be able to make searches so quickly. find takes an element as an argument and returns an iterator to it. So in the section of code

       pos = set2.find(addr4);
       Address addr;
       if (pos != set2.end())
         {
           cout << "Found: ";
           pos->print();
         }
     

we first use an iterator to be assigned the location of the result of the find method (a failure returns end()) in the call pos = set2.find(addr4), and then if pos isn't equal to set2.end(), we print out the result of the find.

Here's the output:

     $ ./set2
     Found 1 element with name Jane
     Found: Name: Jane, Street: 12 Small St., City: Worcs, Phone: 225343