Brief Introduction to the STL Containers - Associative Containers
(Page 3 of 4 )
1) Set:
Declaration:
Header: set<Key, Compare, Alloc>
In Code:
set<int> aSet;
Representation:
A set can be most easily comprehended as a sorted sequence of items. Items added to it are always added so that a sorted property of the set remains intact. The set is sorted in increasing order. The compare is handled by default by the >= operator when defined for the type, or you can pass a function as a second parameter at creation time.
The last parameter in the template declaration is the usual allocation-type chooser. For example, the code below will print 2 into the console for the size and 0 and 1 as members. This is because no multiple existence is allowed in a set. So, only one 1 is added from the vector.
int item = 0;
std::vector<int> aVector;
aVector.reserve(10); // Reserve memory for 10 items
aVector.resize(10,1); // Resize the vector with 10 1
aVector.push_back(item); // add another item / a resize will be called
std::set<int> aSet;
aSet.insert(aVector.begin(), aVector.end());
cout << aSet.size() << endl;
copy(aSet.begin(), aSet.end(), ostream_iterator<int>(cout, " "));
Cons/Pros:
Inserting an item into a set is a fast operation. Inserting a range is also fast (linear time if the inserted range is already sorted). Iterators aren't deemed invalid after modifying the structure of the set unless the iterator was pointing to the modified item. Searching for an item is very fast.
Related types:
multiset -> In this version, multiple presence of the same item is allowed. For example, you may have two "2" numbers within a set, despite the fact that this isn't correct mathematically.
2) Map:
Declaration:
In Header: map<Key, Data, Compare, Alloc>
In Code:
map< string, int> aMap;
Representation:
A map is similar to a set, but, as you can see on the image above, we can also assign data for the key. For the containers above, the [] operator was just returning the nth item when available. However, for the map, this gets a new functionality. Check out the code below:
string text("Avril");
aMap[text] = 9;
aMap[text] = 10;
The first call of the operator inserts the text "Avril" into the container and sets the value pointed by it to 9. The second one just resets the value to 10. You see, the [] operator searches for the key and if it manages to find one, it returns a reference to the data member that was pointed to by the key. However, if it fails to find it, it inserts it, and right after the insertion, it returns the reference to the data member.
Just as for the set, here is a sorted container with the corresponding advantages. Also, an iterator that is returned is now a pair, since it holds the key and the data for it. You can refer to the key as first and the data as -> second. Take a look at the example following:
map<string, int>::iterator it = aMap.begin();
it->first; // will return the key, in our case the text //"Avril"
it->second; // return the second item, the 10
string text_2(" Lavigne");
aMap[text_2] = 11;
it = aMap.find(text_2 + "None");
if( it == aMap.end())
cout << " The searched item not found";
Related types:
multimap -> In this version, multiple presence of the same item is allowed. For example, you may have a "green",1 pair and a "green",2 at the same time.
Next: Closing Thoughts >>
More C++ Articles
More By Gabor Bernat
