1. Sequence Containers

Standard Template Library (STL)

Array

int a[2] = {6, 7};
int a[2] {6, 7};              // preferred in cpp

Now wrap C array in class template Array

template <typename T, size_t N>
struct Array {
    // typedef T value_type;
    using value_type = T;
    // T(&)[N] is a reference to array of N elements of type T
    using TA = T(&)[N];

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }

	// member function, done in compile time
    constexpr int size() const { return N; }
    TA underlying() { return a; }

    T a[N];
};

• using declaration: another way to do typedef. Define new
  • value_type means T
  • TA references to the array
• constexpr can be designated to any (member) function. Tells compiler that such call can be evaluated at compile time
• underlying() pass out the reference to the entire array
  • Avoids decaying array into a pointer, by using T(&)[N]

[!info]

int *p = a;
// pa is a pointer to an array of 5 ints and points to the array a
int (*pa)[5] = &a;
// ra is a reference to an array of 5 ints and refers to the array a
int (&ra)[5] = a;

pa is a pointer. After dereferencing pa, you will get int[5]

• pa has type int (*)[5]
• pa same value as a, but different type
• pa + 1 will point to 5 elements after

	Array<int,5> v { 100, 101, 102, 103, 104 };
	constexpr size_t n = sizeof(v.underlying()) /
							sizeof(decltype(v)::value_type);  
						 // sizeof(Array<int,5>::value_type);
	static_assert(v.size() == n);

• decltype() to get type of a variable

std::array

Same fixed size

    std::array<int,5> v { 100, 101, 102, 103, 104 };
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }

std::vector

Initialization similar to array

• Also guarantees elements are contiguous
• push_back() may invalidate pointers and refs!

    std::vector<int> v { 100, 101, 102, 103, 104 };
    v.push_back(105);
    for (size_t i = 0; i < v.size(); ++i)  { print_int(v[i]); }
  

Can use directly list-initialization. The compiler can deduce type T

	std::vector v { 100, 101, 102, 103, 104 };

std::deque

Double-ended queue

• Vector with push_front() in $O(1)$,
  • vs vector $O(n)$ (must shift everything)
  • Existing elements never move, pointer and refs are preserved on pushing front/back
    • Not preserved if insert() or delete() in the middle :(
• No contiguity guarantee
  • Chunks (still good cache locality)
  • Slower access

      deque<int> v { 100, 101, 102, 103, 104 };
      v.push_front(99);
      v.push_back(105);
    

    Implementation

    Deque maintains a chunk pointer array

• Allocate a new chunk if needed
• Allocate new chunk pointer array, same as vector

![[10-deque.svg]]

std::list

Doubly linked list

    list<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    v.push_back(105);
    while (!v.empty())  {
        print_int(v.front());
        v.pop_front();
    }

No operator[]()!!! Need to traverse yourself

• Avoid providing an inefficient version

Push and insert() all in $O(1)$

• Slower than vector in practice

std::forward_list

Minimal singly linked list

• Just push_back()

    forward_list<int> v { 100, 101, 102, 103, 104 };
    v.push_front(99);
    while (!v.empty())  {
        print_int(v.front());
        v.pop_front();
    }
  

sizeof(forward_list<int>) = 8

• Header is 8 bytes (single head pointer)
• Middle nodes will have size 12.