Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
170 Cards in this Set
- Front
- Back
- 3rd side (hint)
|
Sequence containers
|
- array
- deque - forward_list - list - vector |
|
|
|
Associative containers
|
- map
- multimap - set - multiset |
|
|
|
Unordered associative containers
|
- unordered_map
- unordered_set |
|
|
|
Container adaptors
|
- queue
- priority_queue - stack |
|
|
|
erase(), clear(), pop_back(), pop_front(), swap()
|
These functions don't throw exceptions.
|
|
|
|
swap() impact on elements
|
Does not invalidate any references, pointers or iterators referring to the elements of the containers being swapped.
NOTE: The end() iterator does not refer to an elements, so may be invalidated. |
|
|
|
Given a container type X having an allocator_type identical to A and a value_type identical to T and given an lvalue m of type A, a pointer p of type T*, an expression v of type T, and an rvalue rv of type T, the following terms are defined. (If X is not allocator-aware, the terms below are defined as if A were std::allocator<T>.)
— T is CopyInsertable into X |
means that the following expression is well-formed: allocator_traits<A>::construct(m, p, v);
|
|
|
|
Given a container type X having an allocator_type identical to A and a value_type identical to T and given an lvalue m of type A, a pointer p of type T*, an expression v of type T, and an rvalue rv of type T, the following terms are defined. (If X is not allocator-aware, the terms below are defined as if A were std::allocator<T>.)
— T is MoveInsertable into X |
means that the following expression is well-formed: allocator_traits<A>::construct(m, p, rv);
|
|
|
|
Given a container type X having an allocator_type identical to A and a value_type identical to T and given an lvalue m of type A, a pointer p of type T*, an expression v of type T, and an rvalue rv of type T, the following terms are defined. (If X is not allocator-aware, the terms below are defined as if A were std::allocator<T>.)
— T is EmplaceConstructible into X from args, for zero or more arguments args, |
means that the following expression is well-formed:
allocator_traits<A>::construct(m, p, args); |
|
|
|
Sequence container definition
|
organizes a finite set of objects of the same type into a strictly linear arrangement.
|
|
|
|
Use a vector or array when...
|
in the general case.
|
|
|
|
Use a list or forward_list when...
|
there are frequent insertions and deletions from the middle of the sequence.
|
|
|
|
Use a deque when...
|
most insertions and deletions take place at the beginning or at the end of the sequence.
|
|
|
|
X(n, t)
X a(n, t) where X is a sequence container containing elements of type T n is a value of X::size_type a denotes a value of X t is an lvalue or a const rvalue of X::value_type |
Constructs a sequence container with n copies of t.
after call: distance(begin(), end()) == n |
Requires that T be CopyInsertable into X.
|
|
|
X(i, j)
X a(i, j) where a denotes a value of X X is a sequence container containing elements of type T i and j are iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_type. |
Constructs a sequence container equal to the range [i, j)
where i and j are iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_type. [i, j) is a valid range after call: distance(begin(), end()) == distance(i, j) |
Requires that T be EmplaceConstructible into X from *i. For vector, if the iterator does not meet forward iterator requirements, T shall also be MoveInsertable into X. Each iterator in the range [i, j) shall be dereferenced exactly once.
|
|
|
X(il);
where X is a sequence container containing elements of type T il is an object of type initializer_list<value_type> |
Equivalent to X(il.begin(), il.end());
|
|
|
|
a = il
a denotes a value of X X is a sequence container containing elements of type T il is an object of type initializer_list<value_type> |
Assigns the range [il.begin(), il.end()) into a. All existing elements of a are either assigned to or destroyed.
|
Requires T to be CopyInsertable into X and CopyAssignable.
returns: *this which is X& |
|
|
a.emplace(p, args);
a denotes a value of X X is a sequence container containing elements of type T p denotes a valid const iterator to a args denotes a function parameter pack with the pattern Args&& Args denotes a template parameter pack |
Inserts an object of type T constructed with std::forward<Args>(args)... before p.
|
Requires T to be EmplaceConstructible into X from args. For vector and deque, T is also MoveInsertable into X and MoveAssignable.
Returns an iterator pointing to the new element constructed from args into a. |
|
|
a.insert(p, t)
a denotes a value of X X is a sequence container containing elements of type T t is an lvalue or a const rvalue of X::value_type p denotes a valid const iterator to a |
Inserts a copy of t before p.
|
Requires T to be CopyInsertable into X. For vector and deque, T shall also be CopyAssignable.
Returns an iterator pointing to the copy of t inserted into a. |
|
|
a.insert(p, rv)
a denotes a value of X X is a sequence container containing elements of type T p denotes a valid const iterator to a rv denotes a non-const rvalue of X::value_type |
Inserts a copy of rv before p.
|
Requires T to be MoveInsertable into X. For vector and deque, T should also be MoveAssignable.
Returns an iterator pointing to the copy of rv inserted into a. |
|
|
a.insert(p, n, t)
a denotes a value of X X is a sequence container containing elements of type T t is an lvalue or a const rvalue of X::value_type p denotes a valid const iterator to a n is a value of X::size_type |
Inserts n copies of t before p.
|
Requires T to be CopyInsertable into X and CopyAssignable.
Returns an iterator pointing to the copy of the first element inserted into a, or p if n == 0. |
|
|
a.insert(p, i, j)
a denotes a value of X X is a sequence container containing elements of type T p denotes a valid const iterator to a i and j are iterators (not into a) satisfying input iterator requirements and refer to elements implicitly convertible to value_type. |
Inserts copies of elements in [i, j) before p.
Each iterator in the range [i, j) is dereferenced exactly once. |
Requires T to be EmplaceConstructible into X from *i. For vector, if the iterator does not meet the forward iterator requirements, T should also be MoveInsertable into X and MoveAssignable.
Returns an iterator pointing to the copy of the first element inserted into a, or p if i == j. |
|
|
a.insert(p, il);
a denotes a value of X il is an object of type initializer_list<value_type> p denotes a valid const iterator to a |
Equivalent to a.insert(p, il.begin(), il.end()).
|
Returns an iterator pointing to a copy of the first element inserted into a, or p if il is empty..
|
|
|
a.erase(q)
a denotes a value of X q denotes a valid dereferenceable const iterator to a |
Erases the element pointed to by q.
|
For vector and deque, T needs to be MoveAssignable.
Returns iterator pointing to the element immediately following q prior to the element being erased, or a.end() if no such element exists. |
|
|
a.erase(q1, q2)
a denotes a value of X [q1, q2) denotes a valid range of const iterators in a |
Erases the elements in the range [q1, q2).
|
For vector and deque, T needs to be MoveAssignable.
Returns iterator points to the element pointed to by q2 prior to any elements being erased, or a.end() if no such element exists. |
|
|
a.clear()
|
Destroys all elements in a.
after call a.empty() returns true. |
Invalidates all references, pointers, and iterators referring to the elements of a, and may invalidate the past-the-end iterator.
Returns void. |
|
|
a.assign(i, j)
a denotes a value of X i and j are iterators (not in a) satisfying input iterator requirements and refer to elements implicitly convertible to value_type. [i, j) is a valid range |
Replaces elements in a with a copy of [i, j).
Each iterator in range [i, j) is dereferenced exactly once. |
Requires T to be EmplaceConstructible into X from *i and assignable from *i. For a vector, if the iterator does not meet the forward iterator requirements, T should also be MoveInsertable into X.
Returns void. |
|
|
a.assign(il)
a denotes a value of X il is an object of type initializer_list<value_type> |
Equivalent to a.assign(il.begin(), il.end()).
|
Returns void.
|
|
|
a.assign(n, t)
n is a value of X::size_type a denotes a value of X t is an lvalue or a const rvalue of X::value_type (and not a reference into a). |
Replaces elements in a with n copies of t.
|
Requires T to be CopyInsertable into X and CopyAssignable.
Returns void. |
|
|
Which containers support a.front()?
|
basic_string, array, deque, forward_list, list, vector
|
|
|
|
Which containers support a.back()?
|
basic_string, array, deque, list, vector
|
|
|
|
Which containers support a.emplace_front(args)?
|
deque, forward_list, list
|
|
|
|
Which containers support a.emplace_back(args)?
|
deque, list, vector
|
|
|
|
Which containers support a.push_front(t) and a.push_front(rv)?
t is an lvalue or a const rvalue of X::value_type rv denotes a non-const rvalue of X::value_type |
deque, forward_list, list
|
|
|
|
Which containers support a.push_back(t) and a.push_back(rv)?
t is an lvalue or a const rvalue of X::value_type rv denotes a non-const rvalue of X::value_type |
basic_string, deque, list, vector
|
|
|
|
Which containers support a.pop_front()?
|
deque, forward_list, list
|
|
|
|
Which containers support a.pop_back()?
|
basic_string, deque, list, vector
|
|
|
|
Which containers support a[n] to access elements?
|
basic_string, array, deque, vector
|
|
|
|
Which containers support a.at(n)?
|
basic_string, array, deque, vector
|
|
|
|
a.front()
1) returns what? 2) is equivalent to what other statement? |
1) reference or const_reference for constant a.
2) *a.begin() |
|
|
|
a.back()
1) returns what? 2) is equivalent to what other statement? |
1) reference or const_reference for constant a.
2) { auto tmp = a.end(); --tmp; return *tmp; } |
|
|
|
a.emplace_front(args) does what?
args denotes a function parameter pack with the pattern Args&& Args denotes a template parameter pack |
Prepends an object of type T constructed with std::forward<Args>(args)
|
Requires T to be EmplaceConstructible into X from args.
|
|
|
a.emplace_back(args) does what?
args denotes a function parameter pack with the pattern Args&& Args denotes a template parameter pack |
Appends an object of type T constructed with std::forward<Args>(args)
|
Requires T to be EmplaceConstructible into X from args. For vector T should also be MoveInsertable into X.
|
|
|
a.push_front(t)
t is an lvalue or a const rvalue of X::value_type |
Prepends a copy of t.
|
Requires T to be CopyInsertable into X.
Returns void. |
|
|
a.push_front(rv)
rv denotes a non-const rvalue of X::value_type |
Prepends a copy of rv.
|
Requires T to be MoveInsertable into X.
|
|
|
a.push_back(t)
t is an lvalue or a const rvalue of X::value_type |
Appends a copy of t.
|
Requires T to be CopyInsertable into X.
Returns void. |
|
|
a.push_back(rv)
rv denotes a non-const rvalue of X::value_type |
Appends a copy of rv.
|
Requires T to be MoveInsertable into X.
|
|
|
a.pop_front()
|
Destroys the first element.
Requires a.empty() to be false. |
Returns void.
|
|
|
a.pop_back()
|
Destroys the last element.
Requires a.empty() to be false. |
Returns void
|
|
|
Two other ways to write a[n]
|
*(a.begin() + n)
a.at(n) |
Returns reference or const_reference for a constant a.
Member function at() provides bounds checking and throws out_of_range if n >= a.size(). |
|
|
A class or pointer type X satisfies the requirements of a forward iterator if...
|
- X satisfies the requirements of an input iterator
- X satisfies the DefaultConstructible requirements - if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T - the expression r++ returns convertible to constX& with operational semantics { X tmp = r; ++r; return tmp; } - the expression *r++ is valid and returns a reference - objects of type X off the multi-pass guarantee |
|
|
|
Advantages of array container over an ordinary arrays?
|
Provides the benefits of a standard container:
- an array knows its own size - supports assignment - random access iterators, etc.) - aggregate type semantics of C-style arrays |
|
|
|
Data structure ususally used to implement std::map?
|
red-black trees
|
|
|
|
std::map - Complexity of search, removal, and insertion operations?
|
logarithmic complexity
|
|
|
|
std::array
Element access functions: |
- at
- operator[] - front - back - data |
|
|
|
std::array
Operations: |
- fill
- swap |
|
|
|
std::array
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::get(std::array) - std::swap(std::array) |
|
|
|
std::array
Helper classes: |
- std::tuple_size
- std::tuple_element |
|
|
|
std::array
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::vector
Member functions: |
- (constructor)
- (destructor) - operator= - assign - get_allocator |
|
|
|
std::vector
Element access functions: |
- at
- operator[] - front - back - data |
|
|
|
std::vector
Capacity functions: |
- empty
- size - max_size - reserve - capacity - shrink_to_fit |
|
|
|
std::vector
Modifier functions: |
- clear
- insert - emplace - erase - push_back - emplace_back - pop_back - resize - swap |
|
|
|
std::vector
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::vector) |
|
|
|
std::deque
Member functions: |
- (constructor)
- (destructor) - operator= - assign - get_allocator |
|
|
|
std::deque
Element access functions |
- at
- operator[] - front - back |
|
|
|
std::deque
Capacity functions: |
- empty
- size - max_size - shrink_to_fit |
|
|
|
std::deque
Modifier functions: |
- clear
- insert - emplace - erase - push_back - emplace_back - pop_back - push_front - emplace_front - pop_front - resize - swap |
|
|
|
std::deque
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::deque) |
|
|
|
std::forward_list
Member functions: |
- (constructor)
- (destructor) - operator= - assign - get_allocator |
|
|
|
std::forward_list
Element access functions: |
- front
|
|
|
|
std::forward_list
Capacity functions: |
- empty
- max_size |
|
|
|
std::forward_list
Modifier functions: |
- clear
- insert_after - emplace_after - erase_after - push_front - emplace_front - pop_front - resize - swap |
|
|
|
std::forward_list
Operations: |
- merge
- splice_after - remove - remove_if - reverse - unique - sort |
|
|
|
std::forward_list
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - swap(std::forward_list) |
|
|
|
std::forward_list
Underlying data structure? |
Singly-linked list
|
|
|
|
Advantage of forward_list over list?
|
- no overhead compared to its implementation in C.
- provides more space efficient storage, when bidirectional iteration is not needed. |
|
|
|
std::list
Underlying data structure used to implement? |
doubly-linked list
|
|
|
|
std::list
Member functions: |
- (constructor)
- (destructor) - operator= - assign - get_allocator |
|
|
|
std::list
Element access functions: |
- front
- back |
|
|
|
std::list
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::list
Modifier functions: |
- clear
- insert - emplace - erase - push_back - emplace_back - pop_back - push_front - emplace_front - pop_front - resize - swap |
|
|
|
std::list
Operations: |
- merge
- splice - remove - remove_if - reverse - unique - sort |
|
|
|
std::list
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::list) |
|
|
|
std::set
Data structure used to implement: |
red-black trees
|
|
|
|
std::set
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::set
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::set
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::set
Lookup functions: |
- count
- find - equal_range - lower_bound - upper_bound |
|
|
|
std::set
Observers: |
- key_comp
- value_comp |
|
|
|
std::set
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::set) |
|
|
|
std::multiset
Member functions |
- (constructor)
- (destructor) - operator= - get_allocatord |
|
|
|
std::multiset
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::multiset
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::multiset
Lookup functions: |
- count
- find - equal_range - lower_bound - upper_bound |
|
|
|
std::multiset
Observers: |
- key_comp
- value_comp |
|
|
|
std::multiset
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::multiset) |
|
|
|
std::map
Member classes: |
- value_compare
|
|
|
|
std::map
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::map
Element access functions: |
- at
- operator[] |
|
|
|
std::map
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::map
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::map
Lookup functions: |
- count
- find - equal_range - lower_bound - upper_bound |
|
|
|
std::map
Observer functions: |
- key_comp
- value_comp |
|
|
|
std::map
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::map) |
|
|
|
std::multimap
Member classes: |
value_compare
|
|
|
|
std::multimap
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::multimap
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::multimap
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase -swap |
|
|
|
std::multimap
Lookup functions: |
- count
- find - equal_range - lower_bound - upper_bound |
|
|
|
std::multimap
Observers: |
- key_comp
- value_comp |
|
|
|
std::multimap
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::multimap) |
|
|
|
std::unordered_set
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::unordered_set
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::unordered_set
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::unordered_set
Lookup functions: |
- count
- find - equal_range |
|
|
|
std::unordered_set
Bucket interface functions: |
- begin, cbegin
- end, cend - bucket_count - max_bucket_count - bucket_size - bucket |
|
|
|
std::unordered_set
Hash policy functions: |
- load_factor
- max_load_factor - rehash - reserve |
|
|
|
std::unordered_set
Observers: |
- hash_function
- key_eq |
|
|
|
std::unordered_set
Non-member functions: |
- operator==
- operator!= - std::swap(std::unordered_set) |
|
|
|
std::unordered_multiset
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::unordered_multiset
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::unordered_multiset
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::unordered_multiset
Lookup functions: |
- count
- find - equal_range |
|
|
|
std::unordered_multiset
Bucket interface: |
- begin, cbegin
- end, cend - bucket_count - max_bucket_count - bucket_size - bucket |
|
|
|
std::unordered_multiset
Hash policy: |
- load_factor
- max_load_factor - rehash - reserve |
|
|
|
std::unordered_multiset
Obserrvers |
- hash_function
- key_eq |
|
|
|
std::unordered_multiset
Non-member functions: |
- operator==
- operator!= - std::swap(std::unordered_multiset) |
|
|
|
std::unordered_map
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::unordered_map
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::unordered_map
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::unordered_map
Lookup functions: |
- at
- operator[] - count - find - equal_range |
|
|
|
std::unordered_map
Bucket interface functions: |
- begin, cbegin
- end, cend - bucket_count - max_bucket_count - bucket_size - bucket |
|
|
|
std::unordered_map
Hash policy functions: |
- load_factor
- max_load_factor - rehash - reserve |
|
|
|
std::unordered_map
Observers: |
- hash_function
- key_eq |
|
|
|
std::unordered_map
Non-member functions: |
- operator==
- operator!= - std::swap(std::unordered_map) |
|
|
|
std::unordered_multimap
Member functions: |
- (constructor)
- (destructor) - operator= - get_allocator |
|
|
|
std::unordered_multimap
Capacity functions: |
- empty
- size - max_size |
|
|
|
std::unordered_multimap
Modifier functions: |
- clear
- insert - emplace - emplace_hint - erase - swap |
|
|
|
std::unordered_multimap
Lookup functions: |
- count
- find - equal_range |
|
|
|
std::unordered_multimap
Bucket interface functions: |
- begin, cbegin
- end, cend - bucket_count - max_bucket_count - bucket_size - bucket |
|
|
|
std::unordered_multimap
Hash policy functions: |
- load_factor
- max_load_factor - rehash - reserve |
|
|
|
std::unordered_multimap
Observers: |
- hash_function
- key_eq |
|
|
|
std::unordered_multimap
Non-member functions: |
- operator==
- operator!- - std::swap |
|
|
|
std::stack
Member functions |
- (constructor)
- (destructor) - operator= |
|
|
|
std::stack
Element access functions: |
- top
|
|
|
|
std::stack
Capacity functions |
- empty
- size |
|
|
|
std::stack
Modifier functions: |
- push
- emplace - pop - swap |
|
|
|
std::stack
Non-member functions: |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::stack) |
|
|
|
std::stack
Helper classes |
std::uses_allocator
|
|
|
|
std::queue
Member functions: |
- (constructor)
- (destructor) - operator= |
|
|
|
std::queue
Element access functions: |
- front
- back |
|
|
|
std::queue
Capacity functions: |
- empty
- size |
|
|
|
std::queue
Modifier functions: |
- push
- emplace - pop - swap |
|
|
|
std::queue
Non-member functions |
- operator==
- operator!= - operator< - operator<= - operator> - operator>= - std::swap(std::queue |
|
|
|
std::queue
Helper classes: |
std::uses_allocator
|
|
|
|
std::priority_queue
Member functions: |
- (constructor)
- (destructor) - operator= |
|
|
|
std::priority_queue
Capacity functions: |
- size
- empty |
|
|
|
std::priority_queue
Element access functions: |
- top
|
|
|
|
std::priority_queue
Modifier functions: |
- push
- emplace - pop - swap |
|
|
|
std::priority_queue
Non-member functions: |
std::swap(std::priority_queue)
|
|
|
|
std::priority_queue
Helper classes |
std::uses_allocator
|
|
|
|
Algorithms library
C library functions |
- qsort
- bsearch |
|
|
|
Algorithms library
Numeric operations: |
- iota
- accumulate - inner_product - adjacent_difference - partial_sum |
|
|
|
Algorithms library
Min/Max operations |
- max
- max_element - min - min_element - minmax - minmax_element - lexicographical_compare - is_permutation - next_permutation - prev_permutation |
|
|
|
Algorithms library
Heap operations |
- is_heap
- is_heap_until - make_heap - push_heap - pop_heap - sort_heap |
|
|
|
Algorithms library
Set operations (on sorted ranges) |
- merge
- inplace_merge - includes - set_difference - set_interaction - set_symmetric_difference - set_union |
|
|
|
Algorithms library
Binary search operations (on sorted ranges) |
- lower_bound
- upper_bound - binary_search - equal_range |
|
|
|
Algorithms library
Sorting operations (on sorted ranges) |
- is_sorted
- is_sorted_until - sort - partial_sort - partial_sort_copy - stable_sort - nth_element |
|
|
|
Algorithms library
Partitioning operations |
- is_partitioned
- partition - stable_partition - partition_point |
|
