| 28.3 Associative Containers
|
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.
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 |
Specialized template function | Description |
swap() | Exchanges the elements of two sets or multisets. |
Table 28.6 |
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 |
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 aconst 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 |
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 |
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> >
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 |
An STL set is:
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.
Reversible, because it provides a bidirectional iterator to access its elements.
Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.
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.
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.
set( );
explicit set( const Traits& _Comp );
explicit set( const Traits& _Comp, const Allocator& _Al );
set( const _set& _Right );
template<class InputIterator> set( InputIterator _First, InputIterator _Last );
template<class InputIterator> set( InputIterator _First, InputIterator _Last, const Traits& _Comp );
template<class InputIterator> set( InputIterator _First, InputIterator _Last, const Traits& _Comp, const Allocator& _Al );
Parameter | Description |
_Al | The storage allocator class to be used for this set object, which defaults toAllocator. |
_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 |
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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
Source code is available inC++ STL Container source code.
Check thebest selling C / C++ books at Amazon.com.
Acomplete C++ Standard Library documentation that includes STL.