Tip 14: Useful STL Terminology

Here are some key terms that you may find useful when reading Standard Template Library (STL) literature and documentation.

Container
A container is an object that stores objects as its elements. Normally, it's implemented as a class template that has member functions for traversing, storing and removing elements. Examples of container classes are std::list and std::vector.

Genericity
The quality of being generic, or type-independent. The above definition of the term container is too loose because it may apply to strings, arrays and structs, which also store objects. However, a real container isn't limited to a specific data type or a set of types. Rather, it can store any built-in and user-defined type. Such a container is said to be generic. Note that a string can only contain characters. Genericity is perhaps the most important characteristic of STL. The third tip presents the standard base classes for function objects. Since function objects are one of the constituents of generic programming, adhering to standard conventions in their design and implementation will save you a lot of difficulties.

Algorithm
A set of operations applied to a sequence of objects. Examples of algorithms are std::sort(), std::copy(), and std::remove(). STL algorithms are implemented as function templates taking iterators.

Adaptor
An adaptor is a special object that can be plugged to an exiting class or function to change its behavior. For example, by plugging a special adaptor to the std::sort() algorithm, you can control whether the sorting order is descending or ascending. STL defines several kinds of sequence adaptors, which transform a container to a different container with a more restricted interface. A stack, for instance, is often formed from queue<> and an adaptor that provides the necessary push() and pop() operations.

Big Oh Notation
A special notation used in performance measurements of algorithms. The STL specification imposes minimum performance limits on the operations of its algorithms and container operations. An implementation may offer better performance but not worse. The Big Oh notation enables you to evaluate the efficiency of algorithms and containers for a given operation and data structure. An algorithm such as std::find(), which traverses every element is a sequence (in the worst case scenario) has the following notation:

T(n) = O(n). /* linear complexity */

Iterator
An iterator is an object that functions as a generic pointer. Iterators are used for traversing, adding and removing container elements. STL defines five major categories of iterators:

input iterators and output iterators
forward iterators
bidirectional iterators
random access iterators

Note that this list doesn't represent inheritance relationships; it merely describes the iterator categories and their interfaces. Each lower category is a superset of the category above it. For instance, a bidirectional iterator provides all the functionality of a forward iterators plus additional functionality. Here is a brief summary of the functionality and interfaces for these categories:

Input iterators allow an algorithm to advance the iterator and offer read-only access to an element.

Output iterators allow an algorithm to advance the iterator and offer write-only access to an element.

Forward iterators support both read and write access, but traversal is permitted only in one direction.

Bidirectional iterators allow the user to traverse the sequence in both directions.

Random access iterators support random jumps and "pointer arithmetic" operations, for example:

string::iterator it = s.begin();
char c = *(it+5); /* assign sixth char to c*/

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][0]; 

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