|< 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.3  Associative Containers

  • Associative containers sort their elements automatically according to a certain ordering criterion.

  • This criterion takes the form of a function that compares either the value or a special key that is defined for the value.

  • By default, the containers compare the elements or the keys with operator less than (<). However, you can supply your own comparison function to define another ordering criterion.

  • Associative containers are typically implemented as binary trees. Thus, every element (every node) has one parent and two children. All ancestors to the left have lesser values; all ancestors to the right have greater values. It can be depicted as follow:

C++ STL Associative container binary tree

  • The associative containers differ in the kind of elements they support and how they handle duplicates.  The following is discussion of the associative containers that are predefined in the STL.

  • All of the associative container classes have an optional template argument for the sorting criterion. The default sorting criterion is the operator < (les than).

  • The sorting criterion is also used as the test for equality; that is, two elements are equal if neither is less than the other.

  • You can consider a set as a special kind of map, in which the value is identical to the key. In fact, all of these associative container types are usually implemented by using the same basic implementation of a binary tree.

  • The choice of container type should be based in general on the type of searching and inserting required by the application.

  • Associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient, performing them in a time that is on average proportional to the logarithm of the number of elements in the container.

  • Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.

28.4  Sets

C++ STL Associative container set

 

28.5  <set> Header Members

 

Operators

 

Operator

Description

operator!=

Tests if the set or multiset object on the left side of the operator is not equal to the set or multiset object on the right side.

operator<

Tests if the set or multiset object on the left side of the operator is less than the set or multiset object on the right side.

operator<=

Tests if the set or multiset object on the left side of the operator is less than or equal to the set or multiset object on the right side.

operator==

Tests if the set or multiset object on the left side of the operator is equal to the set or multiset object on the right side.

operator>

Tests if the set or multiset object on the left side of the operator is greater than the set or multiset object on the right side.

operator>=

Tests if the set or multiset object on the left side of the operator is greater than or equal to the set or multiset object on the right side.

 

Table 28.5

 

set Specialized Template Functions

 

Specialized template function

Description

swap()

Exchanges the elements of two sets or multisets.

 

Table 28.6

 

set Class Templates

 

Class

Description

set

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.

multiset

Used for the storage and retrieval of data from a collection in which the values of the elements contained need not be unique and in which they serve as the key values according to which the data is automatically ordered.

 

Table 28.7

 

set Class Template Members

 

Typedefs

 

Typedef

Description

allocator_type

A type that represents the allocator class for the set object.

const_iterator

A type that provides a bidirectional iterator that can read a const element in the set.

const_pointer

A type that provides a pointer to a const element in a set.

const_reference

A type that provides a reference to a const element stored in a set for reading and performing const operations.

const_reverse_iterator

A type that provides a bidirectional iterator that can read any const element in the set.

difference_type

A signed integer type that can be used to represent the number of elements of a set in a range between elements pointed to by iterators.

iterator

A type that provides a bidirectional iterator that can read or modify any element in a set.

key_compare

A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the set.

key_type

The type describes an object stored as an element of a set in its capacity as sort key.

pointer

A type that provides a pointer to an element in a set.

reference

A type that provides a reference to an element stored in a set.

reverse_iterator

A type that provides a bidirectional iterator that can read or modify an element in a reversed set.

size_type

An unsigned integer type that can represent the number of elements in a set.

value_compare

The type that provides a function object that can compare two elements to determine their relative order in the set.

value_type

The type describes an object stored as an element of a set in its capacity as a value.

 

Table 28.8

 

set Class Template Member Functions

 

Member function

Description

begin()

Returns an iterator that addresses the first element in the set.

clear()

Erases all the elements of a set.

count()

Returns the number of elements in a set whose key matches a parameter-specified key.

empty()

Tests if a set is empty.

end()

Returns an iterator that addresses the location succeeding the last element in a set.

equal_range()

Returns a pair of iterators respectively to the first element in a set with a key that is greater than a specified key and to the first element in the set with a key that is equal to or greater than the key.

erase()

Removes an element or a range of elements in a set from specified positions or removes elements that match a specified key.

find()

Returns an iterator addressing the location of an element in a set that has a key equivalent to a specified key.

get_allocator()

Returns a copy of the allocator object used to construct the set.

insert()

Inserts an element or a range of elements into a set.

key_comp()

Retrieves a copy of the comparison object used to order keys in a set.

lower_bound()

Returns an iterator to the first element in a set with a key that is equal to or greater than a specified key.

max_size()

Returns the maximum length of the set.

rbegin()

Returns an iterator addressing the first element in a reversed set.

rend()

Returns an iterator that addresses the location succeeding the last element in a reversed set.

set()

set constructor, constructs a set that is empty or that is a copy of all or part of some other set.

size()

Returns the number of elements in the set.

swap()

Exchanges the elements of two sets.

upper_bound()

Returns an iterator to the first element in a set that with a key that is equal to or greater than a specified key.

value_comp()

Retrieves a copy of the comparison object used to order element values in a set.

 

Table 28.9

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

 

Parameters

 

Parameter

Description

Key

The element data type to be stored in the set.

Traits

The type that provides a function object that can compare two element values as sort keys to determine their relative order in the set. This argument is optional, and the binary predicate less<Key> is the default value.

Allocator

The type that represents the stored allocator object that encapsulates details about the set's allocation and de-allocation of memory. This argument is optional, and the default value is allocator<Key>.

 

Table 28.10

  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.

set Constructor

  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

 

Parameter

Description

_Al

The storage allocator class to be used for this set object, which defaults to Allocator.

_Comp

The comparison function of type const Traits used to order the elements in the set, which defaults to Compare.

_Right

The set of which the constructed set is to be a copy.

_First

The position of the first element in the range of elements to be copied.

_Last

The position of the first element beyond the range of elements to be copied.

 

Table 28.11

[begin, end)                or            [begin, end[

 

  • The range is defined so that it includes the position used as the beginning of the range but excludes the position used as the end. It can be illustrated below:

C++ STL Associative container set

  • From the illustration, begin() and end() define a half-open range that includes the first element but excludes the last. A half-open range has two advantages:

  1. You have a simple end criterion for loops that iterate over the elements, they simply continue as long as end() is not reached.

  2. It avoids special handling for empty ranges. For empty ranges, begin() is equal to 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:

[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:

 

C++ STL Associative container set count()

// 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:

 

C++ STL Associative container set equal_range()

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

// 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:

 

C++ STL Associative container set key_comp()

// 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:

 

C++ STL Associative container set lower_bound()

// 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:

 

C++ STL Associative container set upper_bound()

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

// 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:

 

C++ STL Associative container set value_comp()

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

tenouk C++ STL programming tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ container related reading:

 

  1. Source code is available in C++ STL Container source code.

  2. Check the best selling C / C++ books at Amazon.com.

  3. A complete C & 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