📅 2010-May-25 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ 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 basic_string<char>
. wstring is typedef basic_string<wchar_t>
.
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
.
class Foo;
typedef std::vector<Foo> FooVec;
typedef FooVec::iterator FooVecIter;
Item 4: Call empty()
instead of checking size()
against zero. empty()
is a constant time operation on all containers. size()
can sometimes be a linear time operation on certain containers, like std::list
.
Item 5: Prefer range member functions to their single element counterparts. Instead of doing:
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.
std::remove()
does not remove elements from the container.Use the erase-remove idiom to achieve actual removal:
std::remove(), fooVec.end() ); fooVec.erase(
Item 14: Use reserve to avoid unnecessary reallocations.
Item 16: Know how to pass vector and string data to legacy APIs.
if ( !fooVec.empty() ) // This is important!
0], v.size() ); someCFunctionCall( &v[
vector<bool>
.It is a pseudo-container with a compressed representation of bools. Avoid using std::vector<bool>
, use std::deque<bool>
instead. It offers everything that the former does.
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.
Item 27: Use distance and advance to convert a container’s const_iterator to iterator.
STLContainer v;
STLContainer::const_iterator ci = SomeFunction();
STLContainer::iterator i( v.begin() );std::advance( i, std::distance<STLContainer::const_iterator>( i, ci ));
reverse_iterator
’s base iterator.The base()
iterator of a reverse_iterator
points 1 element in front of the reverse_iterator
position. Use with care.
istreambuf_iterator
for character-by-character input.Useful for unformatted input from files:
// 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! 😊