There are requirements for elements added to an STL container:

• Elements must be copyable via a public copy constructor.
• Elements must be assignable via a public assignment operator.
• Elements must be destroyable via a public destructor (which must not throw).
• All built-in types (like int and double) meet the above requirements.

There are two types of containers:

• Array-based (vector, deque, string)
  • Expensive to insert into or remove from middle (non-ends)
• Node-based (list, set, map)
  • Cheap to insert into or remove from middle (non-ends)

Another way to classify containers:

• Sequence containers (each object has a position and position depends on time object arrived in the collection)
  • Some examples are: vector, deque, list
• Associative containers (each object's position is determined by it's value, and is always sorted, because items are inserted into the correct position)
  • Some examples are set, multiset, map, multimap

Vectors

For vectors, difference between subscript and .at(int index) is that .at(int index) will throw if subscript is out of range.

If reallocation occurs, all pointers and iterators are invalidated.

vector<type> v(n) will create n elements set to the default value, but vector<type> v(n, value) will create them AND set them to value.

vector<type> v(beg, end) will also create a vector from the specified range of elements. Both beg and end in this case are InputIterators.

swap(vector & x) - Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.

reserve(vector<typename>::size_type), of course, only increases the capacity, not the size. So it is different from using vector<type> v(n).

calling resize(vector<typename>::size_type n) will resize the container so it contains n elements. It destroys the back part of the vector.

Remember to check for empty() because empty vectors may contain invalid pointers to data

Swap/Shrink-to-Fit "trick":
std::vector<int>(cont1).swap(cont1);

Deques

Deques are also array-based structures, and act much like vectors.

However, it can grow in both directions, as well as shrink in both directions (adds push_front and pop_front).

Very importantly, you have no control over when a reallocation of memory occurs.

There is no reserve or capacity function.

Insertion and deletion, like usual, invalide pointers or iterators to other elements. The exception is that when an element is added to the end or the front.

Lists

Regular lists are, by default, doubly linked-lists.

Node-based, of course.

Insertion and deletion, obviously, do not invalidate pointers or iterators to other elements.

No reserve or capacity, since they're not necessary. There is push_front and pop_front since those are cheap.

THERE IS NO SUBSCRIPT (OPERATOR[]) OPERATOR!!!!! For good reason too. You really wanna iterate through the whole damn thing every time you need a variable?

NOTE: The following additional methods can only be operated on lists of the same type.

Additional methods are:

• void sort () or void sort (Compare comp)
  • The version of sort that takes in no parameters uses the operator< to sort.
  • comp is a binary predicate which returns true if the first argument goes before the second argument in the strict weak ordering it defines, and false otherwise. In other words, first < second -> true

• void unique() or void unique (BinaryPredicate binary_pred)
  • unique, if given no argument, checks for equality using == (well, that's what makes sense, right?), but if a binary predicate is supplied it will use that to check for "uniqueness" (return true if unique). In any case, only the first element of each unique "set" will be kept in the list.

• void merge (list& x) or void merge (list& x, Compare comp) (rvalue reference version is available for both)
  • if there's no argument, it merges based on the operator<, like sort does.
  • comp, as usual, is a Binary Predicate. It returns true if the first argument is considered to go before the second in the strict weak ordering it defines, and false otherwise. So, kinda like sort, but in this case you're merging two things.

• void splice (const_iterator position, list& x) or void splice (const_iterator position, list& x, const_iterator i) or void splice (const_iterator position, list&& x,const_iterator first, const_iterator last) (rvalue reference version available for first two)
  • Transfers elements from x into the container, inserting them at position.
  • Removes the elements from x as well, altering sizes of both containers
  • No construction or destruction, they're transferred.
  • The first version (1) transfers all the elements of x into the container.
  • The second version (2) transfers only the element pointed by i from x into the container.
  • The third version (3) transfers the range [first,last) from x into the container.

----