COMS W4995 C++ Deep Dive for C Programmers

Sequence Containers

Lecture outline

stl.cpp

1. Arrays in C++

   • Direct-list-initialization for C arrays

   • Array template class code walk-through

   • std::array template class

2. STL containers

   • vector
     • elements are always contiguous
     • push_back() in O(1), but may invalidate pointers and refs
   • deque
     • push_back() & push_front() in O(1), and preserve ptrs and refs
     • elements are not contiguous though
   • list
     • doubly linked list
     • push_back(), push_front(), insert() all in O(1)
     • but probably slower than vector in many situations
   • forward_list
     • minimal singly linked list
     • push_front()