6.8. Storing Objects in Sorted Order
Problem
You have to store a set of objects in order, perhaps because you frequently need to access ordered ranges of these objects and you don’t want to pay for resorting them each time you do this.
Solution
Use the associative container set, declared in
<set>, which stores items in sorted order. It
uses the standard less class template, (which invokes
operator< on its arguments) by default, or you can
supply your own sorting predicate. Example
6-10 shows how to store strings in a set.
Example 6-10. Storing strings in a set
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main() {
set<string> setStr;
string s = "Bill";
setStr.insert(s);
s = "Steve";
setStr.insert(s);
s = "Randy";
setStr.insert(s);
s = "Howard";
setStr.insert(s);
for (set<string>::const_iterator p = setStr.begin();
p != setStr.end(); ++p)
cout << *p << endl;
}Since the values are stored in sorted order, the output will look like this:
Bill Howard Randy Steve
Discussion
A set is an associative container that provides
logarithmic complexity insertion and find, and constant-time deletion of elements (once
you have found the element you want to delete). sets
are unique associative containers, which means that no two elements can be equivalent,
though you can use a multiset if you need to store
multiple instances of equivalent elements. You can think of a set as a set in the mathematical sense, that is, a collection of items, with the added bonus that order ...