Real Power of STL Revealed - Part III

Binders and Function Adapters

As have been said before, some STL algorithms require unary function objects (with one argument), other binary function objects (with two arguments). One example is STL transform. First version takes one input iterator range and assigns result returned by unary function object to corresponding output iterator; second works similar way but uses two input iterator ranges and binary function object. Obviously, function object's argument(s) is assigned a value pointed by the input iterator(s).

Let's declare two containers with 5 items and fill them with "6" and random values respectively.

vector<long> v1(5, 6);
deque<long> dq(5);
dq[0] = 22, dq[1] = 4, dq[2] = -100, dq[3] = 0, dq[4] = -7;
cout << "vector with initial values: ";
copy(v1.begin(), v1.end(), ostream_iterator<long>(cout, " "));
cout << endl;
cout << "deque with initial values: ";
copy(dq.begin(), dq.end(), ostream_iterator<long>(cout, " "));
cout << endl << endl;

Here is the result:

vector with initial values: 6 6 6 6 6
deque with initial values: 22 4 -100 0 -7

Now let's take both containers, add corresponding items to each other, and put result back into the vector. Note: we will not print content of deque because it will remain the same.

transform(v1.begin(), v1.end(), dq.begin(), v1.begin(), plus<long>());

STL transform() sample with two input iterator ranges and binary predicate 'plus':
28 10 -94 6 -1

How to use transform() with unary predicate is shown below.

transform(v1.begin(), v1.end(), v1.begin(), negate<long>());

STL transform() sample with one input iterator range and unary predicate 'negate':
-28 -10 94 -6 1

Now suppose we need to add "7" to each item of vector with transform() which takes only one input iterator range (obviously it is just stupid to create second vector filled with "7" to do this simple task). Unfortunately, STL plus is a binary predicate and cannot be used direct way with this version of transform. However, we can use so called binder to bind certain value to second argument of binary predicate.

long valueToBind = 7;
transform(v1.begin(), v1.end(), v1.begin(), bind2nd(plus<long>(), valueToBind));

STL transform() sample with one input iterator range and binary predicate 'plus' with binder:
-21 -3 101 1 8

By the way, we can use bind1st() to bind desired value to the first argument of binary predicate.

Resume: binders are necessary to allow binary function objects to be used with algorithms which require unary function objects and vice versa.

Function adapter ptr_fun takes a pointer to unary (or binary) function and turns it into unary (or binary) function object. Let's assume we have vector<char *> which needs to be modified and sorted with STL algorithms. It is impossible to use for example STL sort() directly because pointers to strings will be sorted instead of strings themselves. So, first, we need extra auxiliary functions on the basis of standard C routine strcmp(). This is because strcmp() returns negative, zero, or positive integer, not bool, what is required for us.

Inline bool my_strcmp_equal(const char *c1, const char *c2)
/* Returns true if first string is equal to second one. */
{ return (strcmp(c1, c2) == 0); };

inline bool my_strcmp_less(const char *c1, const char *c2)
/* Returns true if first string is less than second one. */
{ return (strcmp(c1, c2) < 0); };

Now we are ready to start.

char c1[] = "Andrew", c2[] = "Serge ", c3[] = "Joanne";

vector<char *> vc;
vc.push_back(c1), vc.push_back(c2), vc.push_back(c3);

Original content: Andrew Serge Joanne

Suppose we need to replace "Andrew" with "Andre" by French manner.

replace_if(vc.begin(), vc.end(), bind2nd(ptr_fun(my_strcmp_equal), c1), "Andre ");

STL replace_if() with function adapter 'ptr_fun' and binder test:
Andrea Serge Joanne

STL sort() can be used the same way to sort items in ascending and descending order.

random_shuffle(vc.begin(), vc.end());

sort(vc.begin(), vc.end(), ptr_fun(my_strcmp_less));

STL sort() with function adapter 'ptr_fun' test:
Andre Joanne Serge

sort(vc.begin(), vc.end(), not2(ptr_fun(my_strcmp_less)));

STL sort() with function adapter 'ptr_fun' and negator 'not2' test:
Serge Joanne Andrea

Pay attention to the so called negator "not2". Negators "not1" and "not2" return (! func_obj()) of unary and binary function objects respectively.

You can view or download source code, as well as output in text format.

Q. Why we need unary/binary predicates and function adaptors when we have operators like "+", "-", "*" already defined?
A. STL algorithms require function objects. Operators are not function objects.

Q. Does usage of function objects cause slowdown of generated codes?
A. Usually not, because they are inlined.

Q. I would like to take a look at sources of standard STL predicates in order to understand what and how is going on.
A. No problem. They are Copyright (c) 1994 by Hewlett-Packard Company.

template <class T>
struct plus: binary_function<T, T, T>

T operator()(const T& x, const T& y) const { return x + y; };

template <class T>
struct negate: unary_function<T, T>

T operator()(const T& x) const { return -x; };

template <class T>
struct equal_to: binary_function<T, T, bool>

bool operator()(const T& x, const T& y) const { return x == y; };


Memory Allocation

Any library could be hardly to called portable if it depends on certain memory model. For example, DOS applications may use various memory models. For MacOS with uniform memory model it is just not an issue. With STL, developers can incorporate its own Allocator class which abstracts library from all low-level memory related details. By default, STL provides its own default allocator class which is used if no other Allocator classes have been specified. You can refer to STL reference in order to learn how to write your own Allocator class. However, this is not needed in most cases.

Quick STL container overview

Sequence Containers
  vector deque (double ended queue) list
Random access Yes Yes No
Sequential access Yes Yes Yes (bi-directional)
Insert/Erase Time
At the beginning Linear Constant Constant
In the middle Linear Linear Constant
At the end Amortized constant Constant Constant
Iterator invalidation
Insert 1) All, if reallocation needed; 2) Only after insertion point, if no reallocation All None
Erase All after erase point 1) In the middle - all; 2) At the beginning or end - only to erased item Only to erased item(s)


  1. It is guaranteed that no reallocation happen during insertion into a vector after call of reserve() until size of vector reaches capacity specified by reserve().
  2. In fact, invalidation of all vector iterators after reallocation is the worst case scenario - in this case vector allocates new, larger storage buffer and copies content to it. Under certain circumstances storage buffer could be just resized. However, the worst case scenario must always be assumed as default.
  3. Inserting multiple items into a vector with single call of insert() is faster than multiple calls of insert().


Sorted Associative Containers
  set multiset map multimap
Keys Unique Multiple Unique Multiple
Insert Logarithmic
Find Logarithmic
Count keys log(size()) + count(keys)
Erase key log(size()) + count(keys)
Erase item Amortized constant
Iterator invalidation
Erase Only to erased item
Insert None

Hashed Associative Containers (not a part of C++ Standard Library yet)
  hash_set hash_multiset hash_map hash_multimap
Keys Unique Multiple Unique Multiple
Insert Constant
Find Constant
Count keys Linear
Erase key Linear
Erase item Constant
Iterator invalidation
Erase Only to erased item
Insert None. However, resizing (increasing number of hash buckets) does not necessarily preserve the ordering relation between iterators.

Character Sequnce Containers (basic_string, string, wstring)
Insert, Erase Not specified, but similar to vector
Iterator invalidation
  1) By member functions that explicitly change the string's contents; 2) In the worst case (depends on realization), by any non-const member function, including the non-const version of begin() and subscription operator []. However, the worst case scenario must always be assumed as default.


PS. Now, after review of even very small fraction of STL features, you can understand, how powerful STL is. Just consider, how much time and effort from your side might be required if you have to design all above algorithms from scratch.

Continued - Useful STL Sample: Dynamic Array of Generic Strings...

MacGuruHQ and MacGuruHQ Logo

Copyright© 1996 - 2002 by Andrei Verovski. All right reserved. Content may not be copied in whole or in part, through electronic or other means, without the author's permission. MacGuru Logo (blue penguin) by Sergey Orehov.