I have listed the 50 tips from the book below with my interpretation of what they mean. I look at at this page from time to time to remind myself in ana attempt to become a better STL programmer. You really need to read the book to understand the reasoning, but you are also welcome to blindly follow the advice if you so chose :-)
As a bonus, Scott Meyers also echos my feelings when he talks about the "One True Editor" being Emacs!
1) Choose your containers with care.
Know the difference between a vector, set, list and map or be forever doomed with inefficient code.
2) Beware of the illusion of container-independent code.
You design your operations to take advantage of the type of containers you use and vice-versa. Attempting to write code that works with any container is futile. If you are using lists, the inserting new elements to the front or middle is OK, but not with a vector. Your algorithm and data structure have to agree with each other.
3) Make copying cheap and correct for objects in conatiners.
Containers will make a copy of the object that you insert. This is fine when inserting integers and strings, but for large/complex objects becomes undesirable. If you do not want multiple copies of the object floating around, store pointers in containers rather than actual objects. If you are happy with multiple copies, get to know your copy-constructor.
4) Call empty instead of size() against zero.
Always better to is "if (c.empty())" rather than "if (c.size() == 0)" since depending on the container type size might have to count the number of objects before comparing it to zero. Vectors often know their size, but lists will often have to count it up.
5) Prefer range member functions to their single-element counterparts.
This is a bit tricky. Given two vectors how do you make v1 be the same as second half of v2? The right way is
v1.assign(v2.begin() + v2.size()/2, v2.end());Know your assign, do not use a loop. Using copy, as below will still get an implicit loop
v1.clear(); copy(v2.begin(), v2.size()/2, v2.end(), back_inserter(v1));and in fact most of the time you should be using insert instead of copy as in:
v1.insert(v1.end(), v2.begin() + v2.size()/2, v2.end());You can and should use range functions when creating containers, insert'ing elements, erase'ing element and assign'ing elements.
6) Be alert fo C++'s most vexing parse.
C++ will parse lines as functions even when you do not want them.
// Regular function declaration
int f(double d);
// Function with no named parameter
int f(double);
// Function that takes a pointer to a function taking nothing and returning double
int g(double (*pf)());
// Same as above without parameter name
int g(double (*pf)());
// Problem!
list<int> data(istream_iterator<int>(dataFile),
istream_iterator<int>());
// instead of having a variable data with 2 iterators we get
// a function where
// the first parameter is named datafile that is of type
// istream_iterator<int> and has superfluous parentheses around it
// the second parameter has no name, its type is pointer to
// function that takes nothing and returns istream_iterator<int>
// Argh, who would have thought?
A much more common mistake is to have "Widget w();" declaring a
function w when what you wanted to do was "Widget w;" and declare a
variable.
7) When using containers of new'ed pointers remember to delete the pointers before the container is destroyed.
Obvious, but so easy to miss.
// the template is inside the struct. If it was above struct, we'd
// need DeleteObject<Widget>() instead of DeleteObject
struct DeleteObject
{
template <typename T>
void operator()(const T* ptr) const
{
delete ptr;
}
}
for_each(v.begin(), v.end(), DeleteObject());
Scot suggests looking at shared_ptr in Boost library to make the above
code exception safe.
8) Never create containers of auto_ptrs.
auto_ptr's change ownership when assigned from one another. If you sort your container, the sort function may involve assignment and the contents of your container will change. Just say no, look at smatr_ptrs instead.
9) Choose carefully among erasing options.
the usual pattern is erase/remove as in
c.erase(remove(c.begin(), c.end(), 2004), c.end());It so happens that if you have a list, it is better to use "c.remove(2004)". If you want to remove objects matching a criteria
// for vector, string, dequeue c.erase(remove_if(c.begin(), c.end(), func_return_bool), c.end()); // lists get a special treatment again c.remove_if(func_return_bool);If you need to write a message to a log file, delete the object in addtion to removing it from the container, you will need to write your own loop. The return value of erase can be used to advance the iterator for sequence containers.
10) Beware of allocator conventions and restrictions.
Don't mess with them unless you know what you are doing.
11) Understand the legitimate use of custom allocators.
Ha, ha, ha. Way to advanced my web based cheat notes.
12) Have realistic expectations about the thread safety of STL containers.
Multiple readers are safe, multiple writes to different containers are safe. Writing multithreaded code is hard and you will probably lose an arm and a leg in the process.
13) Prefer vector and string to dynamically allocated arrays.
Duh! Reduce your dependencies on delete as much as possible.
14) Use reserve to avoid unnecessary reallocations.
If you are going to add 1000 items to a container, let the container know about it, play nice.
15) Be aware of variations in string implementations.
Many ways to string a cat, dive to deep and you mioght get hurt. Your implementation (or your next platform) may use strings that are referenced counted or not, have size similar to char* or not, may or may not require dynamic allocation when creating an empty string, etc.
16) Know how to pass vector and string data to legacy APIs.
Don't make your new code messy just because you need to interface with ancient code. Pass a vector using '&v[0]' if the function wants an array but watch out for cases if v is empty. Pass a string to a function wanting char* using 's.c_str())'
17) Use swap trick to trim excess capacity.
If your vector or string has grown in size and later shrunk, you can shed excess capacity using 'string(s).swap(s)' or 'vector<Type>().swap(v)'. The constructor creates a new string/vector of appropriate size and you swap it with the bloated one.
18) Avoid using vector<bool>.
It is not an STL container and it does not hold bools! Bizzare huh? vector<bool> has a packed representation, so it is a pseudo-container. Try deque<bool> or bitset as alternatives.
19) Understand the difference between equality and equivalence.
Equality is about operator==, equivalence is based on operator<.It becomes important when you have associative containers whether sorted or not.
20) Specify container types for associative containers of pointers.
If you have a 'set' of pointers to strings and you would like them stored alphabetically instead of by their pointer address define it as
struct StringPtrLess:
public binary_function<const string*, const string*, bool>
{
bool operator()(const string *ps1, const string *ps2) const
{
return *ps1 < *ps2;
}
};
set<string*, StringPtrLess > ssp;
// Now you can loop through the iterators and print strings in
alphabetical order.
We could also write a generic DereferenceLess that is not specific to
string
struct DereferenceLess
{
template <typename PtrType>
bool operator()(PtrType pT1, PtrType pT2) const
{
return *pT1 < *pT2;
}
};
set<string*, DerefereceLessLess > ssp;
21) Always have comparison functions return false for equal values.
You cannot define Greater as the negation of LessThan.
22) Avoid in-place key modification in set and multiset.
Copy the element, modify the copy, and insert it. Do not upset set/multiset.
23) Consider replacing associative containers with sorted vectors.
Associative containers are implemented as balanced binary search trees, good for a mix of insertions, erasures and lookups. If insertions are mostly separate from lookups, you can use vectors which would take less memory, sort it and use lookups at a cost of log n.
24) Choose carefully between map::operator[] and map::insert when efficiency is important.
For an empty container, when doing an 'add' operation -- The statement 'm[1]= 10;' creates an object using default constructor, and then assigns the value 10 to it. It would be better to construct the object with the value 10 instead. Using 'm.insert(IntWidgetMap::value_type(1, 10));' would save us 3 function calls (create default object, assign, destroy default object)
Insert is better for 'add' operation, but operator[] is better for update.
25) Familiraize yourself with the nonstandard hashed containers.
Yeah, sure, if you you want to write your own hash functions...
26) Prefer iterator to const_iterator, reverse_iterator and const_reverse_iterator.
iterator is privilidged when it comes to insert/erase. You can get to the others from there but not the other way around. const iterators are still useful in algorithms.
27) Use distance and advance to convert a container's const_iterator to iterators.
Use 'advance(i, distance<ConstIter>(i,ci));' to move the iterator. The casting is so that the iterators of the same type.
28) Understand how to use a reverse_iterator's base iterator.
ri.base() does not point to where ri points to. Use v.erase((++ri).base()); instead.
29) Consider istreambuf_iterators for character by character input.
The good way to read a file into a string is:
ifstream inputFile("data.txt");
string fileData(istreambuf_uterator<char>(inputFile)),
istreambuf_iterator<char>());
Much quicker than istream_iterators (up to 40% faster)
30) Make sure destination ranges are big enough.
Proper way to insert stuff is:
vector<int> results; transform(values.begin(), values.end(), back_inserter(results), transmogrify);You can use front_inserter for lists, but not a good idea for vectors. The insertions are done one object at a time
31) Know your sorting options.
sort/stable_sort for full sort, partial_sort to sort only the top nth elements in order, nth_element allows you to find the nth element without sorting, partition/stable_partition allows you to separate elements into two groups,
32) Follow remove-like algorithms by erase if you really want to remove something.
Remove just moves the undeleted elements to the beginning of the range. The removed elements may or may *not* be in range. Stick to 'v.erase(remove(v.begin(), v.end(), 999), v.end());' routine.
33) Be wary of remove-like algorithms on containers of pointers.
You need to delete the memory associated with pointers, so first call delAndNullify followed by erase/remove
void delAndNulliifyUncertified(Widget*& pWidget)
{
if (!pWidget->isCertified())
{
delete pWidget;
pWidget = 0;
}
}
for_each(v.begin(), v.end(), delAndNullifyUncertified);
v.erase(remove(v.begin(), v.end(),
static_cast<Widget*>(0)),
v.end());
if you have smart pointers you cans use
// using reference counting smart pointers
vector<RCSPW> v;
...
v.push_back(RCSPW(new Widget));
...
v.erase(remove_if(v.begin(), v.end(),
not1(mem_fun(&Widget::isCertified))),
v.end());
You will need a way to implicitly convert smart pointers to pointers
so Widget::isCertified can be called. shared_prt from Boost might be
handy.
34) Note which algorithms expect sorted ranges.
binary_search, upper/lower_blound, set_union/intrersection/difference/symmetric_difference, merge, inplace_merge, includes. The container must be sorted using "<" by default.
35) Implement simple case-insensitive string comparisons via mismatch or lexicogrophical_compare.
lexicographical_compare(s1.begin(), s1.end(),
s2.begin(), s2.end(),
ciCharLess);
Enough said.
36) Understand the proper implementation of copy_if.
Tricky code:
// we'd like to write
copy_if(w.begin(), w.end(), ostream_iterator<Widget>(cerr,"\n"), isDefective);
// we define copy_if as
template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end,
OutputIterator destBegin,
Predicate p)
{
while (begin != end)
{
if (p(*begin)) *destBegin++ = *begin;
++begin;
}
return destBegin;
}
37) Use accumulate or for_each to summarize ranges.
Write things like 'accumulate(v.begin(), v.end(), 1.0f, multiplies<float>());'
38) Design functor classes for pass-by-value.
Functors can contain state as needed. If the state is too big, the amount of information getting copied becomes expensive. To avoid this problem you create a small class that can be used as a functor, and the functor points to the actual big class for doing the work. Of course, if the functor gets copied, the pointer to the implementation gets copied as well and has to be deleted when all teh copies are done. The implementation itself is not copied, so avoid prematuire deletion.
39) Make predicates pur functions.
Predicate should return bool or equivalent and not have any state information since it might get copied along the way.
40) Make functor classes adaptable.
If you want to use not1, not2, bind1st and bind2nd you either have to wrap the function with ptr_fun or have them be operators of a class that inherits from std::unary_function/std::binary_function.
41) Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref.
It has to do with how the function is called as in f(x), x.f() or p->f(). Learn it.
42) Make sure less<T> means operator<.
Misleads programmers and possibly algorithms.
43) Prefer algorithm calls to hand-written loops.
Duh! Use for_each, transform, copy, etc. Yes, there are lots of functions and you will have to look them up occasionally, but the advatages in readability, efficiency, correctness are overwhelming to use library algorithms. Deocde this for fun!
vector<int>::iterator i =
find_if(v.begin(), v.end(),
compose2(logical_and<bool>(),
bind2nd(greater<int>(), x),
bind2nd(less<int>(), y)));
44) Prefer member functions to algorithms with the same names.
If there is a list::remove iot is better than calling remove on the list. Similaryly, s.find is better than find on string, etc.
45) Distinguish among count, find, binary_search, lower_bound, upper_bound, and equal_range.
Faster is better. If your container is sorted, use binary_search, lower_bound, upper_bound, equal_range. If not sorted you will have to use count, count_if, find_if.
46) Consider function objects instead of functions as algorithm parameters.
The higher the abstraction, the better the code. Compiler will often inline the operator() function anyway. A lot of the C++ overhead is absorbed during compilation time.
47) Avoid producing write-only code.
The code should be meaningful to compiler and to humans. Knuth would put the human before the compiler.
48) Always #include the proper headers.
vector may include string automatically or not, do not rely on it as it changes between implementations.
49) Learn to decipher STL-related compiler diagnostics.
This should be #1 in the tip list, but better late than never. Have a look at "An STL Error Message Decryptor for Visual C++" by Zolman.
50) Familiarise yourself with STL-related web sites.
http://www.sgi.com/tech/stl, http://www.stlport.org/, http:///www.boost.org/. STLport has a good debug mode which uses objects instead of pointers and can uncover lots of problems. Boost has smart pointers and shared pointers both worth looking at.