Effective STL Skill

Containers

Item 1: Choose your containers with care

• Contiguous memory (vector, deque, string): fast random access, slow middle insert/delete, iterators invalidated on insert
• Node-based (list, map, set): stable iterators and references, better transactional semantics, slow random access
• sorted vector can outperform map/set for lookup-heavy workloads with infrequent inserts (see Item 23)

Item 2: Beware container-independent code

The STL containers are NOT interchangeable. Writing code that works with any container is almost always a mistake — each container has different iterator categories, member functions, and invalidation rules. Use typedefs to make container type changes easier:

typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;

Item 3: Make copying cheap and correct for container objects

Containers copy objects on insert, erase, and reorder. If copy is expensive, consider containers of pointers or smart pointers.

Item 4: empty() instead of size() == 0

list::size() is O(n) in some implementations. empty() is always O(1).

Item 5: Prefer range member functions to single-element loops

// Prefer this:
v.assign(data, data + numValues);        // range assign
v.insert(v.end(), data, data + n);       // range insert

// Over this:
for (int i = 0; i < n; ++i) v.push_back(data[i]); // single-element loop

Range member functions are often faster and always clearer.

Item 6: C++‘s most vexing parse

// Intends to create a list<int> initialized with istream_iterator:
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());
// Actually declares a FUNCTION. Fix:
istream_iterator<int> begin(dataFile), end;
list<int> data(begin, end);

Item 7: Delete pointers before destroying a pointer container

// Don't do this — leaks memory:
vector<Widget*> vwp;
// fill vwp...
vwp.clear(); // doesn't delete the pointed-to Widgets!

// Do this:
for_each(vwp.begin(), vwp.end(), DeleteObject<Widget>());
// Or use a container of smart pointers (boost::shared_ptr, C++11 shared_ptr)

Item 8: Never create containers of auto_ptr

Copying an auto_ptr transfers ownership — sort, copy, and other algorithms will silently null out elements. Use shared_ptr instead.

Item 9: Choose among erasing options carefully

// Erase all elements with a specific value:
c.erase(remove(c.begin(), c.end(), value), c.end()); // sequence containers
c.erase(value);                                        // associative containers

// Erase elements satisfying a predicate:
c.erase(remove_if(c.begin(), c.end(), pred), c.end()); // vector/deque/string
c.remove_if(pred);                                      // list (member function)
// For associative containers, loop manually

Item 12: STL container thread safety

The standard guarantees:

• Multiple concurrent reads are safe
• Multiple concurrent writes to different containers are safe
• Concurrent reads + writes to the same container require external locking

---

vector and string

Item 13: Prefer vector and string to raw arrays

They manage memory, support STL algorithms, and have size().

Item 14: Use reserve to avoid reallocations

vector<int> v;
v.reserve(1000);  // allocate once, avoid O(n) reallocations

Item 17: Swap trick to trim excess capacity

vector<int>(v).swap(v);  // copy-construct to exact size, swap
string("").swap(s);       // release all memory

Item 18: Avoid vector<bool>

vector<bool> doesn’t store actual bool objects — it’s a space-optimized bitset. operator[] returns a proxy, not a reference. Use deque<bool> or bitset instead.

---

Associative Containers

Item 19: Equality vs. equivalence

• Equality (==): used by find on sequence containers
• Equivalence (!comp(a,b) && !comp(b,a)): used by associative containers for ordering These can differ for custom comparators.

Item 21: Comparison functions must return false for equal values

// WRONG: strict weak ordering violated
bool badComp(int x, int y) { return x <= y; }  // returns true for equal elements

// RIGHT:
bool goodComp(int x, int y) { return x < y; }

Violating strict weak ordering causes undefined behavior.

Item 22: Avoid in-place key modification in set/multiset

The key determines position in the tree. Modifying it without erasing+reinserting corrupts the data structure.

Item 23: Replace associative containers with sorted vectors for lookup-heavy workloads

// Sorted vector: lookup-then-batch-insert pattern
vector<pair<string,int>> lookup;
// ... fill lookup, then:
sort(lookup.begin(), lookup.end());
// Lookup: binary_search / lower_bound / upper_bound

// Better cache locality than map; use when:
// - Inserts happen in batches, not interleaved with lookups
// - Memory usage matters

Item 24: map::operator[] vs map::insert

• operator[]: default-constructs value, then assigns — bad for insert
• insert: constructs in-place — preferred for new keys

m.insert(make_pair(k, v));       // efficient insert
m[k] = v;                        // default-constructs then assigns

---

Algorithms

Item 30: Make sure destination ranges are large enough

// WRONG: undefined behavior — no space in result
transform(v1.begin(), v1.end(), result.begin(), op);  // result must be pre-sized!

// RIGHT:
result.resize(v1.size());
// Or use back_inserter:
transform(v1.begin(), v1.end(), back_inserter(result), op);

Item 31: Sorting options

sort           // unstable, O(n log n), fastest
stable_sort    // stable, O(n log² n)
partial_sort   // sort first k elements, O(n log k)
nth_element    // k-th element + partition, O(n) average — for medians/percentiles
partition      // group satisfying vs not, O(n)
stable_partition

Use nth_element for medians and percentile calculations.

Item 32: Follow remove with erase

// remove doesn't change container size — it returns new logical end
v.erase(remove(v.begin(), v.end(), val), v.end());  // erase-remove idiom

Item 34: Algorithms that require sorted ranges

These algorithms only work correctly on sorted ranges: binary_search, lower_bound, upper_bound, equal_range, set_union, set_intersection, set_difference, merge, includes

Item 45: Choosing the right search algorithm

Use case	Algorithm
Unsorted, exact match?	find / find_if
Sorted, exact exists?	binary_search (returns bool)
Sorted, first not less?	lower_bound (returns iterator)
Sorted, count + bounds?	equal_range
Sorted associative container?	Member functions find(), count(), lower_bound() — faster than generic algorithms

---

Functors

Item 38: Design functor classes for pass-by-value

STL algorithms copy functors by value. Functors must be copyable. Don’t store large state in them; use a pointer or shared_ptr to heap-allocated state.

Item 39: Make predicates pure functions

A predicate must not modify state between calls. Some algorithms (like remove_if) may call a predicate multiple times on the same element.

Item 40: Make functor classes adaptable

Inherit from unary_function<Arg, Result> or binary_function<Arg1, Arg2, Result> to expose argument_type and result_type — required for bind1st, bind2nd, and not1/not2.

Item 46: Function objects over functions as algorithm parameters

Function objects (including lambdas) are inlined by the compiler; function pointers are not. Prefer:

sort(v.begin(), v.end(), greater<int>());  // inlined comparator

---

Programming with the STL

Item 43: Prefer algorithm calls to hand-written loops

• Algorithms are efficient (often superior to hand-written loops)
• Algorithms communicate intent clearly
• Algorithms are less error-prone

Item 44: Prefer member functions to algorithms with same names

map::find is O(log n); std::find on a map is O(n). Always use the member function when it exists: find, count, lower_bound, upper_bound, equal_range.

Item 47: Avoid write-only code

// Hard to read (write-only):
v.erase(remove_if(v.begin(), v.end(), bind2nd(greater<int>(), 10)), v.end());

// Better: name the predicate
auto tooLarge = [](int x) { return x > 10; };
v.erase(remove_if(v.begin(), v.end(), tooLarge), v.end());