// Ordinary insertion:
Noisy n;
ns.insert(n);
cout << endl;
// Check for set membership:
cout << "ns.count(n)= " << ns.count(n) << endl;
if(ns.find(n) != ns.end())
cout << "n(" << n << ") found in ns" << endl;
// Print elements:
copy(ns.begin(), ns.end(),
ostream_iterator<Noisy>(cout, " "));
cout << endl;
cout << "\n-----------\n";
map<int, Noisy> nm;
for(int i = 0; i < 10; i++)
nm[i]; // Automatically makes pairs
cout << "\n-----------\n";
for(size_t j = 0; j < nm.size(); j++)
cout << "nm[" << j <<"] = " << nm[j] << endl;
cout << "\n-----------\n";
nm[10] = n;
cout << "\n-----------\n";
nm.insert(make_pair(47, n));
cout << "\n-----------\n";
cout << "\n nm.count(10)= "
<< nm.count(10) << endl;
cout << "nm.count(11)= "
<< nm.count(11) << endl;
map<int, Noisy>::iterator it = nm.find(6);
if(it != nm.end())
cout << "value:" << (*it).second
<< " found in nm at location 6" << endl;
for(it = nm.begin(); it != nm.end(); it++)
cout << (*it).first << ":"
<< (*it).second << ", ";
cout << "\n-----------\n";
} ///:~
The set<Noisy> object ns is created using two iterators into an array of Noisy objects, but there is also a default constructor and a copy-constructor, and you can pass in an object that provides an alternate scheme for doing comparisons. Both sets and maps have an insert( ) member function to put things in, and you can check to see if an object is already in an associative container in a couple of ways. The count( ) member function, when given a key, will tell you how many times that key occurs. (This can only be zero or one in a set or map, but it can be more than one with a multiset or multimap.) The find( ) member function will produce an iterator indicating the first occurrence (with set and map, the only occurrence) of the key that you give it or will produce the past-the-end iterator if it can’t find the key. The count( ) and find( ) member functions exist for all the associative containers, which makes sense. The associative containers also have member functions lower_bound( ), upper_bound( ), and equal_range( ), which actually only make sense for multiset and multimap, as you will see. (But don’t try to figure out how they would be useful for set and map, since they are designed for dealing with a range of duplicate keys, which those containers don’t allow.)
Designing an operator[ ] always presents a bit of a dilemma. Because it’s intended to be treated as an array-indexing operation, people don’t tend to think about performing a test before they use it. But what happens if you decide to index out of the bounds of the array? One option, of course, is to throw an exception, but with a map "indexing out of the array" could mean that you want an entry there, and that’s the way the STL map treats it. The first for loop after the creation of the map<int, Noisy> nm just "looks up" objects using the operator[ ], but this is actually creating new Noisy objects! The map creates a new key-value pair (using the default constructor for the value) if you look up a value with operator[ ] and it isn’t there. This means that if you really just want to look something up and not create a new entry, you must use the member functions count( ) (to see if it’s there) or find( ) (to get an iterator to it).
A number of problems are associated with the for loop that prints the values of the container using operator[ ]. First, it requires integral keys (which we happen to have in this case). Next and worse, if all the keys are not sequential, you’ll end up counting from zero to the size of the container, and if some spots don’t have key-value pairs, you’ll automatically create them and miss some of the higher values of the keys. Finally, if you look at the output from the for loop, you’ll see that things are very busy, and it’s quite puzzling at first why there are so many constructions and destructions for what appears to be a simple lookup. The answer only becomes clear when you look at the code in the map template for operator[ ], which will be something like this:
mapped_type& operator[] (const key_type& k) {
value_type tmp(k,T());
return (*((insert(tmp)).first)).second;
}
The map::insert( ) function takes a key-value pair and does nothing if there is already an entry in the map with the given key—otherwise it inserts an entry for the key. In either case, it returns a new key-value pair holding an iterator to the inserted pair as its first element and holding true as the second element if an insertion actually took place. The members first and second give the key and value, respectively, because map::value_type is really just a typedef for a std::pair:
typedef pair<const Key, T> value_type;
We’ve seen the std::pair template before, which just holds two values of independent types, as you can see by its definition:
template <class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair();
pair(const T1& x, const T2& y)
: first(x), second(y) {}
// Templatized copy-constructor:
template<class U, class V>
pair(const pair<U, V> &p);
};
The pair template class is very useful, especially when you want to return two objects from a function (since a return statement only takes one object). There’s even a shorthand for creating a pair called make_pair( ), which is used in AssociativeBasics.cpp.
So to retrace the steps, map::value_type is a pair of the key and the value of the map—actually, it’s a single entry for the map. But notice that pair packages its objects by value, which means that copy-constructions are necessary to get the objects into the pair. Thus, the creation of tmp in map::operator[ ] will involve at least a copy-constructor call and destructor call for each object in the pair. Here, we’re getting off easy because the key is an int. But if you want to really see what kind of activity can result from map::operator[ ], try running this: