📅 2010-May-25 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ book, cpp, notes, stl ⬩ 📚 Archive
I recently read Effective STL by Scott Meyers. My review of the book can be found here. Below are my notes from the book.
One guideline that is missing in the book: Do not extend the STL containers. It is possible, but brings about nothing but misery.
Item 1: Choose your containers with care
The standard sequence containers are: vector, list, deque, string The standard associative containers are: set, multiset, map, multimap
string is typedef of basic_string
Scott does not mention this, but I find this useful because when you get compilation errors on string, they will mention basic_string<> and not string.
This item mentions the most important trick to cut the verbosity of STL: Typedef everything possible.
For example: cpp class Foo; typedef std::vector<Foo> FooVec; typedef FooVec::iterator FooVecIter;
empty() is a constant time operation on all containers. size() can sometimes be a linear time operation on certain containers, like std::list.
Instead of doing: cpp for (int i = 0; i < MAX; ++i) vec.push_back(arr[i]);
Try this:
std::copy( arr, arr, std::back_inserter(vec) );
For an example usage of std::back_inserter see this post.
To me, this is STL's biggest gotcha! std::remove() does not remove elements from the container.
Use the erase-remove idiom to achieve actual removal: cpp fooVec.erase( std::remove(), fooVec.end() );
Item 14: Use reserve to avoid unnecessary reallocations
Item 16: Know how to pass vector and string data to legacy APIs
cpp if ( !fooVec.empty() ) // This is important! someCFunctionCall( &v[0], v.size() );
It is a pseudo-container with a compressed representation of bools. Avoid using std::vector
Item 21: Always have comparison functions return false for equal values
Item 23: Consider replacing associative containers with sorted vectors
If the container is used in a phased manner, first phase only for insertions and the second phase only for lookups, then a sequence container might offer better performance than an associative container.
cpp STLContainer v; STLContainer::const_iterator ci = SomeFunction(); STLContainer::iterator i( v.begin() ); std::advance( i, std::distance<STLContainer::const_iterator>( i, ci ));
The base() iterator of a reverse_iterator points 1 element in front of the reverse_iterator position. Use with care.
Useful for unformatted input from files:
cpp // Read file to string std::ifstream iFile("haha.txt"); std::string fileData( std::istreambuf_iterator<char>( iFile ) ), std::istreambuf_iterator<char>() );
This usually leads to bugs. Instead, whenever possible use one of the inserters: std::inserter, std::back_inserter or std::front_inserter.
For an example usage of std::back_inserter see this post.
Ordered by performance, best to worst: partition stable_partition nth_element partial_sort sort stable_sort
These are: binary_search lower_bound upper_bound equal_range set_union set_intersection set_difference set_symmetric_difference merge inplace_merge includes
Item 37: Use accumulate or for_each to summarize ranges
Item 39: Make predicates pure functions
Predicate is a function that returns bool. Pure function is a function whose return value depends only on its input parameters. It does not have any side effects.
Inherit functors from std::unary_function or std::binary_function so that the necessary types are defined nicely for you.
Defining functors as classes or structs is purely a matter of style. STL uses structs. Some may find it better since there is no need to declare it as public.
Item 43: Prefer algorithm calls to hand written loops
Item 44: Prefer member functions to algorithms with the same names
Item 45: Distinguish among count, find, binary_search, lower_bound, upper_bound and equal_range
Item 46: Consider function objects instead of functions as algorithm parameters
Passing functors is actually faster than passing pointer to a function! 😊