STL

Container classes can be roughly divided into two groups:

STL-style (iterator-based)
- There is one container object which owns all the data.
- Hide container from client.
- Iterator steps through data.
- Subcontainers are specified by iterator ranges, usually a closed-open interval: [iter1,iter2)
- Requires sensible 1-D ordering of your container. All subcontainers must be intervals in that 1-D ordering. This creates obvious problems for multidimensional arrays (for example, A(2:6:2,2:6:2) is clearly not a range of some sensible 1-D ordering of the array elements)
- Iterators are based conceptually on pointers, which are the most error-prone aspect of C++. There are many ways to go wrong with iterators.
- It can be difficult for methods and functions to return containers as values. Instead, a container to receive the result can be passed as an argument.
Write containers in this way can take advantage of STL's many algorithms.
Data/ View
- The container contents ("Data") exist outside the container objects. The containers are lightweight handles ("Views") of the Data.
- Multiple containers can refer to the same data, but provide different views.
- Reference counting is used: the container contents disappear when the last handle disappears. This provides a primitive (but effective) form of garbage collection.
- It is sometimes easier to specify subcontainers (for example, subarrays of multidimensional arrays)
- Subcontainers can be first-class containers (e.g. take a subarray of an Array<N>, the result is an Array<N>, not a Subarray<N>)
- There are some subtleties associated with designing reference-counted containers. A cautious design is needed.
- It is easy to return containers from methods and pass containers by value.

vector class is recommended as alternative to the built-in array because it provides index checking and more features (it can grow dynamically too). Two very different forms of using it:

array idiom

vector<int> ivec1(6); // int ivec1[6];
vector<int> ivec2(10, -1); // extra feature, define 10 elements, initialize each to -1
// lacked feature, need extra array to initialize each element of ivec3
int ia[6] = { -2, -1, 0, 1, 2, 1024 };
vector<int> ivec3(ia+1, ia+6); // copy 5 elements of ia into ivec3
vector<int> ivec4(ivec1); // extra feature, initialized with another vector

// iterate across elements using subscript operator
for (int i=0; i<ivec1.size(); i++) // extra feature
  // use ivec1[i] as rvalue or lvalue
bool isEmpty = ivec.empty(); // extra feature
ivec1 = ivec2; // extra feature, assigned to another vector

STL idiom

vector<string> text; // extra feature, define empty vector
text.push_back(word); // insert element rather than index and assign

// iterate across elements using iterator pair
for (vector<string>::iterator it = text.begin(); it!=text.end(); it++)
  // use *it as rvalue or lvalue

Don't mix two idioms.

vector<int> ivec1;
ivec1[0] = 1024; // error, subscript operator will prompt

int ia[7] = { 0, 1, 1, 2, 3, 5, 8 };
vector<int> ivec2(7);
for (int i=0; i<ivec1.size(); i++)
  ivec2.push_back(ia[i]); // add to vector size rather than write over existing elements

Criteria for choosing sequence container type (vector, list or deque):

If require random access, vector/ deque is the clear choice over list because each access is a fixed offset from beginning.
If know the number of elements need to store, vector is preferred over list/ deque like using array.
If need to insert and delete elements other than at the two ends of the container, list is the clear choice over vector/ deque.
If need to insert or delete elements at the front of the container, deque is preferable to vector, for example, in the implementation of a queue.
If need both to randomly access and to randomly insert and delete elements, the trade-off is between the cost of the random access versus that of copying contiguous elements to the right or left. In general, predominant operation of the application (search or insertion) should determine the choice of container type. (Making this decision may require profiling the performance of both container types.) If neither performance is satisfactory, it may be necessary to design a more complex data structure of our own.
If no need either for random access or insertion except at the back, depend on the need to regrow and copy the elements of the container.
1. List holds only the storage necessary for the elements it contains. The overhead is two-fold: two additional pointers associated with each value and the indirect access of the value through a pointer.
2. Vector grow dynamically by allocating memory to hold the new sequence, copy the elements of the old sequence in turn and deallocate the old memory. Moreover, if the elements are class objects, the copy and deallocation may require the invocation of the class copy constructor and destructor on each element in turn. So, when the vector needs to grow itself, it allocates additional storage capacity beyond its immediate need — it holds this storage in reserve. (The exact amount of additional capacity allocated is implementation-defined.)
For small objects (built-in data type, simple class), vector in practice turns out to grow more efficiently than list. The larger and more complex the data type, the less efficient the vector becomes compared with list. (Complex class is class that provides both a copy constructor and a copy assignment operator.) The simple class objects and large simple class objects are inserted through bitwise copy, whereas complex class objects are inserted through copy constructor. Memory reallocation and deallocation of previous memory invoke destructor and copy constructor repeatedly.
An alternative, often preferable solution is to store large or complex class objects indirectly by pointer. The capacity increases, so the number of reallocations drops considerably. Second, the copy and deallocation of a pointer to a class object does not require the invocation of either the copy constructor or the destructor of the class.

Be careful when insert or erase elements of sequential container. They may invalidate current iterator that pointed to particular element of that container. Dereference it can cause invalid pointer read/ write errors or free memory read/ write errors resulting in bad results or crashes.

Adjusting the capacity of simple class vector with default capacity other than 1 seemed to always cause the performance to degrade. On the other hand, increasing the capacity of a large, complex class provided significant performance improvement.

Storing the objects (non built-in data type) directly is considerably less efficient: Each object (and its operands) must be copied onto the stack using copy constructor, then subsequently destroyed. Unless actually modifying the class objects within a container, storing them by pointer is significantly more efficient.

Three constraints to user-defined class types that can be element type of STL containers:

must support operator=.
must support operator< (all the relational operators are implemented using these two operators).
the element type must support a default value (for a class type, this is spoken of as a default constructor).

pair class is part of the standard library by including <utility>. It associates two values of either the same or different types within a single object. The individual elements of the pair can be accessed as first and second.

class EntrySlot;
EntrySlot* look_up(string);

typedef pair<string, EntrySlot*> SymbolEntry;
SymbolEntry current_entry("author", look_up("author"));
// ...
if (EntrySlot *it = look_up("editor"))
{
  current_entry.first = "editor";
  current_entry.second = it;
}

complex class is part of the standard library by including <complex>. It can generally be intermixed with the built-in data types.

complex<double> c1(3.14159, -2.171);
complex<double> c2(c1.real());
int i = 3;
complex<double> c3 = i;
complex<double> c4 = c1 + 3.14159;
double d = c1; // compile-time error

double re = real(c2); // nonmember syntax, like cast
double im = c2.imag();
c4 += c3; // supported
cout << c2 << endl; // "( 3.14159, -2.171 )"
cin >> c2;
// valid input
// 3.14159        ==> complex(3.14159);
// (3.14159)      ==> complex(3.14159);
// ( 3.14, -1.0 ) ==> complex(3.14, -1.0);

map<string, int> word_count;
word_count[string("Anna")] = 1;

The following steps take place:

An unnamed temporary string object initialized with "Anna" is constructed and passed to the subscript operator associated with the map class.
The word_count map is searched for the entry "Anna". The entry is not found.
A new key/ value pair is inserted into word_count. The key, of course, is a string object holding the value "Anna". The value, however, is 0 (default value of built-in data type).
The insertion done, the value is then assigned 1.

In effect, using the subscript operator to initialize a map to a collection of elements causes each value to be initialized to a default value and then assigned the explicit value. If the elements are class objects for which the default initialization and assignment are computationally significant, the performance can be affected. The preferred way

word_count.insert(map<string, int>::value_type(string("Anna"), 1));
// or
typedef pair<string, int> valType;
word_count.insert(valType(string("Anna"), 1));

If the instance is not present, the use of the subscript operator causes an instance to be inserted. To discover whether the key is present without its absence causing an instance to be inserted:

count(keyValue): return number of occurrences of keyValue within map. (For map, the return value can be only 0 or 1; can be more than 1 for multimap)
```
int count = 0;
if (word_count.count("wrinkles"))
  count = word_count["wrinkles"]; // can safely use the operator[]
```

find(keyValue): returns an iterator to the instance within the map if the instance is present or returns an iterator equal to end() if the instance is not present.

int count = 0;
map<string, int>::iterator it = word_count.find("wrinkles");
if (it != word_count.end())
  count = (*it).second; // map iterator point to pair<key, value>

Iteration strategy for multimap or multiset:

Using combination of the iterator returned by find() (it points to the first instance) and the value returned by count(). (This works because the instances are guaranteed to occur contiguously within the container)

multimap<string, string> authors;
string search_item("Alain de Botton");
multimap<string, string>::iterator iter;
iter = authors.find(search_item);
int num = authors.count(search_item);
for (int cnt=0; cnt<num; cnt++, iter++)
  do_something(*iter);

Use equal_range(). It returns a pair of iterator. If the value is present, the first iterator points to the first instance of the value and the second iterator points 1 past the last instance of the value. If the last instance is the last element, the second iterator is set equal to end().
```
typedef multimap<string, string>::iterator iterator;
pair<iterator, iterator> pos;
pos = authors.equal_range(search_item);
for ( ; pos.first != pos.second; pos.first++)
  do_something(*(pos.first));
```

One constraint on access of an element of a multimap is that the subscript operator is not supported.

Index