"Associative containers provide an ability for fast retrieval of data based on keys.", [2], 8.2. Associative containers, like sequence containers, are used to store data. But in addition to that associative containers are designed with an intention to optimize the retrieval of data by organizing the single data records in a specialized structure (e.g. in a tree) using keys for identification. The library provides four different kinds of associative containers: set, multiset, map and multimap.
set and map support unique keys, that means that those containers may contain at most one element (data record) for each key. multiset and multimap support equal keys, so more than one element can be stored for each key. The difference between set (multiset) and map (multimap) is that a set (map) stores data which inherently contains the key expression. map (multimap) stores the key expression and the appropriate data separately, i.e. the key has not to be part of the data stored.
Imagine we have objects that encapsulate the information of an employee at a company. An employee class could look like this:
class employee_data {
public:
employee_data() : name (""), skill(0), salary(0) {}
employee_data(string n, int s, long sa) :
name (n), skill (s), salary (sa) {}
string name;
int skill;
long salary;
friend ostream& operator<< (ostream& os, const employee_data& e);
};
ostream& operator<< (ostream& os, const employee_data& e) {
os << "employee: " << e.name << " " << e.skill << " " << e.salary;
return os;
}
If we want to store employee data in a set (multiset), the key has to be included in the object stored:
class employee {
public:
employee (int i, employee_data e) :
identification_code (i), description (e) {}
int identification_code; // key expression to identify an employee
employee_data description;
bool operator< (const employee& e) const {
return identification_code < e.identification_code; }
};
Now we are able to declare a set (multiset) of employees:
set <employee, less<employee> > employee_set; multiset <employee, less<employee> > employee_multiset;
Note: To use a set include set.h, to use a multiset include multiset.h
Using a set (multiset), employee is both the key type and the value type of the set (multiset).
All associative containers are parametrized on a class Key, which is used to define key_type, and a so-called comparison object of class Compare, for example:
template <class Key, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class set {
typedef Key key_type;
typedef Key value_type;
...
};
If we want to store employee data in a map (multimap), the key type is int and the value type is pair<const int, employee_data>:
map <int, employee_data, less<int> > employee_map; multimap <int, employee_data, less<int> > employee_multimap;
template <class Key, class T, class Compare = less<Key>,
template <class U> class Allocator = allocator>
class map {
typedef Key key_type;
typedef pair<const Key, T> value_type;
...
};
Note: To use a map include map.h, to use a multimap include multimap.h
Two keys k1 and k2 are considered to be equal if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false, so equality is imposed by the comparison object and not by operator==.
The member function key_comp returns the comparison object out of which the associative container has been constructed. value_comp returns an object constructed out of the comparison object to compare values of type value_type. All associative containers have the member functions begin, end, rbegin, rend, empty, size, max_size and swap defined. These member functions are equivalent to the appropriate sequence container member functions. An associative container can be constructed by specifying no argument (less<Key> is used as default comparison object) or by specifying a comparison object. It can be constructed out of a sequence of elements specified by two iterators or another associative container. operator= (assignment operator) is defined for all associative containers. Associative containers provide bidirectional iterators.
Now we want to store some employee data in the set. We can use the insert member function:
employee_data ed1 ("john", 1, 5000);
employee_data ed2 ("tom", 5, 2000);
employee_data ed3 ("mary", 2, 3000);
employee e1 (1010, ed1);
employee e2 (2020, ed2);
employee e3 (3030, ed3);
pair<set <employee, less<employee> >::iterator, bool>
result = employee_set.insert (e1);
if (result.second) cout << "insert ok"; else cout << "not inserted";
cout << endl << (*result.first).description.name << endl;
result = employee_set.insert (e1);
if (result.second) cout << "insert ok"; else cout << "not inserted";
pair<map <int, employee_data, less<int> >::iterator, bool>
result1 = employee_map.insert (make_pair (1010, ed1));
multiset <employee, less<employee> >::iterator
result2 = employee_multiset.insert (e1);
multimap <int, employee_data, less<int> >::iterator
result3 = employee_multimap.insert (make_pair (1010, ed1));
Output: insert ok
Output: john
Output: not inserted
Note: For users of Borland C++ it has to be said that the above map and multimap insert operations can only be compiled with a change in the code in map.h and multimap.h. Instead of "typedef pair<const Key, T> value_type" I used "typedef pair<Key, T> value_type".
insert takes an object of type value_type and returns a pair consisting of an iterator and a bool value. The bool value indicates whether the insertion took place. In case of an associative container supporting unique keys, the iterator points to the element with the key equal to the key of the element specified as argument, in case of an associative container supporting equal keys to the newly inserted element. insert does not affect the validity of iterators and references to the container.
A second version of insert takes a range specified by two iterators and inserts the appropriate elements into the associative container (the return value is void):
pair<int, employee_data> a[2] = { make_pair (2020, ed2),
make_pair (3030, ed3) };
employee_map.insert (&a[0], &a[2]);
The find member function takes a key value and returns an iterator, which indicates the success of the search operation:
map <int, employee_data, less<int> >::const_iterator i = employee_map.find (3030); if (i == employee_map.end() ) cout << "not found"; else cout << (*i).second.name;
Output: mary
map is the only associative container with provides the subscribe operator (oprator[]) to address elements directly:
employee_data d = employee_map[2020]; cout << d;
Output: tom 5 2000
The erase member function can take a value of type key_type, a single iterator or a range specifying the element or elements to be erased:
employee_map.erase (3030); employee_map.erase (employee_map.begin() ); employee_map.erase (employee_map.begin(), employee_map.end() ); if (employee_map.empty() ) cout << "employee_map is empty";
Output: employee_map is empty
erase invalidates only the iterators and references to the erased elements.
Since it doesn't make sense to store more than one employee under an employee key, for the demonstration of an associative container supporting equal keys a slightly different example is used. A number of employees is stored under the same key which represents a department code. We can use the employee_multimap container declared earlier in this section:
// employee_multimap is empty employee_multimap.insert (make_pair(101, ed1)); // department code 101 employee_multimap.insert (make_pair(101, ed2)); employee_multimap.insert (make_pair(102, ed3)); // department code 102
count takes a key value and returns the number of elements stored under this key value.
multimap <int, employee_data, less<int> >::size_type count = employee_multimap.count (101); cout << count;
Output: 2
lower_bound (k) with k of type key_type returns an iterator pointing to the first element with key not less than k. upper_bound (k) returns an iterator pointing to the first element with key greater than k. equal_range (k) returns a pair of iterators with the first iterator being the return value of lower_bound (k) and the second being the return value of upper_bound (k).
ostream& operator<< (ostream& os, const pair<int, employee_data>& p) {
os << "employee: " << p.second.name << " " << p.second.skill << " " <<
p.second.salary;
return os;
}
typedef multimap <int, employee_data, less<int> >::iterator j;
pair<j, j> result = employee_multimap.equal_range (101);
copy (result.first,
result.second,
ostream_iterator<pair<int, employee_data> > (cout , "\n") );
Output: john 1 5000
Output: tom 5 2000
Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996