Title: Theory / Unimportant / CS / Programming / C++ / Manual / IV STL / 31 Container
Tags: automatedNewLineAfterCommaSpace
On every note of this deck, unless a note says otherwise:
Language: C++
Language: C++
Chapter: 31

Name: A sequence container
Definition: A container providing access to a sequence of elements
Page: 886
Chapter: 26
Section: 3.1

Name: An associative container
Definition: A container providing associating lookup based on a key
Page: 886
Chapter: 31
Section: 2
Context: stl

Name: A container adaptor
Definition: A class that uses an underlying container and restrict the API the user has access to
Page: 886, 920
Chapter: 31
Section: 2, 5
Example: stack and queue transfor a deque into a stack and a queue

Name: An almost container
Definition: An object that provides access to a sequences of elements but do not provide all facilities of a container
Page: 886
Chapter: 31
Section: 2

Typ: vector<T, A>
Meaning: A contiguously allocated sequence of T s;
Page: 886
Chapter: 31
Section: 2
Variables: T a type
A an allocator for T

Typ: list<T, A>
Meaning: A doubly-linked list of T ; use when you need to insert and delete elements without moving existing elements
Page: 886
Chapter: 31
Section: 2
Variables: T a type
A an allocator for T

Typ: forward_list<T, A>
Meaning: A singly-linked list of T
Page: 886
Chapter: 31
Section: 2
Variables: T a type
A an allocator for T
Intuition: ideal for empty and very short sequences

Typ: deque<T, A>
Meaning: A double-ended queue of T ; a cross between a vector and a list;
slower than one or the other for most uses
Page: 886
Chapter: 31
Section: 2
Variables: T a type
A an allocator for T

Typ: map<K,V,C,A>
Meaning: An ordered map from K to V ; a sequence of ( K , V ) pairs
Page: 887
Chapter: 31
Section: 2
Variables: K, V types
A an allocator for K
C a comparison for K

Typ: multimap<K,V,C,A>
Meaning: An ordered map from K to V ; duplicate keys allowed
Page: 887
Chapter: 31
Section: 2
Variables: K, V types
A an allocator for K
C a comparison for K

Typ: set<K,C,A>
Meaning: An ordered set of K
Page: 887
Chapter: 31
Section: 2
Variables: K a type
A an allocator for K
C a comparison for K

Typ: multiset<K,C,A>
Meaning: An ordered set of K, duplicate keys allowed
Page: 887
Chapter: 31
Section: 2
Variables: K a type
A an allocator for K
C a comparison for K

Typ: unordered_map<K, V, H, E, A>
Meaning: An unordered map from K to V
Page: 887
Chapter: 31
Section: 2
Variables: K, V types
A an allocator for K
H a hash-function for K
E an equality predicate for E

Typ: unordered_multimap<K, V, H, E, A>
Meaning: An unordered map from K to V, duplicate key allowed
Page: 887
Chapter: 31
Section: 2
Variables: K, V types
A an allocator for K
H a hash-function for K
E an equality predicate for E

Typ: unordered_multiset<K, H, E, A>
Meaning: An unordered set of K, duplicate key allowed
Page: 887
Chapter: 31
Section: 2
Variables: K a type
A an allocator for K
H a hash-function for K
E an equality predicate for E

Typ: unordered_set<K, H, E, A>
Meaning: An unordered set of K
Page: 887
Chapter: 31
Section: 2
Variables: K a type
A an allocator for K
H a hash-function for K
E an equality predicate for E

Instruction: std::equal_to<T>
Page: 887
Section: 2
Returns: The function operator== restricted to T
Variables: T a type

Instruction: std::less<T>
Page: 887
Section: 2
Returns: The function operator< restricted to T
Variables: T a type

Typ: priority_queue<T, C=std::vector<T>, Cmp=std::less<T>>
Meaning: A priority queue for elements of type T, using C as underlying structure and Cmp to compute priority
Page: 887
Chapter: 31
Section: 2
Variables: T a type
C a container of T
Cmp a priority function for T

Typ: stack<T, C=std::vector<T>>
Meaning: A stack of elements of type T, using C as underlying structure
Page: 887
Chapter: 31
Section: 2
Variables: T a type
C a container of T

Typ: queue<T, C=std::deque<T>>
Meaning: A queue of elements of type T, using C as underlying structure
Page: 887
Chapter: 31
Section: 2
Variables: T a type
C a container of T

Typ: array<T, N>
Meaning: A fixed-size array of N contiguous elements of type T ;
Page: 887, 974
Chapter: 31, 34
Section: 2, 2.1
Variables: T a type
N an int
Intuition: Solve some problems that T[N] don't, such as implicit conversion to pointer

Typ: basic_string<T, Tr, A>
Meaning: A string with character C, optimized when strings are short
Page: 887
Chapter: 31
Section: 2
Variables: T a type
Tr a characetr traits
A an allocator for T

Typ: string
Meaning: basic_string<char>
Page: 887
Chapter: 31
Section: 2

Typ: u16string
Meaning: basic_string<char16_t>
Page: 887
Chapter: 31
Section: 2

Typ: u32string
Meaning: basic_string<char32_t>
Page: 887
Chapter: 31
Section: 2

Typ: wstring
Meaning: basic_string<wchar_t>
Page: 887
Chapter: 31
Section: 2

Typ: valarray<T>
Meaning: A numerical vector with vector operations, but with restrictions
to encourage high-performance implementations;
use only if you do a lot of vector arithmetic
Page: 887
Chapter: 31
Section: 2
Variables: T a type

Typ: bitset<N>
Meaning: A set of N bits with set operations, such as & and |
Page: 887, 977
Chapter: 31, 34
Section: 2, 2.2
Variables: N a number
Intuition: Set of numbers between 0 and N-1, or N-bit binary number

Typ: vector<bool>
Meaning: A specialization of vector<T> with compactly stored bits
Page: 887
Chapter: 31
Section: 2

Name: A handle
Definition: An object that represents a container from the point of view of the user. It may simply be a link to the actual objects containing the data
Page: 887
Chapter: 31
Section: 2.1
Context: C++ container

Question: How to create container of type that also accept the descendant of this type
Answer: Create a container for pointer or reference
Page: 890
Chapter: 31
Section: 2.1
Context: C++ container

Question: How to create container for type that don't allow copy/move
Answer: Create a container for pointer or reference
Page: 890
Chapter: 31
Section: 2.1
Context: C++ container

Question: How do ordered containers check for equality
Answer: if a comparison cmp is provided, uses !cmp(x, y) && !cmp(y, x)
Page: 892
Chapter: 31
Section: 2.2.1
Context: C++ container

Name: An iterator
Definition: A data structure that allow to access each elements of the container one by one
Page: 894
Chapter: 31
Section: 2.2.1
Context: C++ container

Name: A forward iterator
Definition: A data structure that allow to access each element one after the other in a fixed order with the ++ operator
Page: 894
Chapter: 31
Section: 2.2.1
Context: C++ container

Name: A Bidirectional iterator
Definition: An iterator with ++ and -- to access the next/previous element of the container
Page: 894
Chapter: 31
Section: 2.2.1
Context: C++ container

Name: A random acces iterator
Definition: An iterator which alow to access any element of the container, using +n to get the n-th next element
Page: 894
Chapter: 31
Section: 2.2.1
Context: C++ container

Name: amortized O(f(n)) complexity
Page: 895
Chapter: 31
Section: 2.2.1
Context: C++ container
Notation: O(f(n))+ complexity

Typ: c.value_type
Meaning: The type of elements contained in c
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.allocator_type
Meaning: The type of memory manager used by c
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.size_type
Meaning: Unsigned type of container subscripts, element counts, etc.
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.difference_type
Meaning: Signed type of difference between iterators
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.iterator
Meaning: Behaves like c.value_type∗, with a ++ operation
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.reverse_iterator
Meaning: Behaves like c.value_type∗, with a -- operation
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.const_reverse_iterator
Meaning: Behaves like const c.value_type∗, with a -- operation
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.const_iterator
Meaning: Behaves like const c.value_type∗, with a ++ operation
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.reference
Meaning: c.value_type&
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.const_reference
Meaning: const c.value_type&
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.pointer
Meaning: c.value_type*
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.const_pointer
Meaning: c.value_type const *
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c a container

Typ: c.key_type
Meaning: The type of key of this conatiner
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c an associative container

Typ: c.mapped_type
Meaning: The type of value of this conatiner
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c an associative container

Typ: c.key_compare
Meaning: Type of comparison criterion;
Page: 896
Chapter: 31
Section: 2.2.1
Context: C++ container
Kind: c an associative ordered container

Typ: c.hasher
Meaning: Type of hash function
Page: 896
Chapter: 31
Section: 3.1
Context: C++ container
Kind: c an associative unordered container

Typ: c.key_equal
Meaning: Type of equivalence function
Page: 896
Chapter: 31
Section: 3.1
Context: C++ container
Kind: c an associative unordered container

Typ: c.local_iterator
Meaning: Type of bucket iterator
Page: 896
Chapter: 31
Section: 3.1
Context: C++ container
Kind: c an associative unordered container

Typ: c.const_local_iterator
Meaning: Type of bucket iterator to constant value
Page: 896
Chapter: 31
Section: 3.1
Context: C++ container
Kind: c an associative unordered container

Instruction: C c{}
Page: 896
Context: C++ container
Section: 3.2
Returns: An empty container of type c
Variables: C a container type

Instruction: C c{a}
Page: 896
Context: C++ container
Section: 3.2
Returns: An empty container of type C using allocator a
Variables: C a container type

Instruction: C c(n)
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C with n value_type{} elements
Variables: C a non associative container type

Instruction: C c(
  n,
  x
)
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C with n times the value x
Variables: C a non associative container type

Instruction: C c(
  n,
  x,
  a
)
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C with n times the value x and allocator a
Variables: C a non associative container type

Instruction: C c {element}
Page: 896
Context: C++ container
Section: 3.2
Returns: ???
Variables: C a non associative container type

Instruction: C {c2}
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C, copying in it the content of c2 and its allocator
Variables: C a non associative container type

Instruction: C {move(c2)}
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C, moving in it the content of c2 and its allocator
Variables: C a non associative container type

Instruction: C {begin, end}
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C, moving in it the elements from position begin included up to position end excluded
Variables: C a non associative container type

Instruction: C {begin, end, allocator}
Page: 896
Context: C++ container
Section: 3.2
Returns: A container of type C, moving in it the elements from position begin included up to position end excluded, with allocator
Variables: C a non associative container type

Instruction: c.~C()
Page: 896
Context: C++ container
Section: 3.2
Returns: destroy c ’s elements and release all resources
Variables: C a non associative container type

Instruction: c2 = c
Page: 896
Context: C++ container
Section: 3.2
Returns: copy c ’s elements into c2
Variables: C a non associative container type
C c, c2

Instruction: c2 = move(c)
Page: 896
Context: C++ container
Section: 3.2
Returns: move c ’s elements into c2
Variables: C a non associative container type
C c, c2

Instruction: c = {elem}
Page: 896
Context: C++ container
Section: 3.2
Returns: Assign to c from initializer_list {elem}
Variables: C a non associative container type
C c, c2

Instruction: c.assign(
  n,
  y
)
Page: 896
Context: C++ container
Section: 3.2
Returns: Assign n copies of x
Variables: C an associative container type
C c

Instruction: c.assign(
  begin,
  end
)
Page: 896
Context: C++ container
Section: 3.2
Returns: Assign to c from [b: e)
Variables: T a type
C<T> an associative container type for type T
C c
T* begin,
  end

Definition: Represents the set of elements elt, starting with *b, and reachable by b++ up to b==e, with this value excluded
Page: 896
Chapter: 31
Section: 3.2
Variables: T a type
T* begin, end
Context: C++ container
Notation: [b: e)

Name: The size of c
Definition: The number of elements in c
Page: 896
Chapter: 31
Section: 3.2
Variables: c a container
Context: C++ container

Name: The capacity of c
Definition: The number of elements that c can contains without needing a resize
Page: 898
Chapter: 31
Section: 3.3
Variables: c a vector/string
Context: C++ container

Instruction: c.size()
Page: 898
Context: C++ container
Section: 3.3
Returns: The size of c
Variables: c a container

Instruction: c.empty()
Page: 898
Context: C++ container
Section: 3.3
Returns: Is c empty
Variables: c a container

Instruction: c.max_size()
Page: 898
Context: C++ container
Section: 3.3
Returns: The largest possible number of elmeents of c
Variables: c a container

Instruction: c.reserve(n)
Page: 898
Effect: Reserve space for n elements for c
Context: C++ container
Section: 3.3
Variables: c a vector/string
Intuition: Ensure that no resize occurs, hence that current pointers remain valid. Also assure predictability of each individual add to the vector. No noticeable decrease on overal cost however

Instruction: c.reserve(
  n,
  v
)
Page: 898
Effect: Reserve space for n elements for c, uses v for added elements
Context: C++ container
Section: 3.3
Variables: c a vector/string

Instruction: c.shrink_to_fit()
Page: 898
Effect: c.reserve(c.size())
Context: C++ container
Section: 3.3
Variables: c a vector, deque or string

Instruction: c.clear()
Page: 898
Effect: Erase all elements of c
Context: C++ container
Section: 3.3
Variables: c a vector, deque or string

Instruction: c.begin()
Page: 898
Context: C++ container
Section: 3.3
Returns: Points to first elements of c
Variables: c a container

Instruction: c.end()
Page: 898
Context: C++ container
Section: 3.3
Returns: Points to one-past-last elements of c
Variables: c a container

Instruction: c.c(r)begin/c(r)end()
Page: 898
Context: C++ container
Section: 3.3
Returns: Same as c.b(r)egin/(r)end(), with pointer to constant elements
Variables: c a container

Instruction: c.rbegin/rend()
Page: 898
Context: C++ container
Section: 3.3
Returns: Same as c.begin/end(), with reverse order
Variables: c a container

Instruction: c.front()
Page: 900
Context: C++ container
Section: 3.5
Returns: Reference to first element of c
Variables: c a nonassociative container

Instruction: c[i]
Page: 900
Context: C++ container
Section: 3.5
Returns: Reference to the i th element of c
Variables: c a nonassociative nonlist container

Instruction: c.at(i)
Page: 900
Context: C++ container
Section: 3.5
Returns: Reference to the i th element of c
Variables: c a nonassociative nonlist container
Exception: throw an out_of_range if i is out of range;

Instruction: c.at(i)
Page: 900
Context: C++ container
Section: 3.5
Returns: Reference to the element with key k of c
Variables: c a map
Exception: throw an out_of_range if i is out of range;

Instruction: c[k]
Page: 900
Effect: insert ( k , mapped_type{} ) if not found; for map and unordered_map only
Context: C++ container
Section: 3.5
Returns: Reference to the element with key k of c
Variables: c a map

Instruction: c.push_back(x)
Page: 900
Effect: Add x to c (using copy or move) after the last element. Do nothingi n case of exception, the container remains intact
Context: C++ container
Section: 3.6
Variables: c a vector, deque or list

Instruction: c.pop_back()
Page: 900
Effect: Remove the last element from c
Context: C++ container
Section: 3.6
Variables: c a vector, deque or list

Instruction: c.emplace_back(args)
Page: 900
Effect: Add an object constructed from args to c after the last element
Context: C++ container
Section: 3.6
Variables: c a vector, deque or list

Instruction: c.emplace_front(args)
Page: 900
Effect: Add an object constructed from args to c before the first element
Context: C++ container
Section: 3.6
Variables: c a forward_list, deque or list

Instruction: c.push_front(x)
Page: 900
Effect: Add x by copy or move before the first element
Context: C++ container
Section: 3.6
Variables: c a forward_list, deque or list

Instruction: c.pop_front(x)
Page: 900
Effect: Remove the first element of c
Context: C++ container
Section: 3.6
Variables: c a forward_list, deque or list

Instruction: c.insert(
  p,
  x
)
Page: 901
Effect: Add x before p, using copy or move
Context: C++ container
Section: 3.7
Returns: A pointer to the inserted element
Variables: C<T> a container type
C c
p an iterator on c

Instruction: c.insert(
  p,
  n,
  x
)
Page: 901
Effect: Add n copies of x before p, using copy or move
Context: C++ container
Section: 3.7
Returns: A pointer to the n-th inserted element
Variables: C<T> a container type
C c
p an iterator on c

Instruction: c.insert(
  p,
  first,
  last
)
Page: 901
Effect: Add [first, last) just before p
Context: C++ container
Section: 3.7
Returns: A pointer to the last element added
Variables: C<T> a container type
C c
p an iterator on c
T* first,
  last

Instruction: c.insert(
  p,
  {elem}
)
Page: 901
Effect: Add elements of initializer_list{elem} before p
Context: C++ container
Section: 3.7
Returns: A pointer to the last element added
Variables: C<T> a container type
C c
p an iterator on c
T* first,
  last

Instruction: c.emplace(
  p,
  args
)
Page: 901
Effect: Add elements constructed from args before p
Context: C++ container
Section: 3.7
Returns: A pointer to the element added
Variables: C<T> a nonassociative container type
C c
p an iterator on c
T* first,
  last

Instruction: c.erase(p)
Page: 901
Effect: Remove p
Context: C++ container
Section: 3.7
Returns: The element after p
Variables: C<T> a nonassociative container type
C c
p an iterator on c
T* first, last

Instruction: c.erase(
  first,
  last
)
Page: 901
Effect: Remove [first, last) from p
Context: C++ container
Section: 3.7
Returns: last
Variables: C<T> a nonassociative container type
C c
first,
  last iterators on c

Instruction: c1 == c2
Page: 902
Context: C++ container
Section: 3.8
Returns: Do all corresponding elements of c1 and c2 compare equal
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1 != c2
Page: 902
Context: C++ container
Section: 3.8
Returns: !(c1==c2)
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1 < c2
Page: 902
Context: C++ container
Section: 3.8
Returns: Is c1 lexicographically before c2
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1 <= c2
Page: 902
Context: C++ container
Section: 3.8
Returns: !(c2<c1)
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1 > c2
Page: 902
Context: C++ container
Section: 3.8
Returns: c2<c1
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1 >= c2
Page: 902
Context: C++ container
Section: 3.8
Returns: !(c1<c2)
Variables: C<T> a nonassociative container type
C<T> c1, c2

Instruction: c1.swap(
  c2
),
swap(
  c1,
  c2
)
Page: 902
Context: C++ container
Section: 3.8
Returns: Exchanges values of c1 and c2
Variables: C<T> a nonassociative container type
C<T> c1,
  c2

Question: Difference between string and vector<char>
Answer: vector elements can be sorted, which is usually meaningless
Page: 902
Chapter: 31
Section: 4.1.4
Context: C++
Answer2: string can be converted to c string, knowing how to deal with 0 terminated, and stream
Answer3: string are often short so there is an optimization for this case

Question: When does an array<T> or T[] is better than Vector<T>
Answer: If we really want data on stack
Page: 902
Chapter: 31
Section: 4.1.4
Context: C++
Answer2: If data is initialized at construction

Question: When does a List<T> is better than Vector<T>
Answer: When we often want to add elements in the middle of the sequence, but not related to a sort of the list
Page: 902
Chapter: 31
Section: 4.1.4
Context: C++
Answer2: When we can not copy elements (list operations uses nodes, whose pointers are changed without changing the stored element)

Instruction: lst.remove(v)
Page: 902
Effect: Remove all elements of lst with value v
Section: 4.1.4
Variables: T a type
list<T> lst

Instruction: lst.remove_if(f)
Page: 902
Effect: Remove all elements of lst satisfying the predicate f
Section: 4.1.4
Variables: T a type
list<T> lst

Instruction: lst.unique()
Page: 902
Effect: Remove all successive duplicate elements
Section: 4.1.4
Variables: T a type
list<T> lst

Instruction: lst.unique(eq_predicate)
Page: 902
Effect: Remove all successive duplicate elements according to eq_predicate
Section: 4.1.4
Variables: T a type
list<T> lst

Instruction: lst.merge(lst2)
Page: 902
Effect: Remove the content of lst2 and merge it in lst according to < order.
Section: 4.1.4
Variables: T a type
list<T> lst, lst2
Assuming: lst, lst2 sorted according to <

Instruction: lst.merge(
  lst2,
  order_pred
)
Page: 902
Effect: Remove the content of lst2 and merge it in lst according to order_pred
Section: 4.1.4
Variables: T a type
list<T> lst,
  lst2
bool order_pred(
  const T&,
  const T&
)
Assuming: lst,
  lst2 sorted according to order_pred

Instruction: lst.reverse()
Page: 902
Effect: Revrse the order of the leements of lst, noexcept
Section: 4.1.4
Variables: T a type
list<T> lst

Instruction: lst.splice(
  p,
  lst2
)
Page: 902
Effect: Insert the elements of lst2 before p ; lst2 becomes empty
Section: 4.1.4
Variables: T a type
list<T> lst,
  lst2
p a lst iterator

Instruction: lst.splice(
  p,
  lst2
)
Page: 902
Effect: remove the elements pointed by p2 from lst2 and move it before p
Section: 4.1.4
Variables: T a type
list<T> lst,
  lst2
p a lst iterator
p2 a lst2 iterator

Instruction: lst.splice(
  p,
  first2,
  last2
)
Page: 902
Effect: remove the elements at [first2, last2) from lst2 and move it before p in lst
Section: 4.1.4
Variables: T a type
list<T> lst,
  lst2
p a lst iterator
first2,
  last2,
  lst2 iterator

Instruction: lst.some_operation_after(
  p,
  args
)
Page: 902
Effect: same as lst.some_operation(p, args), but change is done after p instead of before
Section: 4.1.4
Variables: T a type
(
  forward_
)list<T> lst
p an iterator on lst

Instruction: map m {args, alloc}
Page: 910
Effect: Same as
map m {args}
with allocator alloc
Section: 4.1.4
Variables: T a type
cmp a comparator for T
alloc a T allocator

Instruction: map m {args, cmp}
Page: 910
Effect: same as
map m {args}
with comparator cmp
Section: 4.1.4
Variables: T a type
cmp a comparator for T

Instruction: map {}
Page: 910
Effect: Create an empty map m with default comparator and allocator
Section: 4.1.4
Variables: T a type

Instruction: map m {b, e}
Page: 910
Effect: m is a map initialized with elements of [b, e)
Section: 4.1.4
Variables: K, T a type,
T* iterator of a map<K, T>

Instruction: map m {m2}
Page: 910
Effect: move/copy m2 in m
Section: 4.1.4
Variables: K, T a type,
map<K, T> m2

Instruction: map m {{elem}}
Page: 910
Effect: construct a map m, with elements from initializer_list {elem}
Section: 4.1.4
Variables: K, T a type,
map<K, T> m2

Instruction: m.find(k)
Page: 910
Section: 4.1.4
Returns: first element with key k or c.end()
Variables: K, T a type,
map<K, T> m

Instruction: m.lower_bound(k)
Page: 910
Section: 4.1.4
Returns: pointer to first element with key >= k or c.end()
Variables: K, T a type,
map<K, T> m
Assuming: ordered map/set

Instruction: m.upper_bound(k)
Page: 910
Section: 4.1.4
Returns: pointer to first element with key > k or c.end()
Variables: K, T a type,
order_map<K, T> m

Instruction: m.equal_range(k)
Page: 910
Section: 4.1.4
Returns: pair(m.lower_bound(k), m.upper_bound(k))
Variables: K, T a type,
order_map<K, T> m

Instruction: m.insert(x)
Page: 910
Effect: insert x in m if possible (i.e. either multimap or key absent)
Section: 4.1.4
Returns: pair(pointer to the inserted element, whether the insertion occured)
Variables: K, T a type,
order_map<K, T> m

Instruction: m.insert(
  p,
  x
)
Page: 910
Effect: same as m.insert(p), uses p as hint to start the search of where to insert
Section: 4.1.4
Variables: K,
  T a type,
order_map<K,
  T> m

Instruction: m.insert(
  begin,
  end
)
Page: 910
Effect: same as c.insert(*p) for ever p in [begin, end)
Section: 4.1.4
Variables: K,
  T a type,
order_map<K,
  T> m
T* begin,
  end

Instruction: m.insert({args})
Page: 910
Effect: same as c.insert(*p) for ever p in initrializer_list args
Section: 4.1.4
Variables: K, T a type,
order_map<K, T> m
T* begin, end

Instruction: m.emplace_hint(
  p,
  args
)
Page: 910
Effect: same as m.emplace(args), with h as hint for where to start search for a place for the new entry
Section: 4.1.4
Variables: K,
  T a type,
order_map<K,
  T> m
T* begin,
  end

Instruction: m.key_comp()
Page: 910
Effect: A copy of the key comparison object
Section: 4.1.4
Variables: K, T a type,
order_map<K, T> m

Instruction: m.value_comp()
Page: 910
Effect: A copy of the value comparison object
Section: 4.1.4
Variables: K, T a type,
order_map<K, T> m

Instruction: m.count(k)
Page: 910
Effect: The number of elements with key k
Section: 4.1.4
Variables: K, T a type,
order_map<K, T> m

Instruction: unordered_map{args, eq_predicate}
Page: 910
Effect: Same as unordered_map{args}, with eq_predicate to check for equality
Section: 4.3.3
Variables: K, T a type,
bool eq_predicate(const K&, const K&)

Instruction: unordered_map{args, hash_function}
Page: 910
Effect: Same as unordered_map{args}, with hash_function
Section: 4.3.3
Variables: K, T a type,
sizet_t hash_function(const K&)

Instruction: unordered_map{n}
Page: 910
Effect: Create an unordered map with n buckets
Section: 4.3.3
Variables: K, T a type,

Instruction: unordered_map{}
Page: 910
Effect: Create an unordered map
Section: 4.3.3
Variables: K, T a type,

Instruction: m.hash_function()
Page: 910
Section: 4.3.3
Returns: the hash_function of m
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.key_eq()
Page: 910
Section: 4.3.3
Returns: the equality test of m
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.max_load_factor()
Page: 910
Section: 4.3.3
Returns: the maximum load factor of m
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.load_factor()
Page: 910
Section: 4.3.3
Returns: he number of elements divided by the number of buckets:
double(c.siz e())/c.bucket_count()
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.rehash(n)
Page: 910
Effect: Make c ’s bucket count >= n
Section: 4.3.3
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.reserve(n)
Page: 910
Effect: Make room for n entries (taking the load factor into account):
c.rehash(ceil(n/c.max_load_factor()))
Section: 4.3.3
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.bucket_count()
Page: 910
Effect: the number of buckets in m
Section: 4.3.3
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.max_bucket_count()
Page: 910
Effect: The largest possible number of elmeents in a bucket
Section: 4.3.3
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.bucket_size(n)
Page: 910
Section: 4.3.3
Returns: The number of elements in the n-th bucket
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.bucket(key)
Page: 910
Section: 4.3.3
Returns: the ord of the bucket in which an element with key k would be
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.(c)begin(n)
Page: 910
Section: 4.3.3
Returns: point to first element of bucket n (as a pointer to constant)
Variables: K, T a type,
unordered_map<K, T> m

Instruction: m.(c)end(n)
Page: 910
Section: 4.3.3
Returns: point after last element of bucket n (as a pointer to constant)
Variables: K, T a type,
unordered_map<K, T> m

Question: How should the bucket interface be used in unordered_map/set
Answer: To test and calibrate the performance. Once the right setting is known, it should be fixed in production
Page: 920
Chapter: 31
Section: 4.3.3
Variables: K, T a type,
unordered_map<K, T> m
Context: C++

Typ: stack<T, C = deque<T>>
Meaning: A stack of objects of type T, with underlying implementation C
Page: 920
Chapter: 31
Section: 4.3.3
Variables: T a type,
C a container

Typ: queue<T, C = deque<T>>
Meaning: A quee of values of type T, with underlying implementation C
Page: 920
Chapter: 31
Section: 4.3.3
Variables: T a type,
C a container

Instruction: s.top()
Page: 920
Section: 4.3.3
Returns: the top of the stack
Variables: T a type,
stack<T> s

Instruction: s.push(t)
Page: 920
Effect: Add t to the top of the stack
Section: 4.3.3
Variables: T a type,
stack<T> s

Instruction: s.pop()
Page: 920
Effect: remove the top of the stack
Section: 4.3.3
Variables: T a type,
stack<T> s

Instruction: q.pop()
Page: 923
Effect: remove the bottom of the queue
Section: 5.2
Variables: T a type,
queue<T> q

Instruction: q.front()
Page: 923
Section: 5.2
Returns: the bottom of the queue
Variables: T a type,
queue<T> q