Chapter 11: Containers

11.1

A class with the main purpose of holding objects is commonly called a container. Proiding suitable containers for a given task and supporting them with useful fundamental operations are important steps in the construction of any program.

11.2

The most useful standard-library container is vector. The elements are stored contiguously in memory.

vector has elem, space, last, alloc. The default allocator (alloc) uses new and delete to acquire and release memory.

The standard-library vector is implemented so that growing a vector by repeated push_bach()s is efficient.

reserve() can be used to improve performance, but that can turn out to be a waste of effort: the heuristic used by vector is on average better than a developer's guess. So developers should only reserve() to avoid reallocation of elements when they want to use pointers to elements.

Copying and moving of vectors are implemented by onstructors and assignment operators as described in Section 5.2. Assigning a vector involves copying its elements, so an innocent-looking assignments and initializations can be expensive.

11.2.1

If you have a class hierarchy that relies on virtual functions to get polymorphic behavior, do not store objects directly in a container. Instead store a pointer (or a smart pointer)

11.2.2

The at() operation is a vector subscript operation that throws an exception of type out_of_range if its argument is out of the vector's range.

One way to minimize surprises from uncaught exceptions is to use a main() with a try- block as its body.

Why doesn't the standard guarantee range checking? Many performance-critical applicaitons use vectors and checking all subscripting implies a cost on the order of 10%. Obviously, that cost can vary dramatically depending on hardware, optimizers, and an application's use of subscripting. However, experience shows that such overhead can lead people to prefer the far more unsafe built-in arrays.

11.3

The standard library offers a doubly-linked list called std::list.

We use a list for sequences where we want to insert and delete elements without moving other elements.

When we use a linked list, we tend not to access elements using subscripting the way we commonly do for vectors. Instead, we might search the list looking for an element with a given value.

To do so, we use an iterator": a list iterator identifies an element of a list and can be used to iterate through a list.

The list examples can be written identically using vector and (surprisingly, unless you understand machine architecture) performs better with a small vector and with a small list. Unless you have a reason not to, use a vector. A vector performs better for traveral and for sorting and searching.

The standard library also offers a singly-linked list called forward_list. A forward_list doesn't even keep its number of elements. If you need the element count, count. If you can't afford to count, you probably shouldn't use a forward_list.

11.4

The standard library offers a balanced binary search t ree called map. In other contexts, a map is known as an associative arry or a dictionary

11.5

The cost of a map lookup is O(logN), where N is the number of elements in the map. The standard-library hashed containers are referred to as "unordered" because they don't require an ordering function.

The standard library provides a default hash function for strings as well as for other built-in and standard-library types.

Designing good hash functions is an art and sometimes requires knowledge of the data to which it will be applied.

We can avoid explicitly passing the hash operation by defining it as a speciailization of the standard-library hash.

// method 1: define hashing functor
struct Rhash {
    size_t operator()(const Record& r) const
    {
        return hash<string>()(r.name) ^ hash<int>()(r.number);
    }  
};
std::unordered_set<Record, Rhash> rs;


// method 2: specialization std::hash
namespace std{
    template<> struct hash<Record>
    {
        using argument_type = Record;
        using result_type = std::size_t;
        size_t operator()(const Record& r) const
        {
            return hash<string>()(r.name) ^ hash<int>()(r.number);
        }
    };
}

The difference between a map and an unordered_map

A map requires an ordering function (the default is <) and yields an ordered sequence
A unordered_map requries an equality function (the default is ==); it does not maintain an order among its elements.

11.6

container	explanation
`vector<T>`	A variable-size vector
`list<T>`	A doubly-linked list
`forward_list<T>`	A singly-linked list
`deque<T>`	A double-ended queue
`set<T>`	A set
`multiset<T>`	A set in which a value can occur many times
`map<K,V>`	An associative array
`multimap<K, V>`	A map in which a key can occur many times
`unordered_map<K,V>`	A map using a hashed lookup
`unordered_multimap<K,V>`	A multimap using a hashed lookup
`unordered_set<T>`	A set using a hashed lookup
`unordered_multiset<T>`	A multiset using a hashed lookup

The container are defined in namespace std and presented in headers <vector> etc. In additino, the standard library provides container adaptors queue<T>, stack<T>, and priority_queue<T>. The standard library also provides more speciailized container-like tpys, such as array<T,N> and bitset<N>.

container operations	explanation
`value_type`	the type of an element
`p=c.begin()/c.end()`	first/last element of c. `cbegin()` for an iterator to be `const`
`k=c.size()/c.capacity`	the number of element in `c`/ the number of elements that `c` can hold without a new allocation
`c.empty()`	Is `c` empty?
`c.reserve(k)/c.resize(k)`	make the capacity `k` / make the number of elements `k`; added elements has the value `value_type{}`
`c[k]/c.at(k)`	the k-th element, without/with range check
`c.push_back(x)`	add `x` at the end of `c`
`c.emplace_back(a)`	add `value_type{a}` at the end of `c`
`q=c.insert(p,x)`	add `x` before `p` in `c`
`q=c.erase(p)`	remove element at `p` from `c`
`c = c2`	assignment
`c==c2/c!=c2`	equality comparisong
`c<=>c2`	lexicographical order of `c` and `c2`

Please note that a vector is usually more efficient that a list for short sequences of small elements.

Consider the singly-linked list, forward_list, a container optmized for the empty sequence. An empty forward_list occupies just one word, whereas an empty vector occupy three. Empty sequences, and sequences with only an element or two, are surprisingly common and useful.

An emplace operation, such as emplace_back takes arguments for an element's constructor and builds the boject in a newly allocated space in the container, rather than copying an object into the container.

TODO

check standard implementation of std::vector()
check the SafeVec use of using std::vector<T>::vector to make default vector constructor visible in SafeVec: https://en.cppreference.com/w/cpp/language/using_declaration