Effective STL

Effective STL
50 Specific Ways to Improve Your Use of the Standard Template Library
Scott Meyers

Containers
Item 1	Choose your containers with care.	11
Item 2	Beware the illusion of container-independent code.	15
Item 3	Make copying cheap and correct for objects in containers.	20
Item 4	Call empty instead of checking size against zero.	23
Item 5	Prefer range member functions to their single-element counterparts.	24
Item 6	Be alert for C++'s most vexing parse.	33
Item 7	When using containers of newed pointers, remember to delete the pointers before the container is destroyed.	36
Item 8	Never create containers of auto_ptrs.	40
Item 9	Choose carefully among erasing options.	43
Item 10	Be aware of allocator conventions and restrictions.	48
Item 11	Understand the legitimate uses of custom allocators.	54
Item 12	Have realistic expectations about the thread safety of STL containers.	58
**vector and string**
Item 13	Prefer vector and string to dynamically allocated arrays.	63
Item 14	Use reserve to avoid unnecessary reallocations.	66
Item 15	Be aware of variations in string implementations.	68
Item 16	Know how to pass vector and string data to legacy APIs.	74
Item 17	Use "the swap trick" to trim excess capacity.	77
Item 18	Avoid using vector<bool>.	79
Associative Containers
Item 19	Understand the difference between equality and equivalence.	83
Item 20	Specify comparison types for associative containers of pointers.	88
Item 21	Always have comparison functions return false for equal values.	92
Item 22	Avoid in-place key modification in set and multiset.	95
Item 23	Consider replacing associative containers with sorted vectors.	100
Item 24	Prefer map::insert to map::operator[] when efficiency is a concern.	106
Item 25	Familiarize yourself with the nonstandard hashed containers.	111
Iterators
Item 26	Prefer iterator to const_iterator, reverse_iterator, and const_reverse_iterator.	116
Item 27	Use distance and advance to convert const_iterators to iterators.	120
Item 28	Understand how to use a reverse_iterator's base iterator.	123
Item 29	Consider istreambuf_iterators for character by character input.	126
Algorithms
Item 30	Make sure destination ranges are big enough.	129
Item 31	Know your sorting options.	133
Item 32	Follow remove-like algorithms by erase if you really want to remove something.	139
Item 33	Be wary of remove-like algorithms on containers of pointers.	143
Item 34	Note which algorithms expect sorted ranges.	146
Item 35	Implement simple case-insensitive string comparisons via mismatch or lexicographical_compare.	150
Item 36	Use not1 and remove_copy_if to perform a copy_if.	154
Item 37	Use accumulate or for_each to summarize sequences.	156
Functors, Functor Classes, Functions, etc.
Item 38	Design functor classes for pass-by-value.	162
Item 39	Make predicates pure functions.	166
Item 40	Make functor classes adaptable.	169
Item 41	Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref.	173
Item 42	Make sure less means operator<.	177
Programming with the STL
Item 43	Prefer algorithm calls to hand-written loops.	181
Item 44	Prefer member functions to algorithms with the same names.	190
Item 45	Distinguish among count, find, binary_search, lower_bound, upper_bound, and equal_range.	192
Item 46	Consider function objects instead of functions as algorithm parameters.	201
Item 47	Avoid producing write-only code.	206
Item 48	Always #include the proper headers.	209
Item 49	Learn to decipher STL-related compiler diagnostics.	210
Item 50	Familiarize yourself with STL-related web sites.	217

Notes

Continguous-memory containers: vector, deque, string
Node-based containers: list, associative containers (set, map, multiset, multimap), hashed containers (unordered_set, unordered_map, unordered_multiset, unordered_multimap)
Is lookup speed a critical consideration? Use (in this order): p14: 1) hashed containers 2) sorted vectors 3) associative containers
To search an unsorted range:: find, find_if ... returns where found, stops when found; count, count_if ... returns how many; all use "equality" (based on operator==)
To search a sorted range:: equal_range, lower_bound, upper_bound, binary_search (rarely used, only returns bool); all use "equivalence" (neither value precedes the other p85)
Cheapest sort to most expensive:: map/set ... elements maintained in sorted order; partition ... runs in linear time; stable_partition ... runs in linear time; nth_element ... runs in linear time, requires random-access iterators (can't use on a list); partial_sort ... requires random-access iterators; sort ... requires random-access iterators; stable_sort ... requires random-access iterators
What they do:: partition ... divides the range into 2 groups; nth_element ... put a single element in the correct nth position, all others placed before or after; partial_sort ... nth_element plus: sort the preceding elements; stable_xxx ... maintains the original order of secondary "sort key"
Algorithms that have comparable container member functions: associative containers: count, find, lower_bound, upper_bound, equal_range; list container: remove, remove_if, unique, sort, merge, reverse

What you want to know
Item 45: Distinguish between count, find, binary_search,
lower_bound, upper_bound, and equal_range Algorithm to use Member function to use
on an unsorted
range on a sorted
range with a set
or map with a multiset
or multimap
Does the desired value exist? find binary_search count find
Does the desired value exist? If so, where is the first element with that value? find equal_range find find (not guaranteed
to find the first)
or lower_bound
Where is the first element with a value not preceding the desired value? find_if lower_bound lower_bound lower_bound
Where is the first element with a value succeeding the desired value? find_if upper_bound upper_bound upper_bound
How many elements have the desired value? count equal_range, then distance count count
Where are all the elements with the desired value? find (iteratively) equal_range equal_range equal_range

Item 47: Avoid producing write-only code ... Suppose you want to get rid of all elements in a vector whose value is less than X, except that elements preceding the last occurrence of a value at least as big as Y should be retained. p206

   v.erase( remove_if( find_if( v.rbegin(), v.rend(),
                                bind2nd( greater_equal(), Y ) ).base(),
                       v.end(),
                       bind2nd( less(), X ) ),
            v.end() );

   v.f1(f2(f3(v.f4(),v.f5(),f6(f7(),y)).f8(),v.f9(),f6(f10(),x)),v.f9());

What you want to know Item 45: Distinguish between count, find, binary_search, lower_bound, upper_bound, and equal_range	Algorithm to use		Member function to use
	on an unsorted range	on a sorted range	with a set or map	with a multiset or multimap
Does the desired value exist?	find	binary_search	count	find
Does the desired value exist? If so, where is the first element with that value?	find	equal_range	find	find (not guaranteed to find the first) or lower_bound
Where is the first element with a value not preceding the desired value?	find_if	lower_bound	lower_bound	lower_bound
Where is the first element with a value succeeding the desired value?	find_if	upper_bound	upper_bound	upper_bound
How many elements have the desired value?	count	equal_range, then distance	count	count
Where are all the elements with the desired value?	find (iteratively)	equal_range	equal_range	equal_range

Effective STL 50 Specific Ways to Improve Your Use of the Standard Template Library Scott Meyers

Notes

Effective STL
50 Specific Ways to Improve Your Use of the Standard Template Library
Scott Meyers