Author : Mumit Khan
Page : 1 Next >>
-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
About this Document
I started this document as a wastebasket for my random notes and thoughts on STL when I first started learning and using it heavily during winter of 1994. So far I have only included a small subset of my STL.NOTES file here (because it is such a mess), and hopefully will keep adding to it over the next few weeks.
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
General overview
My primary motivation for starting this guide is to help those who are starting out with STL and I would like to hear from you if you find it useful. Currently most of this document really deals with issues that are hard to find in manuals, such as how to create containers of pointers, or how to manage manual instantiation of STL template with GCC, etc.
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).
What's so special about writing container objects
STL containers copy the objects for local storage, and typically make heavy use of the default constructor, copy constructor and assignment operator.
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
For each class X, define the following constructors (unless you're happy with the compiler provided ones of course):
default constructor -- X();
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
For each class X, define the following operators (again, unless you're happy with the compiler provided ones of course):
operator= (const X&)
Better have this -- same effect as copy constructor.
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.
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?
One of the most frequent questions regarding STL seems to be of the following form:
What members do I have to define for an object that will live in
an STL container?
To explain this without having to go through the STL source code, let's examine how list<T> works. Here's a typical list usage scenario:
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)
Now let's see what happens at steps (1) through (7).
Enter a new scope, function f. Automatic objects will be destructed when we leave this scope in Step (7).
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.
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;
}
Page : 1 Next >>