Code Yarns ‍👨‍💻
Tech BlogPersonal Blog

Notes from Effective STL

📅 2010-May-25 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ books, 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.

The standard sequence containers are: vector, list, deque, string The standard associative containers are: set, multiset, map, multimap

string is typedef of basic_string wstring 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() );

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, use std::deque instead. It offers everything that the former does.

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

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.

Passing functors is actually faster than passing pointer to a function! 😊