1.2.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.
  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. For stack and queue default use deque as container inside. Why, because for a large amount of element, vector has relocation problem, each relocation need to copy and move all the old elements. For example, 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. Of course, if you are quite sure that you stack will just contain 10 items, you can pass vector as inside container too. That is why it call "container adapter"
  12. All the container adapter support push(), pop(). and stack and priority_queue support top(). They don’t have any iterator.