STL FAQ

From the makers of InspIRCd.
Jump to: navigation, search

Performance Tips

Reserve the estimated size of vectors in advance

This prevent unneeded allocations; use reserve() rather than specifying the size for the contructor - it will save allocation times.

Use pointer containers rather than object containers

The STL relies heavily on copy constructors; they will be internally called for the templated class many times for operations such as search and sort. The copy constructors pointers are cheap (copying the bits, basically) - making the entire process efficient.

Preincrement rather than postincrement

++it returns a reference, it++ returns an object; save the allocation on the stack by using preincrement whenever possible (especially in loops).

Insertions into trees

Usage of map::insert() is preferred to map::operator[]: in the first case, only the copy constructor is called, and in the latter - the default constructor followed by an assignment constructor.

Vector iteration – with iterators and not []

Actually any iteration should be done with an object rather than with random access; but in vectors this is particularly important, both for correctness (making sure you access only accessible memory) and efficiency.

Cache during iterations

OK, this is not specific to STL and even not to C++. Don't allocate or do anything inside loops if it can be done outside - the compiler will very rarely recognize this and cache the value. For example: while (container.size() > 5) { do_somthing(); } is not as efficient as size_t sz = container.size(); while (sz > 5) { do_somthing(); } Unless, of course, you are changing the container while iterating. Things that are commonly repeated in loops are iterator dereferencing (remember - operator* is overloaded for iterators and is not a simple memory access) and the end() function.

If possible, add/remove ranges of elements rather than looping

Once again, this prevents unneeded reallocations, resizes, tree rebalancing etc.

empty() better than (0==size())

This is due to the fact that empty() is always O(1), while size() is sometimes much more (for lists, it is linear in the list length).

Memory Issues

  • STL containers will not decrease in size even after you took all the elements out. To force downsizing, swap() vectors and copy hashes.
  • Binaries of STL small programs tend to inflate due to the large header filer; in any case; don't #include unless you use it (i.e. don't include stl.h, but only containers/algorithms you use). The size can further be reduced by uniting templates into (void*), but that's a bit risky.

Some Common Mistakes

  • Invalidation of iterators happens a lot when using a modifying / mutating algorithm on a container while iterating over it (e.g. erase()).
  • Incorrect map lookup: accessing maps using the [] operator will insert an empty node into the lookup entry if it does not exist.
  • auto_ptr should never be used in STL containers because of the ownership property that causes copy constructors to behave differently than STL expects.
  • Unsafe multithreading: STL is not thread safe. Use mutexes.
  • Inheriting a container: Don't do it unless you really know what you are doing.

How to pick an STL container

STLContainers.png

Use string.data() instead of string.c_str() when not null terminating

When you're doing operations on a std::string that do not require a null terminator (such as send()), you can use .data() instead of .c_str() to avoid a potential memory copy or allocation.