1.5.1.2 Basic classifications

• STL container: sequence container, associative container and containter adapter:
  1. sequence: vector, list, string, deque
  2. associative: map , multiset , set and multimap
  3. adapter: stack, queue and priority_queue.

  

  1. If you can find same name member functions in container, prefer to use member function than generic algorithm. Such as sort, merge, remove, reverse, unique in list, and find, count, low_bound in set and map.
  2. all container support empty(), size(), max_size(), and swap(). max_size() is just theoretic value. (4 functions)
  3. First class container includes begin(), end(), rbegin(), rend(). insert() and erase(). (6 functions)
  4. sequence container support pop_back(), push_back(),front() and back() (4 functions) while associative don’t.
  5. vector support operator[], list support push_front and pop_front. and deque support both. (3 function.) By now deque support (4+6+4+3 = 17 functons)container(4)–> first container(6)–>sequence container(4)–>deque(3)
  6. vector support reserve, list has reverse(not reserve) and splice(). deque support nothing.
  7. list support it’s own version sort(), remove(), merge(),unique(). For other container, you can use the generic algorithm, Why list has its own? For sort(), list doesn’t support random access iterator. For merge(), remove() and unique(). generic algorithm just use copy method, but list has high efficient pointer implementation, So list offer its own version merge(), remove(),sort(), unique().
  8. All first class container support begin() and end(). Only sequence containers support push_front() or push_back(). begin is not equal front, begin can be used for all first class container, but front only be used for sequence container.
     1. begin() and end() return iterator, and all first container support them.
     2. front() and back() return reference, and all sequenced container support them.
     3. push_front() and push_back() add element, and vector only support push_back. deque and list support both.
  9. Associative container support It’s own find(), count(), lower_bound(), upper_bound() , equal_range(). They share the same name with generic algorithm, Don’t confuse them. When you deal with associative container, just use container member function, don’t use generic algorithm. Associative offer log-time lower_bound, upper_bound and equal_range, but generic algorithm just linear time.
  10. deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence. It doesn’t not guarantee continuity within memory, and higher constant factor cost than vector. Although both offer random access to elements and linear-time insertion and removal from middle of a sequence, the vector is faster. In my evernote, you can see a implementation of deque.
  11. difference between vector and deque:
      1. vector has relocation problem,If vector has 1000, It probably need log(1000) = 10 times relocation. that is a little costly. On the contrary, deque just allocate a new place then insert pointer of new place to pointer map. It’s relatively cheap.
      2. Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector.
      3. For stack and queue default use deque as container inside. Why, because for a large amount of element, vector has relocation problem,
  12. All the container adapter support push(), pop(). and stack and priority_queue support top(). They don’t have any iterator.
  13. If you want strongly error-safe code, such as transnational semantics for inserting and erasing, or need to minimize iterator invalidation, prefer a node-based container.
  14. Using a vector for small list is almost always superior to using list. Even though inseriton in the middle of the sequence is a linear-time operation for vector and a constant-time operation for list. Vector usually outperforms list because of its better constant factor. list’s Big-Oh advantage doesn’t kick in until data sizes get larger
  15. Store only values and smart pointers(unique_ptr or shared_ptr) in container.
      1. To contain objects even though they are not copyable or otherwise not value-like (e.g., DatabaseLocks and TcpConnections), prefer containing them indirectly via smart pointers (e.g., container< shared_ptr<DatabaseLock> > and container<shared_ptr<TcpConnection> >).
      2. Optional values. When you want a map<Thing, Widget>, but some Things have no associated Widget, prefer map<Thing, shared_ptr<Widget> >.
      3. Index containers. To have a main container hold the objects and access them using different sort orders without resorting the main container, you can set up secondary containers that "point into" the main one and sort the secondary containers in different ways using dereferenced compare predicates. But prefer a container of MainContainer::iterators (which are value-like) instead of a container of pointers.
      4. To have a container store and own objects of different but related types, such as types derived from a common Base class, prefer container< shared_ptr<Base> >. An alternative is to store proxy objects whose nonvirtual functions pass through to corresponding virtual functions of the actual object.