|< C++ STL Container 5| Main| C++ STL Container 7 >| Site Index| Download|

MODULE 28

THE C++ STL CONTAINER PART 6

list, set, multiset

My Training Period: xx hours

What do we have in this session?

1. Associative Containers

2. Sets

3. <set> Header Members – operator, specialize template function & class template

4. set Class Template Members – typedef & member function

5. set Constructor

6. set, constructor program example

7. set, count() program example

8. set, equal_range() program example

9. set, key_comp() program example

10. set, lower_bound() program example

11. set, upper_bound() program example

12. set, value_comp() program example

28.4  Sets

• A set is a collection in which elements are sorted according to their own values. Each element may occur only once, thus duplicates are not allowed.  Its structure can be depicted as shown below.

28.5  <set> Header Members

Operators

set Specialized Template Functions

set Class Templates

set Class Template Members

Typedefs

set Class Template Member Functions

• The STL container class set is used for the storage and retrieval of data from a collection in which the values of the elements contained are unique and serve as the key values according to which the data is automatically ordered.

• The value of an element in a set may not be changed directly. Instead, you must delete old values and insert elements with new values.

template < class Key, class Traits = less<Key>, class Allocator = allocator<Key>  > 

Parameters

• An STL set is:

1. An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.  It is a simple associative container because its element values are its key values.

2. Reversible, because it provides a bidirectional iterator to access its elements.

3. Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

4. Unique in the sense that each of its elements must have a unique key. Since set is also a simple associative container, its elements are also unique.

• A set is also described as a template class because the functionality it provides is generic and independent of the specific type of data contained as elements. The data type to be used is, instead, specified as a parameter in the class template along with the comparison function and allocator.

• The elements of a set are unique and serve as their own sort keys. This type of structure is an ordered list of, say, words in which the words may occur only once. If multiple occurrences of the words were allowed, then a multiset would be the appropriate container structure.

• If unique definitions were attached as values to the list of key words, then a map would be an appropriate structure to contain this data. If instead the definitions were not unique, then a multimap would be the container of choice.

• The set orders the sequence it controls by calling a stored function object of type key_compare. This stored object is a comparison function that may be accessed by calling the member functionkey_comp.  In general, the elements need to be merely less than comparable to establish this order so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements.

• The iterator provided by the set class is a bidirectional iterator, but the class member functions insert() andset() have versions that take as template parameters a weaker input iterator, whose functionality requirements are more minimal than those guaranteed by the class of bidirectional iterators.

• The different iterator concepts form a family related by refinements in their functionality. Each iterator concept has its own set of requirements, and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator.

• It may be assumed that an input iterator may be dereferenced to refer to some object and that it may be incremented to the next iterator in the sequence. This is a minimal set of functionality, but it is enough to be able to talk meaningfully about a range of iterators [_First, _Last) in the context of the class's member functions.

set Constructor

• Constructs a set that is empty or that is a copy of all or part of some other set.  The following is a prototype code for set constructor set::set.  It is provided here for parameters terminologies reference and will not be repeated for other associative containers.

1. set( );

2. explicit set( const Traits& _Comp );

3. explicit set( const Traits& _Comp, const Allocator& _Al );

4. set( const _set& _Right );

5. template<class InputIterator> set( InputIterator _First, InputIterator _Last );

6. template<class InputIterator> set( InputIterator _First, InputIterator _Last, const Traits& _Comp );

7. template<class InputIterator> set( InputIterator _First, InputIterator _Last, const Traits& _Comp, const Allocator& _Al );

Parameters

• All constructors store a type of allocator object that manages memory storage for the set and that can later be returned by callingget_allocator().  The allocator parameter is often omitted in the class declarations and preprocessing macros used to substitute alternative allocators.

• All constructors initialize their sets.

• All constructors store a function object of type Traits that is used to establish an order among the keys of the set and that can later be returned by calling key_comp().

• The first three constructors specify an empty initial set, the second specifying the type of comparison function (_Comp) to be used in establishing the order of the elements and the third explicitly specifying the allocator type (_Al) to be used.

• The keyword explicit suppresses certain kinds of automatic type conversion.

• The fourth constructor specifies a copy of the set _Right.

• The last three constructors copy the range [_First, _Last) of a set with increasing explicitness in specifying the type of comparison function of class Traits and Allocator.

• You will find somewhere sometime in STL the half-open ranges format as shown below.

[begin, end)                or            [begin, end[

// set, constructor

#include <set>

#include <iostream>

using namespace std;

 

char main()

{

   set <char>::iterator st0_Iter, st1_Iter, st2_Iter, st3_Iter, st4_Iter, st5_Iter, st6_Iter;

   // create an empty set st0 of key type char

   set <char> st0;

   // create an empty set st1 with the key comparison function of less than, then insert 6 elements

   set <char, less<char> > st1;

   st1.insert('p');

   st1.insert('e');

   st1.insert('g');

   st1.insert('P');

   st1.insert('y');

   st1.insert('b');

   // create an empty set st2 with the key comparison function of greater than, then insert 2 elements

   set <char, greater<char> > st2;

   st2.insert('f');

   st2.insert('k');

   // create a set st3 with the allocator of set st1

   set <char>::allocator_type st1_Alloc;

   st1_Alloc = st1.get_allocator();

   set <char> st3(less<char>(), st1_Alloc);

   st3.insert('u');

   st3.insert('U');

   //set st4, a copy of set st1

   set <char> st4(st1);

   // create a set st5 by copying the range st1[_First, _Last)

   set <char>::const_iterator st1_PIter, st1_QIter;

   st1_PIter = st1.begin();

   st1_QIter = st1.begin();

   st1_QIter++;

   st1_QIter++;

   st1_QIter++;

   set <char> st5(st1_PIter, st1_QIter);

   // create a set st6 by copying the range st4[_First, _Last) and with the allocator of set st2

   set <char>::allocator_type st2_Alloc;

   st2_Alloc = st2.get_allocator();

   set <char> st6(st4.begin(), ++st4.begin(), less<char>(), st2_Alloc);

   // ------------------------------------------------

   cout<<"Operation: set <char> st0\n";

   cout<<"st0 data: ";

   for(st0_Iter = st0.begin(); st0_Iter != st0.end(); st0_Iter++)

      cout<<" "<<*st0_Iter;

   cout<<endl;

   cout<<"\nOperation1: set <char, less<char> > st1\n";

   cout<<"Operation2: st1.insert('p')...\n";

   cout<<"st1 data: ";

   for(st1_Iter = st1.begin(); st1_Iter != st1.end(); st1_Iter++)

      cout<<" "<<*st1_Iter;

   cout<<endl;

   cout<<"\nOperation1: set <char, greater<char> > st2\n";

   cout<<"Operation2:  st2.insert('f')...\n";

   cout<<"st2 data: "<<*st2.begin()<<" "<<*++st2.begin()<<endl;

   cout<<"\nOperation1: set <char> st3(less<char>(), st1_Alloc)\n";

   cout<<"Operation2: st3.insert('u')\n";

   cout<<"st3 data: ";

   for(st3_Iter = st3.begin(); st3_Iter != st3.end(); st3_Iter++)

      cout<<" "<<*st3_Iter;

   cout<<endl;

   cout<<"\nOperation: set <char> st4(st1)\n";

   cout<<"st4 data: ";

   for(st4_Iter = st4.begin(); st4_Iter != st4.end(); st4_Iter++)

      cout<<" "<<*st4_Iter;

   cout<<endl;

   cout<<"\nOperation: set <char> st5(st1_PIter, st1_QIter)\n";

   cout<<"st5 data: ";

   for(st5_Iter = st5.begin(); st5_Iter != st5.end(); st5_Iter++)

      cout<<" "<<*st5_Iter;

   cout<<endl;

   cout<<"\nOperation: set <char> st6(st4.begin(), \n++st4.begin(), less<char>(), st2_Alloc)\n";

   cout<<"st6 data: ";

   for(st6_Iter = st6.begin(); st6_Iter != st6.end(); st6_Iter++)

      cout<<" "<<*st6_Iter;

   cout<<endl;

   return 0;

}

 

Output:

• The return value is 1 if the set contains an element whose sort key matches the parameter key. 0 if the set does not contain an element with a matching key.

• The member function returns the number of elements in the following range:

[lower_bound (_Key), upper_bound (_Key)).

// set, count(), expect some warning during the compilation

#include <set>

#include <iostream>

using namespace std;

int main()

{

    set <int> st1;

    int i;

    st1.insert(1);

    st1.insert(2);

    st1.insert(1);

    // keys must be unique in set, duplicates are ignored

    i = st1.count(1);

    cout<<"The number of elements in st1 with a sort key of 1 is: "<<i<<endl;

    i = st1.count(2);

    cout<<"The number of elements in st1 with a sort key of 2 is: "<<i<<endl;

    i = st1.count(3);

    cout<<"The number of elements in st1 with a sort key of 3 is: "<<i<<endl;

    return 0;

}

Output:

• The return value is a pair of iterators where the first is thelower_bound of the key and the second is theupper_bound of the key.

• To access the first iterator of a pair pr returned by the member function, use pr.first, and to dereference the lower bound iterator, use *(pr.first).  To access the second iterator of a pair pr returned by the member function, use pr.second, and to dereference the upper bound iterator, use *(pr.second).

// set, equal_range(), expect some warning during compilation

#include <set>

#include <iostream>

using namespace std;

int main()

{

    typedef set<int, less<int> > IntSet;

    IntSet st1;

    set <int>::iterator st1Iter;

    set <int, less< int > > :: const_iterator st1_RcIter;

    st1.insert(10);

    st1.insert(20);

    st1.insert(30);

    st1.insert(40);

    st1.insert(50);

    cout<<"st1 data: ";

    for(st1Iter = st1.begin(); st1Iter != st1.end(); st1Iter++)

        cout<<" "<<*st1Iter;

    cout<<endl;

    pair <IntSet::const_iterator, IntSet::const_iterator> p1, p2;

    p1 = st1.equal_range(30);

    cout<<"\nThe upper bound of the element with\na key of 30 in the set st1 is: "<<*(p1.second)<<endl;

    cout<<"\nThe lower bound of the element with\na key of 30 in the set st1 is: "<<*(p1.first)<<endl;

    // compare the upper_bound called directly

    st1_RcIter = st1.upper_bound(30);

    cout<<"\nA direct call of upper_bound(30) gives "<<*st1_RcIter<<" matching\nthe 2nd element of the pair"

        <<" returned by equal_range(30)."<<endl;

    cout<<"\nOperation: p2 = st1.equal_range(60)\n";

    p2 = st1.equal_range(60);

    // if no match is found for the key, both elements of the pair return end()

    if ((p2.first == st1.end()) && (p2.second == st1.end()))

        cout<<"\nThe set st1 doesn't have an element\nwith a key less than 60."<<endl;

    else

        cout<<"The element of set st1 with a key >= 60 is: "<<*(p1.first)<<endl;

    return 0;

}

Output:

• The return value is the function object that a set uses to order its elements, which is the template parameter Traits.

• The stored object defines the member function:

bool operator()(const Key& _xVal, const Key& _yVal);

• Which returns true if _xVal precedes and is not equal to _yVal in the sort order.

• Note that both key_compare andvalue_compare are synonyms for the template parameter Traits. Both types are provided for the set and multiset classes, where they are identical, for compatibility with the map and multimap classes, where they are distinct.

// set, key_comp()

#include <set>

#include <iostream>

using namespace std;

int main()

{

    set <int, less<int> > st1;

    set<int, less<int> >::key_compare kc1 = st1.key_comp();

    bool res1 = kc1(3, 7);

    if(res1 == true)

    {

        cout<<"kc1(3,7) returns value of true, where kc1\nis the function object of st1."<<endl;

    }

    else  

    {

        cout<<"kc1(3,7) returns value of false where kc1\nis the function object of st1."<<endl;

    }

    set <int, greater<int> > st2;

    set<int, greater<int> >::key_compare kc2 = st2.key_comp();

    bool res2 = kc2(3, 7);

    if(res2 == true)  

    {

        cout<<"kc2(3,7) returns value of true, where kc2\nis the function object of st2."<<endl;

    }

    else  

    {

        cout<<"kc2(3,7) returns value of false, where kc2\nis the function object of st2."<<endl;

    }

    return 0;

}

Output:

• The return value is an iterator or const_iterator that addresses the location of an element in a set that with a key that is equal to or greater than the argument key or that addresses the location succeeding the last element in the set if no match is found for the key.

// set, lower_bound()

#include <set>

#include <iostream>

using namespace std;

int main( )

{

    set <int> st1;

    set <int> :: const_iterator st1Iter, st1_PIter, st1_QIter;

    st1.insert(11);

    st1.insert(21);

    st1.insert(30);

    st1.insert(10);

    st1.insert(22);

    cout<<"st1 data: ";

    for(st1Iter = st1.begin(); st1Iter != st1.end(); st1Iter++)

        cout<<" "<<*st1Iter;

    cout<<endl;

    st1_QIter = st1.lower_bound(21);

    cout<<"The element of set st1 with a key of 21 is: "<<*st1_QIter<<endl;

    st1_QIter = st1.lower_bound(60);

    // if no match is found for the key, end() is returned

    if(st1_QIter == st1.end())

        cout<<"The set st1 doesn't have an element with a key of 60."<<endl;

    else

        cout<<"The element of set st1 with a key of 60 is: "<<*st1_QIter<<endl;

    // the element at a specific location in the set can be found

    // by using a dereferenced iterator that addresses the location

    st1_PIter = st1.end();

    st1_PIter--;

    st1_QIter = st1.lower_bound(*st1_PIter);

    cout<<"The element of st1 with a key matching that\nof the last element is: "<<*st1_QIter<<endl;

    return 0;

}

Output:

• Return value is an iterator or const_iterator that addresses the location of an element in a set that with a key that is equal to or greater than the argument key, or that addresses the location succeeding the last element in the set if no match is found for the key.

// set, upper_bound()

#include <set>

#include <iostream>

using namespace std;

int main()

{

    set <int> st1;

    set <int> :: const_iterator st1Iter, st1PIter, st1QIter;

    st1.insert(9);

    st1.insert(12);

    st1.insert(20);

    st1.insert(13);

    st1.insert(11);

    cout<<"st1 data: ";

    for(st1Iter = st1.begin(); st1Iter != st1.end(); st1Iter++)

        cout<<" "<<*st1Iter;

    cout<<endl;

    st1QIter = st1.upper_bound(9);

    cout<<"The first element of set st1 with a key greater than 9 is: "<<*st1QIter<<endl;

    st1QIter = st1.upper_bound(22);

    // if no match is found for the key, end( ) is returned

    if(st1QIter == st1.end())

        cout<<"The set st1 doesn't have an element with a key greater than 22."<<endl;

    else

        cout<<"The element of set st1 with a key > 22 is: "<<*st1QIter<<endl;

    // the element at a specific location in the set can be found

    // by using a dereferenced iterator addressing the location

    st1PIter = st1.begin();

    st1QIter = st1.upper_bound(*st1PIter);

    cout<<"The first element of st1 with a key greater than\nthat of the initial element of st1 is: "<<*st1QIter<<endl;

    return 0;

}

Output:

• The return value is a function object that a set uses to order its elements, which is the template parameter Traits.

• The stored object defines the member function:

bool operator(const Key& _xVal, const Key& _yVal);

• Which returns true if _xVal precedes and is not equal to _yVal in the sort order.

• Note that both value_compare andkey_compare are synonyms for the template parameterTraits. Both types are provided for the set and multiset classes, where they are identical, for compatibility with the map and multimap classes, where they are distinct.

// set, value_comp()

#include <set>

#include <iostream>

using namespace std;

int main()

{

    set <int, less<int> > st1;

    set <int, less<int> >::value_compare vcom1 = st1.value_comp();

    bool result1 = vcom1(5, 9);

    if(result1 == true)  

    {

        cout<<"vcom1(5,9) returns value of true, \nwhere vcom1 is the function object of st1."<<endl;

    }

    else  

    {

        cout<<"vcom1(5,9) returns value of false, \nwhere vcom1 is the function object of st1."<<endl;

    }

    set <int, greater<int> > st2;

    set<int, greater<int> >::value_compare vcom2 = st2.value_comp();

    bool result2 = vcom2(5, 9);

    if(result2 == true)

    {

        cout<<"vcom2(5,9) returns value of true, \n0where vcom2 is the function object of st2."<<endl;

    }

    else  

    {

        cout<<"vcom2(5,9) returns value of false, \nwhere vcom2 is the function object of st2."<<endl;

    }

    return 0;

}

Output:

• For other associative containers, previously shown program examples will not be presented again, except the containers constructor, because they are similar.

• You can try on your own by using the same previous program examples, replacing the containers and keeping other codes as it is.  Re-compile and re- run.  Start using your own brain and creativity.  Be creative :o).

-------------------------------------------End of set--------------------------------------

tenouk C++ STL programming tutorial

Further C++ container related reading:

1. Source code is available inC++ STL Container source code.

2. Check thebest selling C / C++ books at Amazon.com.

3. Acomplete C Standard Library.

4. Acomplete C++ Standard Library documentation that includes STL.

|< C++ STL Container 5| Main| C++ STL Container 7 >| Site Index| Download|

C++ STL Container Classes:  Part 1 | Part 2 |Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11