Effective STL Flashcards
What are the STL sequence containers?
vector, string, deque, list.
What are the STL associative containers?
map, set, multimap, multiset.
What are the contiguous-memory containers?
Containers that store their elements in one or more chunks of memory, each chunk holding more than one container element.
What are the node-based containers?
Containers that store only a single element per chunk of memory.
What are some of the contiguous-memory containers?
vector, string, deque.
What are some of the node-based containers?
list and all associative containers.
What type of iterators do contiguous-memory containers provide?
Random access iterators.
What type of iterators do node-based containers provide?
Bidirectional iterators.
What type of iterators does std::sort require?
Random access iterators.
Can std::map be used with std::sort algorithm?
No
Why can’t std::list be used with std::sort algorithm?
Because list uses bidirectional iterators and sort requires random access iterators.
Why is empty() prefered over size() == 0 check for container sizes?
Because empty is a constant-time evalutation and size can be linear operation and thus more innefficient.
What is a range member function?
Function taking two iterator parameters to speficy range of elements over which something should be done.
What are the costs of invoking single-element container functions?
Unecessary function calls (in a loop), memory allocation, innefficieny of moving elements in the container while inserting new elements.
What are the advantages of using range member functions?
Easier to write, more clear intent, higher performance
What does following statement declare: int f(double d);
Function taking double and returning an int.
What does following statement declare: int f(double (d));
Function taking double and returning an int, () are ignored.
What does following statement declare: int f(double);
Function taking double and returning an int, param name is omittted.
What does following statement declare: int g(double ());
Function taking a pointer to a function returning double with 0 args.
What does following statement declare: int g(double pf());
Function taking a pointer to a function returning double with 0 args, pf is implicitly a pointer.
What does following statement declare: int g(double (*pf)());
Function taking a pointer to a function returning double with 0 args, pf is explicitly marked as pointer.
What are two ways for making sure dynamically allocated objects in the container are freed?
Smart pointers or explicit delete invokation on each container element.
What is the time complexity of invoking erase for map and set?
Logartihmic
What is the time complexity of invoking erase for multimap and multiset?
Linear for a number of elements contained.
What is the recommended approach for removing all objects in a list that have particular value?
Use list’s remove member function because it is more efficient than std::remove.
What is the recommended approach for removing all objects in a contigous-memory container that have particular value?
Use erase-remove idiom -> Erase member function with std::remove for range.
What is the recommended approach for removing all objects in a associative container that have particular value?
Use erase member function of the container.
What is the recommended approach for removing all objects in a list that satisfy a particular predicate?
Use list’s remove_if member function.
What is the recommended approach for removing all objects in a contigous-memory container that satisfy a particular predicate?
Use erase-remove_if idiom.
What is the recommended approach for removing all objects in a associative container that satisfy a particular predicate?
Use remove_copy_if with swap or write a loop to walk the container elements, being sure to postincrement your iterator when you pass it to erase.
What “problems” does vector growth bring?
It invalidates all pointers and references to its internals because the content is relocated.
Why is vector bool not considered an STL container?
It does not fully conform to C++ standard rules for containers. operator[] does not return a reference to bool object.
How are bools stored internally in vector?
Stored like bitfields.
What does vector bool operator[] return?
Reference to a proxy object that wraps the bitfield representation of bool.
What does equality means in terms of associative containers?
Equality is based on operator==.
What is equivalence in terms of associative containers?
It is based on relative ordering of objects values in a sorted range. Two vales are equivalent if neither precedes the other on, according to some ordering criterion.
What is the default comparison for associative containers?
std::less
How are associative containers usually implemented?
As balanced binary search trees.
What is a drawback for using sorted vector instead of an associative container?
Keeping it sorted on lots of insertions and erasures.
What is the potential benefit of using a sorted vector instead of an associative container?
Less memory consumption and faster access (binary search).
What does std::partial_sort do?
Sorts n number of elements per specified criteria. Remaining elements (n+1, n+2) won’t be sorted.
What does std::nth_element do?
Finds an nth element and puts it to its nth position. All the elements that would follow up to that element are put before it.
What does std::partition do?
Finds all the elements that match the specified criteria and moves them to the beginning of the vector.
What is meant by stable sort?
Equivalent elements will be unchanged (their position won’t be changed) when sorted with stable sort.
What does std::remove do?
It moves the “to be removed” elements to the end of the range and returns an iterator pointing to the first element to be removed.
What does std::accumulate predicate must ensure?
It must not have side effects.
Function objects are modeled on what?
Function pointers.
How should function objects be passed?
By value.
What are the two things that should be taken into account when defining function objects?
They should be small (cheap to copy) and monophormic (not use virtual functions).
What is an advantage of function objects over function pointers?
They can hold more state (via members).
What is a predicate?
A function that returns a bool (or something implicitly convertable to bool).
What is a pure function?
Function whose return value depends only on its input parameters.
What is a predicate class?
Class whose operator() returns bool or something implicitly convertable to bool.
Why should operator() be marked as const?
To enforce imutability.
Why should std components never be modified or specialized (templates) ?
Because doing so can lead to UB.
What are the three reason describing why should algorithms be prefered over hand-written loops?
Efficiency, maintainability, correctness.
Why should member functions be prefered over std::algorithms with same name?
They are often faster and integrate better with the containers.
What is the time complexity of std::set find?
Logarithmic.
What is the time complexity of std::find ?
Linear.
What are the two things that one should consider when choosing between std algorithms and member functions?
Efficiency and correctness.
What is the time complexity of count and find?
Linear.
On what type of ranges should count and find be used for lookup?
On unsorted ranges.
On what type of testing are count and find based on?
Equality testing.
On what type of ranges should binary_search, lower_bound, upper_bound, equal_range be used?
On sorted ranges.
On what type of testing are binary_search and other similar algorithms based on?
Equivalence testing.
When should std::count be used?
When we want to see how many copies of certain value are there in the range.
When should std::find be used?
When we want to see if certain value exists and where it is.
What algorithm is more efficient, count or find?
Find because it returns when it finds the element.
