Mumit's STL Newbie guide

• About this document
• General Overview
• What's so special about writing container objects
  • Class constructors
  • Class operators
  • *NEW* How do STL containers and container objects interact?
• Pointers and STL
  • Gotcha's with storing pointers to objects
  • Example of a pointer wrapper for storing in STL containers
  • How do I store derived objects in an STL container?
  • Checking for item in a map
  • More on evils of char*: Phone-book example.
• *NEW* Predicates, Comparators and General Functions
  • Predicates: what and how
  • Comparators: what and how
  • General Functions: what and how
• STL iterators
  • what does iterator::end() return?
  • Const'ness of iterators
  • *NEW* Using iterator tags
• Miscellaneous examples/notes
  • Copy between lists: right way and wrong way
  • Copy between maps
  • Adaptors in STL: not1, stack, queue, etc
  • remove vs erase
  • List of List's in STL
  • Sorting a container
    • Sorting a list of user defined objects
    • Sorting a vector of user defined objects
  • Shuffling a deck of cards
  • Deducing type from iterator
• Persistent STL
• 236 examples from ObjectSpace
• A look at ObjectSpace STL<ToolKit>
• Template instantiation with GCC
  • *NEW Visibility of template definitions
  • Manual instantiation
  • Using GCC 2.7.0 template repository mechanism
• Internet resources available
• Acknowledgments

As always, I welcome thoughtful comments, suggestions, corrections, ale, and offers of help via email at khan@xraylith.wisc.edu.

Copyright(c) 1995 Mumit Khan

I personally use GCC 2.7.0 (combined with Cygnus template repository patch) and ObjectSpace STL<ToolKit>, so please bear this in mind when you see something that doesn't make sense to your configuration. If you are using GCC 2.7.0 with ObjectSpace STL<ToolKit>, then you should get in touch with ObjectSpace for bug fixes (See here for more info).

Here I describe some "general guidelines" (read: this is what I do, your mileage may vary widely) on what constructors and operators one should define when working with STL.

Class constructors

1. default constructor -- X();
2. copy constructor -- X(const X&);

   If you don't have this, STL will use the compiler generated one (ie., member-wise copy), and embedded pointers will result in weird bugs.

See here for an in-depth look at why and when these are needed.

Class operators

1. operator= (const X&)

   Better have this -- same effect as copy constructor.

2. operator< (const X&)

   if your class X is essentially un-ordered, simply return true or false. For example, if you have container full of pointers to some other object, ordering may not make sense either.

3. operator== (const X&)

   if your class X is essentially un-ordered, simply return true or false. For example, if you have container full of pointers to some other object, ordering may not make sense either.

The operators == and < are very important for sorted collections like set, map etc, and are the reason why storing pointers in STL sorted collections may not work as you would expect. See here for some caveats in storing pointers in STL containers. Even though I've shown the 2 operators as member functions here, they don't need be (which is great, since you can use somebody else's class without having to modify it). eg., if there is a library class X that you cannot modify, you can define the operators == and < externally as following:

• bool operator== (const X& x1, const X& x2)
• bool operator< (const X& x1, const X& x2)

Note that you may not need the < and == operators for some compilers if your code doesn't use the algorithms that need these operators (eg., sorting and such things). The compilers I deal with like to instantiate ALL the members when I manually instantiate templates, and so I'm out of luck. GCC 2.7.0 seems to do a much better job of instantiating only the needed members.

See here for an in-depth look at why and when these are needed.

How do STL containers and container objects interact?

    What members do I have to define for an object that will live in
    an STL container?

    void f() {                           //   <------- (1)
        class X { };
        list<X> xlist;                   //   <------- (2)

        //
        // now populate the list with lots of X's.
        //
        X x();
        xlist.push_back(x);             //   <-------- (3)

        //
        // do what-not with xlist 
        //

	// 
	// now replace the 1st element with something else.
	//
	X x2;
	xlist.front() = x2;             //   <-------- (4)

	//
        // remove the element with value x3
	//
	X x3;
	xlist.remove(x3);               //   <-------- (5)

	//
        // now sort the list
	//
	xlist.sort();                   //   <-------- (6)


	//
        // do stuff with xlist and then return from f()
	//

        return;
    }                                   //   <-------- (7)

1. Enter a new scope, function f. Automatic objects will be destructed when we leave this scope in Step (7).

2. Create a concrete list<X> from parameterized type, list<T>. At this point, the constructor for list creates a list_node that has a member data holding a copy of X. The list_node looks like the following:

       template <class T>
       struct list_node {
   	void_pointer next;
   	void_pointer prev;
   	T data;
       };
       

   To create list_node, the data member, T, must have a default constructor (or equivalent, such as a constructor with all default arguments) defined.

   Step (2) requires a default constructor.

3. Here we add an object, x, of type X, to the end of the list. The method push_back would typically invoke the following:

       insert(begin(), x);
       

   And here's the code for a typical insert method:

       iterator insert(iterator position, const T& x) {
           link_type tmp = get_node();                         < ---- (3a)
           construct(value_allocator.address((*tmp).data), x); < ---- (3b)
           (*tmp).next = position.node;
           (*tmp).prev = (*position.node).prev;
           (*(link_type((*position.node).prev))).next = tmp;
           (*position.node).prev = tmp;
           ++length;
           return tmp;
       }
       
       

   Step 3a requires the construction of a data member of type X as in the Step 1, and hence requires a default constructor. Step 2b uses the STL allocator interface to construct the object from argument x using placement new and hence requires a copy constructor. The typical construct looks like the following:

       template <class T1, class T2>
       inline void construct(T1* p, const T2& value) {
   	new (p) T1(value);
       }
   
       

   Step (3) requires a copy constructor (3b) in addition to a default constructor (3a).

4. Here we are replacing the first element of the list with a new object, x2. Here the front method returns a reference (lvalue) to the data member of the first element in the list and it is assigned a new value x2. This operation hence requires the assignement operator (ie., operator=).

   Step (4) requires an assignment operator, ie., operator=(const X& x).

5. Here we want to remove the element, if any, in the list that equals the value x3. The code looks like the following:

       template <class T>
       void list<T>::remove(const T& value) {
   	iterator first = begin();
   	iterator last = end();
   	while (first != last) {
   	    iterator next = first;
   	    ++next;
   	    if (*first == value)        //   <-------- (5a)
   		erase(first);
   	    first = next;
   	}
       }
   
       

   The remove member starts in the beginning of the list and searches till either the end is reached or a value equalling value argument is found; if found, remove removes the element from the list and calls the destructor. Note in Step (6a), we need the equality operator (operator==) defined for this to work.

   Step (5) requires an equality operator, ie., bool operator==(const X& x).

6. Now we sort the list. The sort member use an in-place merge sort algorithm that requires the less-than relation defined for the object (Step 6a below).

       template <class T>
       void list<T>::merge(list<T>& x) {
   	iterator first1 = begin();
   	iterator last1 = end();
   	iterator first2 = x.begin();
   	iterator last2 = x.end();
   	while (first1 != last1 && first2 != last2)
   	    if (*first2 < *first1) {            //   <-------- (6a)
   		iterator next = first2;
   		transfer(first1, first2, ++next);
   		first2 = next;
   	    } else
   		first1++;
   	if (first2 != last2) transfer(last1, first2, last2);
   	length += x.length;
   	x.length= 0;
       }
   
       template <class T>
       void list<T>::sort() {
   	if (size() < 2) return;
   	list<T> carry;
   	list<T> counter[64];
   	int fill = 0;
   	while (!empty()) {
   	    carry.splice(carry.begin(), *this, begin());
   	    int i = 0;
   	    while(i < fill && !counter[i].empty()) {
   		counter[i].merge(carry);
   		carry.swap(counter[i++]);
   	    }
   	    carry.swap(counter[i]);         
   	    if (i == fill) ++fill;
   	} 
   	while(fill--) merge(counter[fill]);
       }
   
       

   Step (6) requires a less-than operator, ie., bool operator<(const X& x).

7. Here the list object goes out of scope and is automatically destructed by the C++ runtime system. The destructor for list in turns calls the destructor for all the elements that are in the list. Hence the object requires a destructor.

   Step (7) requires a destructor

The following are automatically supplied by the compiler if not defined by the user:

• X() -- default constructor, but only when no other constructor is defined
• X(X const&) -- copy constructor
• operator=(X const&) -- assignment operator
• ~X() -- destructor

If X in this example contains pointers, please be sure to define all of these instead of leaving it to the compiler.

The following must be defined explicitly by the user:

• bool operator==(X const&) -- equality operator
• bool operator<(X const&) -- less-than operator

• Large objects that are too expensive to duplicate and are already constructed on the heap.
• Single object stored in multiple containers. This is quite common and I believe the right way to do is to wrap the pointers into a class the manages the objects, perhaps via a reference count.
• When you need to store objects derived from a (or a set of) base objects in a container. This is quite common in CAD systems where most manipulable objects are derived from a common base with a set of common semantics. See here for an example. Remember that C++ != Smalltalk, and true heterogeneous containers are simply too messy to do in C++.

• No pointers to local variables please. See the function change_phno for an example of this.
• Who manages the destruction? See here for an example of templatized sequence destructor.
• Most STL containers use < for comparison which may be meaningless in some contexts. This is where Smart pointers shine.
• Be careful when supplying a Comparator to STL containers need one, such as SET, MAP, etc. See here for a rather involved example. Also see here for another example.

  A better solution is to wrap the pointers in a simple class that you store in STL containers. For a trivial example, see here.

• Some compilers and STL implementations seem to have inordinate amount of trouble when you store pointers to objects instead of objects, and it stems from construct and destroy functions in STL allocator design; eg., HP reference implementation comes with destroy specialized for pointers to all built-in types, so it works fine if you store int* in a container, but not when you store X*, where X is some user-defined data type. See here for Benjamin Scherrey's note on how to manage this.

• Storing pointers in STL containers: Example code
• Deallocating pointers stored in STL containers
• Who owns the storage?
• More gotchas in storing char*

#include <stl.h>                // or individual includes if you like
                                // need list.h, set.h and algo.h
#include <iostream.h>

//
// THIS IS VERY IMPORTANT (see note above). You have to tell the set
// or multiset or map to compare the objects pointed to rather than 
// the pointers these containers are storing.
//
struct compare {
    bool operator() (const int* i1, const int* i2) const {
        return *i1 < *i2;
    }
};

void print(int* i) {
    cout << " " << *i;
}

int main(int, char*[]) {
    list<int*> list1;

    //
    // create a list of new'd integers.
    //
    for(int i = 0; i < 5; ++i) {
        list1.push_back(new int(i * i));
    }

    cout << "List of int*: (";
    for_each(list1.begin(), list1.end(), print);
    cout << ")" << endl;

    //
    // now put these integers into a set. Note that I'm using a
    // custom comparator to compare the integers, not the pointers.
    //
    set<int*, compare> set1;
    copy(list1.begin(), list1.end(), 
        insert_iterator<set<int*, compare> > (set1, set1.begin())
    );

    cout << "Set of int* : [";
    for_each(set1.begin(), set1.end(), print);
    cout << "]" << endl;

    return 0;
}

When you run the program, it should produce the following output.

% ./testc++
List of int*: ( 0 1 4 9 16)
Set of int* : [ 0 1 4 9 16]

Special Note for Borland C++ users: However, Ben Scherrey (scherrey@proteus-tech.com) points out that the OS/2 Borland C++ compiler cannot handle this, and I believe this is due the compiler's lack of support for explicitly calling template destructor. Ben says that the if you overload destroy and construct yourself, it works out. Thanks Ben.

void destroy(X** pointer ) {
    (*pointer)->~X();
}

inline void construct(X** p, const X* value ) {
    new (p) (const X*)(value);
}

   template <class ForwardIterator, class ForwardIterator>
   void sequence_delete(ForwardIterator first, ForwardIterator last) {
       while (first != last)
	   delete *first++;
   }

   template <class ForwardIterator, class ForwardIterator>
   void map_delete(ForwardIterator first, ForwardIterator last) {
       while (first != last)
	   delete (*first++).second;
   }

   Map<int, SomeType*, less<int> > mymap_;
   //
   // populate my map with new'd SomeType's.
   //
   map_delete(mymap_.begin(), mymap_.end());

list<char*> means a list character pointers, NOT strings they point to. less<char*> will compare the pointers, NOT the strings (ie., NOT use strcmp and friends).

   char buf[1024];
   strcpy(buf, "THIS_WOULD_CHANGE_MAGICALLY");
   list<char*> list1;
   list1.push_back(buf);
   ostream_iterator<char*> citer(cout, " ");
   copy(list1.begin(), list1.end(), citer);

   // you should see one string, the one in buf above.

   strcpy(buf, "YIKES!");
   copy(list1.begin(), list1.end(), citer);

   // SURPRISE. your list is changed now.
   

In general, do not use char* as container objects, rather write a simple string class (ask me if you need one) and use that instead.

#include <stl.h>
#include <iostream.h>

int main(int, char*[]) {
    static char* names[] = {"one", "two", "three"};
    set<char*, less<char*> > name_set;
    name_set.insert(names[0]);
    name_set.insert(names[1]);
    name_set.insert(names[2]);

    char buf[256];
    strcpy(buf, "one");
    const char* one = buf;
    set<char*, less<char*> >::const_iterator it = name_set.find(one);
    if (it == name_set.end()) {
        cerr << "No such name `" << one << "' in set!" << endl;
    } else {
        cerr << "Found name `" << one << "' in set." << endl;
    }
    return 0;
}

#include <stl.h>
#include <iostream.h>

//
// Let's say you want to put pointers to X into multiple STL containers.
//
class X {
public:
    X(int i) : i_(i) { ; }
    X(const X& x) : i_(x.i_) { }
    ~X() { }
    X& operator= (const X& x) { i_ = x.i_; }

    int operator()() const { return i_; }
private:
    int i_;
};

bool operator== (const X& x1, const X& x2) {
    return x1() == x2();
}

bool operator< (const X& x1, const X& x2) {
    return x1() < x2();
}

//
// Define a simple wrapper class to put into STL containers. This one
// simple wraps X.
//
class XPtrWrapper {
public:
    XPtrWrapper(X* x = 0) : x_(x) { }
    XPtrWrapper(const XPtrWrapper& xw) : x_(xw.x_) { }
    ~XPtrWrapper() { }
    XPtrWrapper& operator= (const XPtrWrapper& xw) { x_ = xw.x_; }

    const X* operator() () const { return x_; }
    X* operator() () { return x_; }
private:
    X* x_;
};

bool operator== (const XPtrWrapper& xw1, const XPtrWrapper& xw2) {
    return (xw1.operator()() && xw2.operator()()) ? *xw1() == *xw2() : false;
}

bool operator< (const XPtrWrapper& xw1, const XPtrWrapper& xw2) {
    return (xw1() && xw2()) ? *xw1() < *xw2() : false;
}

void print(const XPtrWrapper& xw) {
    cout << " " << (*xw())();
}

int main(int, char*[]) {
    XPtrWrapper bucket[5];
    for(int i = 0; i < 5; ++i) {
        bucket[i] = XPtrWrapper(new X(i * i));
    }
    random_shuffle(bucket, bucket + 5);

    list<XPtrWrapper> list1;
    copy(bucket, bucket + 5, 
        back_insert_iterator<list<XPtrWrapper> > (list1)
    );

    cout << "List of XPtrWrapper: (";
    for_each(list1.begin(), list1.end(), print);
    cout << ")" << endl;

    //
    // now put these XPtrWrappers into a set. Note that I can use
    // greater since I've defined operator> for it.
    //
    set<XPtrWrapper, greater<XPtrWrapper> > set1;
    copy(list1.begin(), list1.end(), 
        insert_iterator<set<XPtrWrapper, greater<XPtrWrapper> > > 
            (set1, set1.begin())
    );

    cout << "Set of XPtrWrapper : [";
    for_each(set1.begin(), set1.end(), print);
    cout << "]" << endl;

    //
    // now put these integers into a deque. 
    //
    deque<XPtrWrapper> deque1;
    copy(list1.begin(), list1.end(), 
        back_insert_iterator<deque<XPtrWrapper> > (deque1)
    );

    cout << "Deque of XPtrWrapper : (";
    for_each(deque1.begin(), deque1.end(), print);
    cout << ")" << endl;

    return 0;
}

And the output is:

List of XPtrWrapper: ( 4 0 16 1 9)
Set of XPtrWrapper : [ 16 9 4 1 0]
Deque of XPtrWrapper : ( 4 0 16 1 9)

1. Store the pointer itself in the container. You have to explicitly deallocate the memory later on of course. Also, not all STL implementations seem to handle storage of pointers uniformly, so I would suggest using a wrapper shown below.
2. Hard-coded wrapper that takes a pointer to the base class
3. Templated pointer wrapper that takes a pointer to the base class

Hard-coded wrapper that takes a pointer to the base class

Note: After the new'd Base derivative is passed to the wrapper, it owns it and deletes it in the destructor.

#include <stl.h>
#include <string.h>
#include <iostream.h>

//
// abstract base class
//
class Base {
public:
    const char* typename() const { return typename_; }
    virtual Base* clone() const = 0;
    virtual void identify(ostream& os) const = 0;
    virtual ~Base();

public:
    static int count;

protected:
    Base(const char* typename);
    Base(const Base& base);

private:
    char* typename_;
};

Base::Base(const char* typename) {
    const char* tname = (typename) ? typename : "unknown";
    strcpy(typename_ = new char[strlen(tname) + 1], tname);
    ++count;
}

Base::Base(const Base& base) {
    strcpy(
        typename_ = new char[strlen(base.typename_) + 1], base.typename_
    );
    ++count;
}

Base::~Base() {
    delete[] typename_;
    --count;
}

//
// First derived class. 
//
class Derived1 : public Base {
public:
    Derived1(int data) : Base("derived1"), data_(data) { }
    Derived1(const Derived1& d) : Base("derived1"), data_(d.data()) { }
    virtual ~Derived1()        { }
    virtual Base* clone() const { return new Derived1(*this); }
    virtual void identify(ostream& os) const;
    int data() const { return data_; }
private:
    int data_;
};

virtual void Derived1::identify(ostream& os) const {
    os << "(" << typename() << " " << data() << ")";
}

//
// Second derived class. 
//
class Derived2 : public Base {
public:
    Derived2(int data) : Base("derived2"), data_(data) { }
    Derived2(const Derived2& d) : Base("derived2"), data_(d.data()) { }
    virtual ~Derived2()        { }
    virtual Base* clone() const { return new Derived2(*this); }
    virtual void identify(ostream& os) const;
    int data() const { return data_; }
private:
    int data_;
};

virtual void Derived2::identify(ostream& os) const {
    os << "(" << typename() << " " << data() << ")";
}

//
// now define the pointer wrapper.
//
class BaseWrapper {
public:
    BaseWrapper(Base* base_ptr = 0) : base_ptr_(base_ptr) { }
    BaseWrapper(const BaseWrapper& bw) {
        base_ptr_ = bw() ? bw()->clone() : 0;
    }
    ~BaseWrapper() { delete base_ptr_; }
    const Base* operator()()  const { return base_ptr_; }
    Base* operator()()  { return base_ptr_; }
    BaseWrapper& operator= (const BaseWrapper& bw) {
        delete base_ptr_;
        base_ptr_ = bw()->clone();
    }
private:
    Base* base_ptr_;
};

bool operator== (const BaseWrapper& bw1, const BaseWrapper& w2) {
    return false;
}

bool operator< (const BaseWrapper& bw1, const BaseWrapper& w2) {
    return false;
}

//
// end of class defs.
//

// define static members.
int Base::count = 0;

int main(int, char*[]) {
    list<BaseWrapper> list1;
    list1.push_back(BaseWrapper(new Derived1(101)));
    list1.push_back(BaseWrapper(new Derived2(201)));
    list1.push_back(BaseWrapper(new Derived2(202)));
    list1.push_back(BaseWrapper(new Derived1(102)));
    list1.push_back(BaseWrapper(new Derived2(203)));

    list<BaseWrapper>::const_iterator it = list1.begin();
    for(; it != list1.end(); ++it) {
        const BaseWrapper& bw = *it;
        bw()->identify(cerr); 
        cerr << " ";
    }
    cerr << endl << endl;

    return 0;
}

(derived1 101) (derived2 201) (derived2 202) (derived1 102) (derived2 203) 

Note: After the new'd Base derivative is passed to the wrapper, it owns it and deletes it in the destructor.

#include <stl.h>
#include <string.h>
#include <iostream.h>

//
// abstract base class
//
class Base {
public:
    const char* typename() const { return typename_; }
    virtual Base* clone() const = 0;
    virtual void identify(ostream& os) const = 0;
    virtual ~Base();

public:
    static int count;

protected:
    Base(const char* typename);
    Base(const Base& base);

private:
    char* typename_;
};

Base::Base(const char* typename) {
    const char* tname = (typename) ? typename : "unknown";
    strcpy(typename_ = new char[strlen(tname) + 1], tname);
    ++count;
}

Base::Base(const Base& base) {
    strcpy(
        typename_ = new char[strlen(base.typename_) + 1], base.typename_
    );
    ++count;
}

Base::~Base() {
    delete[] typename_;
    --count;
}

//
// First derived class. 
//
class Derived1 : public Base {
public:
    Derived1(int data) : Base("derived1"), data_(data) { }
    Derived1(const Derived1& d) : Base("derived1"), data_(d.data()) { }
    virtual ~Derived1()        { }
    virtual Base* clone() const { return new Derived1(*this); }
    virtual void identify(ostream& os) const;
    int data() const { return data_; }
private:
    int data_;
};

virtual void Derived1::identify(ostream& os) const {
    os << "(" << typename() << " " << data() << ")";
}

//
// Second derived class. 
//
class Derived2 : public Base {
public:
    Derived2(int data) : Base("derived2"), data_(data) { }
    Derived2(const Derived2& d) : Base("derived2"), data_(d.data()) { }
    virtual ~Derived2()        { }
    virtual Base* clone() const { return new Derived2(*this); }
    virtual void identify(ostream& os) const;
    int data() const { return data_; }
private:
    int data_;
};

virtual void Derived2::identify(ostream& os) const {
    os << "(" << typename() << " " << data() << ")";
}

//
// now define a templated pointer wrapper. The class must support the
// clone() method.
//
template <class T>
class PtrWrapper {
public:
    PtrWrapper(T* t_ptr = 0) : t_ptr_(t_ptr) { }
    PtrWrapper(const PtrWrapper<T>& w) {
        t_ptr_ = w() ? w()->clone() : 0;
    }
    ~PtrWrapper() { delete t_ptr_; }
    const T* operator()()  const { return t_ptr_; }
    T* operator()()  { return t_ptr_; }
    PtrWrapper<T>& operator= (const PtrWrapper<T>& w) {
        delete t_ptr_;
        t_ptr_ = w()->clone();
        return *this;
    }
private:
    T* t_ptr_;
};

template <class T>
bool operator== (const PtrWrapper<T>& w1, const PtrWrapper<T>& w2) {
    return false;
}

template <class T>
bool operator< (const PtrWrapper<T>& w1, const PtrWrapper<T>& w2) {
    return false;
}

//
// end of class defs.
//

// define static members.
int Base::count = 0;

int main(int, char*[]) {
    list<PtrWrapper<Base> > list1;
    list1.push_back(PtrWrapper<Base> (new Derived1(101)));
    list1.push_back(PtrWrapper<Base> (new Derived2(201)));
    list1.push_back(PtrWrapper<Base> (new Derived2(202)));
    list1.push_back(PtrWrapper<Base> (new Derived1(102)));
    list1.push_back(PtrWrapper<Base> (new Derived2(203)));

    list<PtrWrapper<Base> >::const_iterator it = list1.begin();
    for(; it != list1.end(); ++it) {
        const PtrWrapper<Base>& w = *it;
        w()->identify(cerr); 
        cerr << " ";
    }
    cerr << endl << endl;

    return 0;
}

(derived1 101) (derived2 201) (derived2 202) (derived1 102) (derived2 203) 

    typedef Map<int, X*, less<int> > XMap;
    XMap xmap;
    //
    // populate xmap will what-not.
    //
    const X* xx = xmap[5];
    if (xx == 0) {			// not in map.
	do_something();
    } else {
	do_something_else();
    }

looks pretty innocuous, but what really happens is that a new entry for xmap[5] is created and gets stuffed with a NULL pointer which causes amazing amount of headache 10,000 lines of code later. The right way of course (and documented in the fine manual) is the following:

    typedef Map<int, X*, less<int> > XMap;
    XMap xmap;
    //
    // populate xmap will what-not.
    //
    XMap::const_iterator it = xmap.find(5);
    if (it == xmap.end()) {		// not in map.
	do_something();
    } else {
	do_something_else();
    }

#include <stl.h>
#include <iostream.h>

typedef map<char*, unsigned long, less<char*> > Phonebook;

static void print_phbook(ostream& os, const Phonebook& map_) {
    for(Phonebook::const_iterator i = map_.begin(); i != map_.end(); ++i) {
        os << "\t(" << (*i).first << " " << (*i).second << ") " << endl;
    }
}

static void change_phno(
    Phonebook& phbook, const char* name, unsigned long phno
) {
    char buf[1024];
    strcpy(buf, name);
    phbook[(char*)buf] = phno;
};

int main(int, char*[]) {
    Phonebook phbook;

    phbook[(char*)"grumpy"] = 5551212;
    phbook[(char*)"sleepy"] = 5552121;
    phbook[(char*)"gandhi"] = 5554242;

    cerr << "==> Initial phone book" << endl;
    print_phbook(cerr, phbook);
    cerr << endl;

    change_phno(phbook, "grumpy", 9995152);

    cerr << "==> Grumpy moved. The new number is 9995152" << endl;
    print_phbook(cerr, phbook);
    cerr << endl;

    char buf[1024];
    strcpy(buf, "grumpy");
    phbook[(char*)buf] = 7621212;

    cerr << "==> Grumpy moved again! latest number 7621212" << endl;
    print_phbook(cerr, phbook);
    cerr << endl;

    return 0;
}

And here's the output (might even dump core with some STL implementations):

==> Initial phone book
	(grumpy 5551212) 
	(sleepy 5552121) 
	(gandhi 5554242) 

==> Grumpy moved. The new number is 9995152
	(grumpy 5551212) 
	(sleepy 5552121) 
	(gandhi 5554242) 
	( 9995152) 

==> Grumpy moved again! latest number 7621212
	(grumpy 5551212) 
	(sleepy 5552121) 
	(gandhi 5554242) 
	( 9995152) 
	(grumpy 7621212) 

1. Predicates: boolean function. Especially useful for algorithms that end in _if, such as count_if, find_if, replace_if, etc.
2. Comparator: boolean function. Useful for ordered containers, such as map<T>, priority_queue<T>, etc.
3. General functions: functions that operate on objects, but do not necessarily return a value, and if they do, it could be anything.

Predicates: what and how

     First off. thank you for maintaining such a useful page on STL. It has 
     filled the documentation gap for me twice when I could'nt figure out 
     the Modena manual !

     A question that I cannot get a handle on yet is how to search for 
     element in a list without passing the full element in..

     Example: If I have a list or vector of regions which contain a pointer 
     to a buffer.

     vector<Region>

     and Region has a method for determining whether or not it contains a 
     specific pointer in memory. 
     
     bool Region::Contains(Byte* Bfr)
     
     What I thought I should be able to do is use 
     
     Region = find(List.begin(), List.end(), Byte* BfrToBeSearchedFor);
     
     or something like it.
     
     But STL (in my probably limited understanding) seems to require that I 
     use 
     
     Region = find(List.begin(), List.end(), RegionToBeSearchedFor);
     
     or 
     
     Region = find(List.begin(), List.end(), ComparisonFunction);
     
     Neither of which appears to answer my needs.
     
     If you have any suggestions on how this would be tackled please put 
     them in your Newbie guide. If not I will try posting to comp.lang.c++.
     Thank you again.
     
     Jim Jackl-Mochel

The first thing to note is that the appropriate algorithm to use is find_if, not find; now, we also need to supply a predicate (has_buffer shown below) that will do the right thing. The following solution works in this case:

    class Region {
    public:
	// ...
	bool Contains(Byte* Bfr) const;
    private:
	// ...
    };

    list<Region> regions;
    //
    // populate regions with all the Region objects containing unique
    // Byte* elements, one of which may contain the Byte* you're looking
    // for.
    //

    Byte* BfrToBeSearchedFor = INITIALIZE_BUFFER_POINTER;

    //
    // find the region which contains the given buffer pointer bufferp;
    //
    // first, let's define the appropriate comparator fct.
    //

    struct has_buffer {
	Byte* buffer_;
	has_buffer(const Byte* buffer) : buffer_(buffer) { }
	bool operator()(const Region& region) const {
	    return region.Contains(buffer_);
	}
    };

    list<Region>::const_iterator it = find_if(regions.begin(), 
	regions.end(), has_buffer(BfrToBeSearchedFor)
    );

    if (it == regions.end()) {
	// not found
    } else {
	// found it
	const Byte* Bfr = *it;
	// ...
    }

Comparators: what and how

    
    deque<int*> deque1;
    //
    // populate deque1
    //

    //
    // now sort. (THIS IS INCORRECT)
    //
    sort(deque1.begin(), dequeu1.end());

The following example shows how to do a custom pointer comparator.

    bool intp_less(const int* i1, const int* i2) {
	return *i1 < *i2;
    }

    sort(deque1.begin(), dequeu1.end(), intp_less);

    template <class BinaryFunction>
    class binary_dereference : binary_function<
	BinaryFunction::first_argument_type,
	BinaryFunction::second_argument_type, 
	BinaryFunction::result_type> 
    {
    public:
	binary_dereference(
	    const BinaryFunction& func = BinaryFunction()
	) : func_(func) { }
	BinaryFunction::result_type operator() (
	    BinaryFunction::first_argument_type* const& x,
	    BinaryFunction::second_argument_type* const& y
	) const {
	    return func_(*x, *y);
	}
    protected:
	BinaryFunction func_;
    };

    template <class BinaryFunction>
    inline binary_dereference<BinaryFunction>
    dereference2 (const BinaryFunction& func) 
    {
	return binary_dereference<BinaryFunction>(func);
    }

    //
    // populate deque<int*>
    //

    deque<int*> deque1;

    //
    // now we sort ...
    //
    sort(
	deque1.begin(), deque1.end(), 
	binary_dereference<less<int> > (less<int>())
    );

    //
    // or use the adapter
    //
    sort(
	deque1.begin(), deque1.end(), 
	dereference2 (less<int> ())
    );

    typedef binary_dereference<less<int> > ip_compare;
    typedef set<int*, ip_compare> ip_set;

    template <class BinaryFunction, class Modifier>
    class binary_arg_modifier : binary_function<
	Modifier::argument_type,
	Modifier::argument_type,
	BinaryFunction::result_type> 
    {
    public:
	binary_arg_modifier(
	    const BinaryFunction& func = BinaryFunction(),
	    const Modifier& modifier = Modifier()
	) : func_(func), modifier_(modifier) { }
	BinaryFunction::result_type operator() (
	    const Modifier::argument_type& x,
	    const Modifier::argument_type& y
	) const {
	    return func_(modifier_(x), modifier_(y));
	}
    protected:
	BinaryFunction func_;
	Modifier modifier_;
    };

    template <class BinaryFunction, class Modifier>
    inline binary_arg_modifier<BinaryFunction, Modifier>
    arg_modifier2 (const BinaryFunction& func, const Modifier& modifier) 
    {
	return binary_arg_modifier<BinaryFunction, Modifier>(func, modifier);
    }


    template <class T>
    struct dereference : unary_function<T*, T> {
	T operator() (const T* x) const { return *x; }
    };


    //
    // populate deque<int*>
    //

    deque<int*> deque1;

    //
    // now we sort ...
    //

    sort(
	deque1.begin(), deque1.end(), 
	binary_arg_modifier< less<int>, dereference<int>  > ()
    );

    //
    // or use the adapter
    //
    sort(
	deque1.begin(), deque1.end(), 
	arg_modifier2 (less<int> (), dereference<int> ())
    );

    typedef binary_arg_modifier< less<int>, dereference<int> > ip_compare;
    typedef set<int*, ip_compare> ip_set;
    
    ip_set set1;

    
    class Appointment {
    public:
	//
	// define all the usual members ...
	//

	bool today(Date const& date) const;
    private:
	//
	// private stuff here.
	//
    };

    typedef list<Appointment> Appointments;
    Appointments appt_book;

    //
    // define a general function 
    //
    void print_todays_appt(Appointment& const appt) {
	if (appt.today(date))
	    print_appt(appt);
    }

    
    //
    // and here's how it's used.
    //

    for_each(appt_book.begin(), appt_book.end(), print_todays_appt);

Another common scenario is when you would like to modify each of the container elements within a given range; eg., let's say you would like to negate all the elements of the list. The following code shows how:

    
    //
    // define an appropriate algorithm that will modify the element
    // in place calling the supplied function object.
    //
    template <class OutputIterator, class UnaryOperation>
    void modify_element(OutputIterator first, OutputIterator last,
			     UnaryOperation op) {
	while (first != last) {
	    *first = op(*first);
	    ++first;
	}
    }
    
    list<int> list1;
    //
    // populate list1 with what-not.
    //

    modify_element(list1.begin(), list1.end(), negate<int>());

Predicates, Comparators and General Functions
Back to index

Why point beyond the end of the container? Why not point at the last item? The reason is quite simple: Remember that STL containers emulate (or try to as faithfully as possible) C pointer semantic and end() returns the equivalent of C 0 pointer.

Consider how else you would do the following if end() instead returned the last item in the container.

	MyMap::const_iterator it = my_map.find(key);
	if (it == my_map.end())
	    no_such_key();
	else
	    found_key();

or,

	bool empty(const STL_Container& container) {
	    return container.begin() == container.end();
	}

• STL_Container::begin() returns the first item in the container if it exists or end() otherwise.
• STL_Container::end() returns one-past the end of the container.

#include <stl.h>

void foo(const list<int>& list1) {
    list<int>::iterator it = list1.begin();
    for(; it != list1.end(); ++it) {
        ;
    }
}

and here's the error message from GNU C++ 2.6.3:

g++ -g -I/usr/local/ospace -I/usr/local/ospace/include  -c const_iterator.cc -o const_iterator.o
const_iterator.cc: In function `void foo(const class list<int> &)':
const_iterator.cc:5: no matching function for call to `list_iterator<int>::list_iterator<int> (list_const_iterator<int>)'
/usr/local/ospace/ospace/stl/list.h:5: candidates are: list_iterator<int>::list_iterator(const list_iterator<int> &)
/usr/local/ospace/ospace/stl/list.h:79:                 list_iterator<int>::list_iterator()
/usr/local/ospace/ospace/stl/list.h:131:                 list_iterator<int>::list_iterator(os_list_node<int> *)
const_iterator.cc:5: in base initialization for class `list_iterator<int>'
const_iterator.cc:6: no conversion from `list_iterator<int>' and `list_const_iterator<int>' to types with default `operator !=' 
gmake: *** [const_iterator.o] Error 1

Of course the correct way is to use list<int>::const_iterator instead as shown here:

#include <stl.h>

void foo(const list<int>& list1) {
    list<int>::const_iterator it = list1.begin();
    for(; it != list1.end(); ++it) {
        ;
    }
}

//
// slightly modified STL standard sort() algorithm to not exclude 
// containers that do not support Random Access Iterators. Uses the 
// same interface as HP reference sort(first, last) interface.
//
// This code used with libg++ STL tweaks the infamous "template 
// unification failed" problem in all version of, so caveat emptore. 
// OS STL<ToolKit> works around this gcc problem.
//
// Mumit Khan <khan@xraylith.wisc.edu>
// 
//
#include <stl.h>

template <class RandomAccessIterator, class T>
inline void __generalized_sort (
    RandomAccessIterator first, 
    RandomAccessIterator last,
    random_access_iterator_tag,
    T*
) {
    sort(first, last);
}

//
// highly inefficient, but proves the point.
//
template <class BidirectionalIterator, class T>
inline void __generalized_sort (
    BidirectionalIterator first, 
    BidirectionalIterator last,
    bidirectional_iterator_tag,
    T*
) {
    deque<T> deque1;
    copy(first, last, back_inserter(deque1));
    sort(deque1.begin(), deque1.end());
    copy(deque1.begin(), deque1.end(), first);
}

template <class BidirectionalIterator>
inline void generalized_sort (
    BidirectionalIterator first, 
    BidirectionalIterator last
) {
    __generalized_sort(
        first, last, iterator_category(first), value_type(first)
    );
}

STL iterators
Back to index

Consider the following:

   list<int> list1;
   //
   // populate list1 with what-not.
   //
   list<int> list2;
   // DOESN'T WORK.
   copy(list1.begin(), list1.end(), list2.begin());  

   // this works because back_list_iterator invokes push_back() which
   // dynamically resizes the list as appropriate. Note that if the
   // target were a set, inserter would've been
   // the appropriate one.
   copy(list1.begin(), list1.end(), back_list_iterator<int> (list2));

#include <stl.h>
#include <math.h>
#include <iostream.h>

typedef map<int, float, less<int> > MyMap;

void dump_map(ostream& os, const MyMap& map_) {
    for(MyMap::const_iterator i = map_.begin(); i != map_.end(); ++i) {
        os << "(" << (*i).first << " " << (*i).second << ") ";
    }
}

int main(int, char*[]) {
    MyMap map1;
    for(int i = 1; i < 5; ++i)
        map1[i] = sqrt(i);
    
    MyMap map2;
    for(i = 10; i < 15; ++i)
        map2[i] = sqrt(i);

    cerr << "==> Map1" << endl;
    dump_map(cerr, map1);
    cerr << endl << endl;
    cerr << "==> Map2" << endl;
    dump_map(cerr, map2);
    cerr << endl << endl;

    copy(map2.begin(), map2.end(), 
        insert_iterator<MyMap> (map1, map1.begin())
    );
    cerr << "==> Map1 += Map2" << endl;
    dump_map(cerr, map1);
    cerr << endl << endl;
    return 0;
}

1. Function adaptors
2. Data type adaptors

For example, you can create copy_if from remove_copy_if by negating the predicate that you supply to remove_copy_if().

    //
    // fill up a list with some numbers.
    //
    const int list1[] = {18, 3, 21, 3, 24, 3};
    const int npoints = sizeof(list1)/sizeof(list1[0]);

    cout << endl << "===> Initial list" << endl;
    ostream_iterator<int> citer(cout, "\n");
    copy(list1, list1 + npoints, citer);

    //
    // create a new sequence with all elements but 3's from list1. Note
    // that we initialize the result container to be as large as the
    // original one and use a simple output iterator.
    //
    cout << endl << "===> Removing all 3's" << endl;
    list<int> list2(npoints);
    list<int>::iterator iter = remove_copy_if(
	list1, list1 + npoints, list2.begin(),
	bind2nd(equal_to<int> (), 3)
    );
    copy(list2.begin(), iter, citer);
    cout << "===" << endl;

    //
    // create a new sequence with all elements from list1, but 3's. Note
    // that we use a front_insert_iterator in this case.
    //
    cout << endl << "===> Removing all but 3's" << endl;
    list<int> list3;
    front_insert_iterator<list<int> > out_iter(list3);
    iter = remove_copy_if(
	list1, list1 + npoints, out_iter,
	not1 (bind2nd(equal_to<int> (), 3))
    );
    copy(list3.begin(), iter, citer);
    cout << "===" << endl;

Data type adaptors

Performance Note: When you have a choice between a list and a dequeu for some adaptor, I have found dequeu to give better, and in some cases, much better, performance.

1. Stack
2. Queue
3. Priority Queue

Stack

#include <stl.h>
#include <iostream.h>

int main () {
    typedef stack<deque<int> > IntStack;
    IntStack istack;
    istack.push (31);
    istack.push (87);
    istack.push (13);
    istack.push (29);
    while (!istack.empty ()) {
        cout << istack.top () << endl;
        istack.pop ();
    }
    return 0;
}

And the output:

29
13
87
31

Queue

#include <stl.h>
#include <iostream.h>

int main () {
    typedef queue<deque<int> > IntQueue;
    IntQueue iqueue;
    iqueue.push (31);
    iqueue.push (87);
    iqueue.push (13);
    iqueue.push (29);
    while (!iqueue.empty()) {
        cout << iqueue.front() << endl;
        iqueue.pop ();
    }
    return 0;
}

And the output:

31
87
13
29

Priority Queue

#include <stl.h>
#include <iostream.h>

int main () {
    typedef priority_queue<deque<int>, less<int> > IntPQueue;
    IntPQueue ipqueue;
    ipqueue.push (31);
    ipqueue.push (87);
    ipqueue.push (13);
    ipqueue.push (29);
    while (!ipqueue.empty()) {
        cout << ipqueue.top() << endl;
        ipqueue.pop();
    }
    return 0;
}

And the output:

87
31
29
13

#include <stl.h>
#include <iostream.h>

static bool even(int i) {
    return i % 2 == 0;
}

int main(int, char*[]) {
    list<int> list1;
    for(int i = 0; i < 10; ++i) {
        list1.push_back(i * i);
    }

    ostream_iterator<int> out(cout, " ");
    cout << "==> Initial list (x(i) = i**2):              [";
    copy(list1.begin(), list1.end(), out);
    cout << "]" << endl;

    list<int>::iterator end = remove_if(list1.begin(), list1.end(), even);

    cout << "==> After removing even numbers (Surprise!): [";
    copy(list1.begin(), list1.end(), out);
    cout << "]" << endl;

    list1.erase(end, list1.end());

    cout << "==> After erasing removed numbers:           [";
    copy(list1.begin(), list1.end(), out);
    cout << "]" << endl;

    return 0;
}

And here's the output:

==> Initial list (x(i) = i**2):              [0 1 4 9 16 25 36 49 64 81 ]
==> After removing even numbers (Surprise!): [1 9 25 49 81 25 36 49 64 81 ]
==> After erasing removed numbers:           [1 9 25 49 81 ]

//
// Sample STL program to show how to iterate thru list of list's.
//
#include <stl.h>
#include <iostream.h>

//
// convenience typedefs to save typing.
//
typedef list<int> List;
typedef list<List> ListOfList;

void print_list(const List& list1, int id) {
    ostream_iterator<int> out(cout, " ");
    cout << "list " << id << ": ";
    copy(list1.begin(), list1.end(), out);
    cout << endl;
}

int main () {
    ListOfList list_of_list1;

    //
    // create the list of list: total of 3 lists, each with 4 members.
    //
    for(int i = 0; i < 3; ++i) {
        List list1;
        for(int j = 0; j < 4; ++j) {
            list1.push_back(i * 4 + j);
        }
        print_list(list1, i+1);
        list_of_list1.push_back(list1);
    }

    cout << endl;

    //
    // now iterator thru list of lists.
    //
    ListOfList::iterator it = list_of_list1.begin();
    for(int j = 1; it != list_of_list1.end(); ++it, ++j) {
        const List& list1 = *it;
        print_list(list1, j);
    }

    return 0;
}

And the output:

list 1: 0 1 2 3 
list 2: 4 5 6 7 
list 3: 8 9 10 11 

list 1: 0 1 2 3 
list 2: 4 5 6 7 
list 3: 8 9 10 11 

There are 2 things to look out for:

1. For containers that support random-access iterators, use the STL sort algorithm which uses quicksort.
2. If your container objects are non-trivial, you should arm your container object with the appropriate constructors and comparison operators. See here for more info.

• Sorting a list of user defined objects
• Sorting a vector of user defined objects

#include <iostream.h>
#include <stdlib.h>
#include <stl.h>
#include <string.h>

inline char* strnew(const char* str) {
    char* newstr = 0;
    if (str) {
        newstr = new char[strlen(str) + 1];
        strcpy(newstr, str);
    }
    return newstr;
}

struct ListElem {
    int id_;
    char* name_;
    ListElem() :
        id_(0),
        name_(strnew("unknown"))
    { }
    ListElem(const ListElem& elem) :
        id_(elem.id_),
        name_(strnew(elem.name_))
    { }
    ListElem(int id, const char* name) :
        id_(id),
        name_(strnew(name))
    { }
    ~ListElem() { 
        delete[] name_;
    }
    ListElem& operator= (const ListElem& elem) {
        id_ = elem.id_;
        delete[] name_;
        name_ = strnew(elem.name_);
    }
    bool operator< (const ListElem& elem) const {
        return id_ < elem.id_;
    }
    bool operator== (const ListElem& elem) const {
        return id_ == elem.id_;
    }
    void print(ostream& os) const {
        os << "(" << id_ << " " << name_ << ")";
    }
};

void print_list(ostream& os, const list<ListElem>& list1) {
    for(
        list<ListElem>::const_iterator it = list1.begin();
        it != list1.end();
        ++it
    ) {
        const ListElem& elem = *it;
        elem.print(os);
    }
}

int main(int, char*[]) {
    list<ListElem> list1;
    list1.push_back(ListElem(5, strnew("5")));
    list1.push_back(ListElem(0, strnew("0")));
    list1.push_back(ListElem(99, strnew("99")));
    list1.push_back(ListElem(-1, strnew("-1")));
    list1.push_back(ListElem(31, strnew("31")));

    cerr << "Initial list: ";
    print_list(cerr, list1);
    cerr << endl;

    //
    // cannot use sort(list1.begin(), list1.end()) here; instead, must use
    // sort() member of list class. Hint: lists don't support random access 
    // iterators.
    //
    list1.sort();

    cerr << " Sorted list: ";
    print_list(cerr, list1);
    cerr << endl;

    return 0;
}

% ./stl-list-sort
Initial list: (5 "5")(0 "0")(99 "99")(-1 "-1")(31 "31")
 Sorted list: (-1 "-1")(0 "0")(5 "5")(31 "31")(99 "99")

#include <iostream.h>
#include <stdlib.h>
#include <stl.h>
#include <string.h>

inline char* strnew(const char* str) {
    char* newstr = 0;
    if (str) {
        newstr = new char[strlen(str) + 1];
        strcpy(newstr, str);
    }
    return newstr;
}

struct ListElem {
    int id_;
    char* name_;
    ListElem() :
        id_(0),
        name_(strnew("unknown"))
    { }
    ListElem(const ListElem& elem) :
        id_(elem.id_),
        name_(strnew(elem.name_))
    { }
    ListElem(int id, const char* name) :
        id_(id),
        name_(strnew(name))
    { }
    ~ListElem() { 
        delete[] name_;
    }
    ListElem& operator= (const ListElem& elem) {
        id_ = elem.id_;
        delete[] name_;
        name_ = strnew(elem.name_);
    }
    bool operator< (const ListElem& elem) const {
        return id_ < elem.id_;
    }
    bool operator== (const ListElem& elem) const {
        return id_ == elem.id_;
    }
    void print(ostream& os) const {
        os << "(" << id_ << " " << name_ << ")";
    }
};

void print_vector(ostream& os, const vector<ListElem>& vector1) {
    for(
        vector<ListElem>::const_iterator it = vector1.begin();
        it != vector1.end();
        ++it
    ) {
        const ListElem& elem = *it;
        elem.print(os);
    }
}

int main(int, char*[]) {
    vector<ListElem> vector1;
    vector1.push_back(ListElem(5, strnew("5")));
    vector1.push_back(ListElem(0, strnew("0")));
    vector1.push_back(ListElem(99, strnew("99")));
    vector1.push_back(ListElem(-1, strnew("-1")));
    vector1.push_back(ListElem(31, strnew("31")));

    cerr << "Initial vector: ";
    print_vector(cerr, vector1);
    cerr << endl;

    sort(vector1.begin(), vector1.end());

    cerr << " Sorted vector: ";
    print_vector(cerr, vector1);
    cerr << endl;

    return 0;
}

% ./stl-list-sort
Initial list: (5 "5")(0 "0")(99 "99")(-1 "-1")(31 "31")
 Sorted list: (-1 "-1")(0 "0")(5 "5")(31 "31")(99 "99")

#include <stl.h>                // or individual includes if you like
#include <iostream.h>

int main(int, char*[]) {
    const unsigned ncards = 5;
    int cards[ncards];
    for(int i = 0; i < ncards; ++i) {
        cards[i] = i + 1;
    }

    // print out the initial list (should be 1 ... ncards).
    ostream_iterator<int> out(cout, " ");
    cout << "initial: ";
    copy(cards, cards + ncards, out);
    cout << endl;

    // shuffle and print out the shuffled list 
    random_shuffle(cards, cards + ncards);
    cout << "shuffled: ";
    copy(cards, cards + ncards, out);
    cout << endl;

    return 0;
}

initial: 1 2 3 4 5 
shuffled: 3 1 5 2 4 

Miscellaneous examples/notes
Back to index

    template <class InputIterator, class T>
    void __do_something(InputIterator first, InputIterator last, T*) {
	T tmp;
	//
	// now we can create variables of type T!
	//
    }
    
    template <class InputIterator>
    void do_something(InputIterator first, InputIterator last) {
        __do_something(first, last, value_type(first));
    }

Miscellaneous examples/notes
Back to index

I'm making available an extremely simple and crude implementation of Persistent STL using libg++-2.6.2 hacked STL as the base implementation. Send me email if you'd like to know more about it. My current prototype is based on Texas Persistent Store v0.3 from UT-Austin OOPS research group. Click here for a GNU zip'd and tar'd copy of the current prototype (v0.1.1).

Persistent STL
Back to index

I've been using ObjectSpace STL<ToolKit> with gcc-2.6.3 quite heavily in the last few weeks and it turns out to be pretty solid. You obviously only get what GCC supports, but ObjectSpace did a pretty good job in squeezing out everything possible out of GCC in their implementation. I've run into a few problems (other than the well-known ones mentioned in the release notes), but there are easy work-arounds. Recently I have switched to ObjectSpace STL<ToolKit< with GCC 2.7.0.

GCC 2.7.0 users: ObjectSpace is providing bug fixes for STL <ToolKit> version 1.1 to make it work GCC 2.7.0. Please get in touch with ObjectSpace tehnical support for more information on how to acquire the fixes.

If you're using GCC 2.6.3, two things before you start:

• patch 2.6.3 with the template fix ftp://ftp.cygnus.com/pub/g++/gcc-2.6.3-template-fix This solves the multiple definition problem.
• learn the art of manual template instantiation if you want to avoid incredible code bloat in reasonable sized programs.

If you're using GCC 2.7.0, two things before you start:

• patch 2.7.0 with the template repository fix ftp://ftp.cygnus.com/pub/g++/gcc-2.7.0-repo.gz This allows you to use template repositories to instantiate templates.
• learn how to instantiate templates using the Cygnus -frepo.

Things in favor of ObjectSpace implementation:

• GREAT install utility, esp if you want to use it for multiple compilers.
• TONS of example programs. I believe these are now donated to the public domain and archived at the HP STL site (butler.hpl.hp.com).
• Terrific manual. Just the manual is worth the $149 or so you pay for OS STL.
• source code (guess it'll be kind of hard not to supply source :-)

• Not the greatest telephone support.
• crippled by the limitations of GCC (2.7.0 should make this a lot easier), the least of which are:
  • no just-used-member instantiation. One side effect is the extra unnecessary code generated, and the other one that is that even you don't use sort on a list, you still have to define relation operator <.
  • Manual instantiation is not uniform across platforms. The Utah HP PA GCC release needs some extra instantiations.
• Some non-standard methods (like erase()) and non-standard algorithms (like release). The documentation does mention that these are non-standard, but the index should note that as well. Both are trivial to write, and I did to make sure that the code works with other implementations.

• OS provides a <stl.h> that includes EVERYTHING. I personally liked it when I started out, and I recommend the same to newcomers. After you figure out what STL is all about, it's pretty easy to include only the necessary include files. Obvious compile time tradeoff. This may not be available in other implementations (eg., ones from HP and FSF/GNU), but again, trivial to write. See here for an example one.
• Some header file names may be different from other implementations. For example, OS <algorith.h> vs FSF/GNU and HP <algo.h>. If you choose to include individual headers instead of the <stl.h> shabang, watch out for these tiny things if you need portability with other implementations.

If you have templated code (eg., when using STL) and you're stuck with GCC, there are three ``somewhat portable'' ways to go (I don't like weird #pragma directives that are compiler specific):

• Compile everything with no special flags and let GCC instantiate everything in sight statically each translation unit. This is great if you're building small applications (or if you have a single source file), but results in incredible code bloat for medium to large applications.
• Compile everything with -fno-implicit-templates and manually instantiate the templates. Takes a bit of patience (and a C++ demangler, such as c++filt), but certainly doable and it does alleviate the template bloat somewhat. See here for more info.
• If you're willing to upgrade to GCC version 2.7.0 and apply the frepo patch from Jason Merrill of Cygnus Support, you will be pleasantly surprised at how easy template instantiation can be. See here for more info.

Visibility of template definitions

One major complication with GCC is that all the template definitions must be visible at the point of instantiation (which may not be the case with Borland, but I wouldn't know about that), and if you have the template class members defined in a .cc file that is not included in the declaration file (.h), then you'll get undefined errors. The simple trick there is to conditionally include the .cc file in the template header .h file with some preprocessor directive that gets set for compilers like gcc. Take the following example:

=== template.h
template <class T> 
class XX {
public:
    XX(T t) : t_(t) { }
    T value() const;		// declaration only, defn not inline.
private:
    T t_;
};

==== template.cc
#include "template.h"

template <class T>
T XX<T>::value() const {
    return t_;
}

=== main.cc

#include <iostream.h>
#include "template.h"

int main (int, char*[]) {
    XX<int> xx(5);
    cerr << "value = " << xx.value() << endl;
    return 0;
}
===

This will *NOT* work for gcc unless you also include template.cc at the end of template.h. You'll get undefined error that looks something like:

    
    ld: Undefined symbol
	XX<int>::value(void) const
    collect2: ld returned 2 exit status

=== template.h
template <class T>
class XX {
public:
    XX(T t) : t_(t) { }
    T value() const;
private:
    T t_;
};

#if INCLUDE_TEMPLATE_DEFINITION
# include "template.cc"
#endif
===

#if __GNUC__ <= 2 && __GNUC_MINOR__ <= 7
# define INCLUDE_TEMPLATE_DEFINITION
#endif

Let's start with a trivial program, where a list is the only STL data type used, specifically list<int>. For the examples here, I'm assuming ObjectSpace STL<ToolKit> with GCC 2.6.3 appropriately patched with Jason Merrill template fix (the same idea applies to FSF/GNU STL, but the particular set of templates that need to be instantiated may differ due to implementation differences).

Here's a trivial test program:

#include <stl.h>                // include everything for simplicity.
#include <iostream.h>
#include <stdlib.h>

int main(int, char*[]) {
    list<int> list1;
    for(int i = 0; i < 10; ++i) {
        list1.push_back(rand());
    }
    return 0;
}

(STL_INCLUDE_DIRS and STL_LIBS depend on your system).

% g++ -fno-implicit-templates -c $(STL_INCLUDE_DIRS) f1.cc
% g++ -o f1 f1.o $(STL_LIBS) |& c++filt 
ld: Undefined symbol 
   list<int>::list(void) 
   list<int>::push_back(int const &) 
   list<int>::~list(void) 
collect2: ld returned 2 exit status
gmake: *** [f1] Error 1

So all we have to do is to instantiate the members of list<int> listed above. But the problem is that GCC doesn't allow instantiating individual members, so we'll simply instantiate ALL the members for now (until GCC fixes it).

so now I can create a file template-inst.cc:

#include <stl.h>

template class list<int>;

% g++ -c $(STL_INCLUDE_DIRS) template-inst.c
% g++ -o f1 f1.o template-inst.o $(STL_LIBS) |& c++filt 
% ./f1
%

Now for a bit of reality. Let's say you are going to use the following templated data types in STL:

• list<int>
• deque<int>

and the following algorithms:

• copy (to ostream_iterator)
• copy (list to deque)
• for_each (on list objects)

#include <stl.h>                // include everything for simplicity.
#include <iostream.h>
#include <stdlib.h>

int main(int, char*[]) {
    deque<int> deque1;
    for(int i = 0; i < 10; ++i) {
        deque1.push_back(rand());
    }

    ostream_iterator<int> out(cout, " ");
    cout << "==> Deque1: ";
    copy(deque1.begin(), deque1.end(), out);
    cout << endl << endl;

    list<int> list1;
    copy(deque1.begin(), deque1.end(), 
        back_insert_iterator<list<int> > (list1)
    );

    cout << "==> List1: ";
    copy(list1.begin(), list1.end(), out);
    cout << endl << endl;

    //
    // This nested (within main) struct is going to cause problems later
    // on.
    //
    struct FooBar {
        void operator() (int val) const {
            cout << " " << val;
        }
    };
    cout << "==> For_each List1: ";
    for_each(list1.begin(), list1.end(), FooBar());
    cout << endl << endl;

    return 0;
}

% g++ -fno-implicit-templates -c $(STL_INCLUDE_DIRS) f2.cc
% g++ -o f2 f2.o $(STL_LIBS) |& c++filt 
ld: Undefined symbol 
   list<int>::list(void) 
   deque<int>::deque(void) 
   deque<int>::begin(void) 
   copy(list_iterator<int>, list_iterator<int>, ostream_iterator<int>) 
   copy(deque_iterator<int>, deque_iterator<int>, ostream_iterator<int>) 
   copy(deque_iterator<int>, deque_iterator<int>, back_insert_iterator<list<int> >) 
   ostream_iterator<int>::ostream_iterator(ostream &, char *) 
   deque<int>::end(void) 
   for_each(list_iterator<int>, list_iterator<int>, main::FooBar) 
   list<int>::~list(void) 
   list<int>::begin(void) 
   list<int>::end(void) 
   back_insert_iterator<list<int> >::back_insert_iterator(list<int> &) 
   deque<int>::~deque(void) 
   deque<int>::push_back(int const &) 
collect2: ld returned 2 exit status
gmake: *** [f2] Error 1

Note the for_each instantiation -- we cannot manually instantiate it because of the main::FooBar, so we simply move FooBar to file scope (not shown here) and redo the compile and link commands.

After moving FooBar to file scope in f2.cc:

% g++ -fno-implicit-templates -c $(STL_INCLUDE_DIRS) f2.cc
% g++ -o f2 f2.o $(STL_LIBS) |& c++filt 
ld: Undefined symbol 
   list<int>::list(void) 
   deque<int>::deque(void) 
   deque<int>::begin(void) 
   copy(list_iterator<int>, list_iterator<int>, ostream_iterator<int>) 
   copy(deque_iterator<int>, deque_iterator<int>, ostream_iterator<int>) 
   copy(deque_iterator<int>, deque_iterator<int>, back_insert_iterator<list<int> >) 
   ostream_iterator<int>::ostream_iterator(ostream &, char *) 
   deque<int>::end(void) 
   for_each(list_iterator<int>, list_iterator<int>, FooBar) 
   list<int>::~list(void) 
   list<int>::begin(void) 
   list<int>::end(void) 
   back_insert_iterator<list<int> >::back_insert_iterator(list<int> &) 
   deque<int>::~deque(void) 
   deque<int>::push_back(int const &) 
collect2: ld returned 2 exit status
gmake: *** [f2] Error 1

#include <stl.h>
#include <iostream.h>

template class list<int>;
template class list_iterator<int>;
template class back_insert_iterator<list<int> >;

template class ostream_iterator<int>;

template class deque<int>;
template class deque_iterator<int>;

template void copy(
    list_iterator<int>, list_iterator<int>, ostream_iterator<int>
); 

template void copy(
    deque_iterator<int>, deque_iterator<int>, ostream_iterator<int>
);

template void copy(
    deque_iterator<int>, deque_iterator<int>, back_insert_iterator<list<int> >
); 

struct FooBar {
    void operator() (int val) const {
        cout << " " << val;
    }
};
template void for_each(list_iterator<int>, list_iterator<int>, FooBar); 

% g++ -fno-implicit-templates -c $(STL_INCLUDE_DIRS) f2.cc
% g++ -c $(STL_INCLUDE_DIRS) template-inst.cc
% g++ -o f2 f2.o template-inst.o $(STL_LIBS) |& c++filt 
% ./f2

==> Deque1: 1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847 

==> List1: 1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847 

==> For_each List1:  1103527590 377401575 662824084 1147902781 2035015474 368800899 1508029952 486256185 1062517886 267834847

Let's start with a trivial program, where a list is the only STL data type used, specifically list<int>. For the examples here, I'm assuming ObjectSpace STL<ToolKit> with GCC 2.7.0 appropriately patched with Jason Merrill template frepo patch. It should also work just fine with any other STL implementation that happens to work with GCC.

• A trivial example: building a simple standalone application
• Providing library closure(s)

A trivial example: building a simple standalone application

Here's a trivial test program:

#include <stl.h>                // include everything for simplicity.
#include <iostream.h>
#include <stdlib.h>

int main(int, char*[]) {
    list<int> list1;
    for(int i = 0; i < 10; ++i) {
        list1.push_back(rand());
    }
    return 0;
}

(STL_INCLUDE_DIRS and STL_LIBS depend on your system).

% g++ -frepo -c $(STL_INCLUDE_DIRS) f1.cc
% g++ -frepo -o f1 f1.o $(STL_LIBS) 
collect: recompiling f1.cc
collect: relinking
collect: recompiling f1.cc
collect: relinking
collect: recompiling f1.cc
collect: relinking
%

And Voila! Granted, the first time you better go to lunch during build, but the subsequent times are much faster. How does it work? Quick answer: look in the build directory for f1.rpo and study it. You can get a good feel for what's happenning here by doing the following:

• start afresh, ie., delete f1, f1.o and f1.rpo
• simply compile f1.cc with the -frepo option and copy (not rename!) the resulting f1.rpo file to another file, say f1.rpo.org
• build the executable f1 as in the example above and now compare the updated f1.rpo with your saved version). Notice that difference in the first column (the 'O's and the 'C's)

Providing library closure(s)

[
    build all the object files needed to build the library using the 
    -frepo option
]
% gcc $(CPPFLAGS) $(CXXFLAGS) -frepo -o closure $(OBJS)
collect: recompiling xx.cc
collect: relinking
...
collect: recompiling xx.cc
collect: relinking
[
    Whole bunch of error messages about unresolved stuff -- ignore
]
% ar crv libxyz.a $(OBJS)
% ranlib libxyz.a

This forced instantiation is fortunately quite extendible; consider the following case:

• Application a needs to link with libraries l1 and l2.
• Library l2 uses l1, and hence some of the templates in l2 are also instantiated in l1 if we build them separately using the method described in the previous paragraph.

The fix is quite simple:

• Build l1 as in the example case above (ie., force the instantiation of all templates used within).
• Build l2 with l1 on the command line.

  % gcc $(CPPFLAGS) $(CXXFLAGS) -frepo -o closure $(L2_OBJS) libl1.a
  collect: recompiling xx.cc
  collect: relinking
  ...
  collect: recompiling xx.cc
  collect: relinking
  [
      Whole bunch of error messages about unresolved stuff -- ignore
  ]
  % ar crv libl2.a $(L2_OBJS)
  % ranlib libl2.a
  
  

• Now link the application with the two libraries, and you're in business.

//
// Suck in the entire (HP implementation derived) STL.
// This is very helpful for beginners, and one gets more familiar with
// STL, it's easy to figure out which headers to include. Also, different
// implementations might have different header names, eg., ObjectSpace
// has <algorith.h> and HP has <algo.h> Go figure.
//

#ifndef STL_H
#define STL_H

#include <algo.h>
#include <function.h>
#include <iterator.h>
#include <list.h>
#include <deque.h>
#include <map.h>
#include <pair.h>
#include <set.h>
#include <stack.h>
#include <vector.h>

#endif

1. SGI STL: Freely available STL implementation from SGI. Lots of useful links to other STL sites as well. A site to visit for all STL enthusiasts.
2. HP: This supposedly compiles with Borland C++ 4.5 out of the box. An alternate site is here .
3. FSF/GNU libg++ 2.6.2: Works with GCC 2.6.3 or newer. Based on Carsten Bormann's work.
4. FSF/GNU libg++ 2.7.0a: Works with GCC 2.7.0 or newer. Based on Carsten Bormann's work.
5. Bagnara: Another hacked STL based on HP implementation (modified GNU sources). Works with GCC 2.6.3 or newer.

C++ draft standard document:

1. HTML version of the DWP (courtesy of Mike Stump of Cygnus Support).
2. PDF and Postscript versions from Bell Labs ftp site.

Web pages/FTP sites with info on STL:

1. ObjectSpace examples: ObjectSpace has contributed over 300 examples to the public domain and these are a very good start for beginners.
2. Joseph Y. Laurino's STL page.
3. Musser's STL docs and examples. Very nice.
4. STL Newbie home site.
5. Marian Corcoran's STL FAQ.
6. Jak Kirman's STL Tutorial

Back to index
Go to Mumit's Home Page