[C/C++] - Tips for STL and Generic Programming

Tip 15: The Location of Template Definitions

Normally, you declare functions and classes in a .h file and place their definition in a separate .cpp file. With templates, this practice isn't really useful because the compiler must see the actual definition (i.e., the body) of a template, not just its declaration, when it instantiates a template. Therefore, it's best to place both the template's declaration and definition in the same .h file. This is why all STL header files contain template definitions.

In the future, when compilers support the "export" keyword, it will be possible to use only the template's declaration and leave the definition in a separate source file.

Tip 16: Standard Base Classes for Function Object

To simplify the process of writing function objects, the Standard Library provides two class templates that serve as base classes of user-defined function objects: std::unary_function and std::binary_function. Both are declared in the header “functional”. As the names suggest, unary_function serves as a base class of function objects taking one argument and binary_function serves as a base class of function objects taking two arguments. The definitions of these base classes are as follows:

template < class Arg, class Res > struct

unary_function

{

typedef Arg argument_type;

typedef Res result_type;

};

template < class Arg, class Arg2, class Res >

struct binary_function

{

typedef Arg first_argument_type;

typedef Arg2 second_argument_type;

typedef Res result_type;

};

These templates don't provide any useful functionality. They merely ensure that arguments and return values of their derived function objects have uniform names. In the following example, the predicate is_vowel, which takes one argument, inherits from unary_function:

template < class T >

class is_vowel: public unary_function< T, bool >

{

public:

bool operator ()(T t) const

{

if ((t=='a')||(t=='e')||(t=='i')||(t=='o')||(t=='u'))

return true;

return false;

}

};

Tip 17: Storing Dynamically Allocated Objects in STL Containers

Suppose you need to store objects of different types in the same container. Usually, you do this by storing pointers to dynamically allocated objects. However, instead of using named pointers, insert the elements to the container as follows:

class Base {};

class Derived : public Base{};

std::vector < Base* > v;

v.push_back(new Derived);

v.push_back(new Base);

This way you ensure that the stored objects can only be accessed through their container. Remember to delete the allocated objects as follows:

delete v[0];

delete v[1];

Tip 18: Treating a Vector as an Array

Suppose you have a vector of int and function that takes int *. To obtain the address of the internal array of the vector v and pass it to the function, use the expressions &v[0] or &*v.front(). For example:

void func(const int arr[], size_t length );

int main()

{

vector <int> vi;

//.. fill vi

func(&vi[0], vi.size());

}

It's safe to use &vi[0] and &*v.front() as the internal array's address as long as you adhere to the following rules: First, func() shouldn't access out-of-range array elements. Second, the elements inside the vector must be contiguous. Although the C++ Standard doesn't guarantee that yet, I'm not aware of any implementation that doesn't use contiguous memory for vectors. Furthermore, this loophole in the C++ Standard will be fixed soon.

Tip 19: Dynamic Multidimensional Arrays and Vectors

You can allocate multidimensional arrays manually, as in:

int (*ppi) [5]=new int[4][5]; /*parentheses required*/

/*fill array..*/

ppi[0][0] = 65;

ppi[0][1] = 66;

ppi[0][2] = 67;

//..

delete [] ppi;

However, this style is tedious and error prone. You must parenthesize ppi to ensure that the compiler parses the declaration correctly, and you must delete the allocated memory. Worse yet, you can easily bump into buffer overflows. Using a vector of vectors to simulate a multidimensional array is a significantly superior alternative:

#include <vector>

#include <iostream>

using namespace std;

int main()

{

vector <vector<int> > v; /*two dimensions*/

v.push_back(vector <int>()); /*create v[0]*/

v.push_back(vector <int>()); /*create v[1]*/

v[0].push_back(15); /*assign v[0][0]*/

v[1].push_back(16); /*assign v[1][0]*/

}

Because vector overloads operator [], you can use the [][] notation as if you were using a built-in two-dimensional array:

cout << v[0][0]

cout << v[1][1] style="">

The main advantages of using a vector of vectors are two: vector automatically allocates memory as needed. Secondly, it takes care of deallocating memory so you don't have to worry about potential memory leaks.

Tip 20: Why You Shouldn't Store auto_ptr Objects in STL Containers

The C++ Standard says that an STL element must be "copy-constructible" and "assignable." These fancy terms basically mean that for a given class, assigning and copying one object to another are well-behaved operations. In particular, the state of the original object isn't changed when you copy it to the target object.

This is not the case with auto_ptr, though: copying or assigning one auto_ptr to another makes changes to the original in addition to the expected changes in the copy. To be more specific, the original object transfers ownership of the pointer to the target, thus making the pointer in the original null. Imagine what would happen if you did something like this:

std::vector <auto_ptr<Foo> > vf;/*a vector of auto_ptr's*/

// ..fill vf

int g()

{

std::auto_ptr <Foo> temp=vf[0]; /*vf[0] becomes null*/

}

When temp is initialized, the pointer of vf[0] becomes null. Any attempt to use that element will cause a runtime crash. This situation is likely to occur whenever you copy an element from the container. Remember that even if your code doesn't perform any explicit copy or assignment operations, many algorithms (std::swap(), std::random_shuffle() etc.) create a temporary copy of one or more container elements. Furthermore, certain member functions of the container create a temporary copy of one or more elements, thereby nullifying them. Any subsequent attempt to the container elements is therefore undefined.

Visual C++ users often say that they have never encountered any problems with using auto_ptr in STL containers. This is because the auto_ptr implementation of Visual C++ (all versions thereof) is outdated and relies on an obsolete specification. When the vendor decides to catch up with the current ANSI/ISO C++ Standard and change its Standard Library accordingly, code that uses auto_ptr in STL containers will manifest serious malfunctions.

To conclude, you shouldn't use auto_ptr in STL containers. Use either bare pointers or other smart pointer classes instead of auto_ptr (such classes are available at www.Boost.org).