How would you go about learning STL? I know how the data structures work because I have written my own, but STL''s classes look like a nightmare! OK, maybe a little worse than a nightmare.

the std::list class declaration:  

template >
    class list {
public:
    typedef A allocator_type;
    typedef A::size_type size_type;
    typedef A::difference_type difference_type;
    typedef A::reference reference;
    typedef A::const_reference const_reference;
    typedef A::value_type value_type;
    typedef T0 iterator;
    typedef T1 const_iterator;
    typedef reverse_bidirectional_iterator reverse_iterator;
    typedef reverse_bidirectional_iterator const_reverse_iterator;
    explicit list(const A& al = A());
    explicit list(size_type n, const T& v = T(), const A& al = A());
    list(const list& x);
    list(const_iterator first, const_iterator last,
        const A& al = A());
    iterator begin();
    const_iterator begin() const;
    iterator end();
    iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
    void resize(size_type n, T x = T());
    size_type size() const;
    size_type max_size() const;
    bool empty() const;
    A get_allocator() const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;
    void push_front(const T& x);
    void pop_front();
    void push_back(const T& x);
    void pop_back();
    void assign(const_iterator first, const_iterator last);
    void assign(size_type n, const T& x = T());
    iterator insert(iterator it, const T& x = T());
    void insert(iterator it, size_type n, const T& x);
    void insert(iterator it,
        const_iterator first, const_iterator last);
    void insert(iterator it,
        const T *first, const T *last);
    iterator erase(iterator it);
    iterator erase(iterator first, iterator last);
    void clear();
    void swap(list x);
    void splice(iterator it, list& x);
    void splice(iterator it, list& x, iterator first);
    void splice(iterator it, list& x, iterator first, iterator last);
    void remove(const T& x);
    void remove_if(binder2nd > pr);
    void unique();
    void unique(not_equal_to pr);
    void merge(list& x);
    void merge(list& x, greater pr);
    void sort();
    template
        void sort(greater pr);
    void reverse();
protected:
    A allocator;
    };
 

blech! And what''s with all the pushing and popping? Back to the main question, though: How do I learn it? Are there any good tutorials on the ''net? Or just a few pages in the docs? The class references seem to be as cryptic as the class declarations... Also, what in the world are function objects? - null_pointer Sabre Multimedia

Try SGI''s STL library reference.

http://www.sgi.com/Technology/STL/

Mason McCuskey
Spin Studios - home of Quaternion, 2000 GDC Indie Games Fest Finalist!
www.spin-studios.com

Pushing means to insert at the end (either front or back, depending on push_front/push_back). Pop is to delete the element at either the front or back (again depending on the function) and return the contents of that element. It''s in the list specification so that you can use it as a stack/queue.

Function objects are instances of classes such that the operator () is overloaded, so that they can be called like a function.
ex:
class Add() {
int operator()(const int& x, const int& y) { return x + y; }
}

Then you can do:
Add a;
z = a(x1, y1);

It''s a way of passing functions without passing function pointers.

You know, a Google search on STL brings up quite a few good sites.
www.google.com

Mike

OK, thanks for the references everyone!

SiCrane: This may seem like a stupid question, but since you are passing the function specification with all of its typing etc. why not pass a function pointer? That''s why we have function pointers, right? Also, why are the queue-like functions found in the base class, list? Why didn''t they just derive classes from list and then add the functions?


- null_pointer
Sabre Multimedia

Check out http://www.icce.rug.nl/docs/cplusplus/

I have no idea why they bothered to throw in all those darn functions into the STL classes. It''s one of my (many) beefs with STL. Ok, actually I have one theory, that it''s considered a violation of the abstraction method to create subclasses that access the class data members directly. Therefore subclasses that implement specific data types based on the list class must be supplied the functions to implement their ADT. So the Stack class can implement a call to Pop as a call to pop_front, etc.

Function objects have an advantage that you can enclose state into the function calls. ex: counting the number of times the function is called. You could, for example, profile a sort function, by having the function object you pass for the comparison operation increment an internal counter.

Yes, the headers look really bad The SGI STL is much more readable than the DinkumWare one, which I think was cut down to a minimal size to speed compilation. (At least I hope so. Otherwise that P.J. Plauger guy is one demented programmer.) The SGI docs are probably the best, too, although to be honest I've found -no- STL docs to be perfect. I like to keep a link to the SGI and the Borland C++ Builder STL documentation in MSVC along with its own Dinkumware docs, so that anything missing or glossed over in one is covered elsewhere.

But a lot of why they look really bad is the 4 or 5 levels of indirection. This is so a very similar interface can be used for everything, as I'm sure you can appreciate. This is why we have the pop_* and push_* functions, as they make sense for lists, stacks, queues, heaps, vectors, etc etc.

Function objects are more versatile than function pointers. As SiCrane said, they can store local state. Of course, so can a function, using static variables, but then what if 2 parts of your program want to store different states independently? You will only have 1 set of static variables in that function when you might want 2 or more instances. So, the answer is function objects - just instantiate another one, which will have its own internal state etc.

Just a convoluted example:

class FuncObj{public:    int called;    FuncObj() : called(0) {}    int operator(int stuff)    {        // Do something with 'stuff'        return ++called;    }};  

That object just tracks how often you call it. I'm sure you could find some more useful way of using internal state, such as caching the results of the last operation to avoid repeating expensive ones. Or something.

You could also derive subclasses from your base function object, and use virtual methods to call their specific implementations from a pointer to the base. Changing the functionality without the calling function needing to know. I'm sure you could find a use for this, too.

Oh, and you can still pass function pointers when the STL asks for a function object, too So you get the best of both worlds. Some parts of the STL will require you use the ptr_fun member to wrap your pointer, but I've never needed that yet.

The 'queue-like' functions in the list class suit list perfectly well, so I'm not sure what your problem is with that. Perhaps you could elaborate? The idea is to have a unified interface, so that you can learn one data structure and you pretty much know them all. So although the names may not seem 'list-like', you get used to them. The main reason why there isn't much inheritance to achieve the unified interface goal is that most of these functions return iterators, and whereas list returns a bi-directional iterator, deque returns a random-access iterator for the same functions. Others return different iterators entirely. In fact, many implementations do not return a basic iterator, they return a special type that is specialised for that class. So although the names are the same, the function signatures are not. A final reason would be that nesting any more templates than already happens would slow compile times down even further. Which would annoy me.

Edited by - Kylotan on May 14, 2000 8:45:54 AM

If your looking to learn STL then i can recommend none other than the man who designed the library or to be more exact, C++ itself

Therefore learning comes in a little oblong form called a book:

The C++ Programming language
by Bjarne Stroustrup
ISBN: 0-201-88954-4

I highly recommend this book for any programmer especially
migrating from c -> C++ !

First, the book I used to learn STL:
STL tutorial and reference guide : C++ programming with the standard template library. C plus plus / Musser, David R.. Reading, MA : Addison-Wesley Pub. Co, c1996.

Second, here are some hints about learning STL:
There are three parts to the library: containers, iterators and functions. IMO, you have to understand iterators before anything else. Once you understand how iterators work, containers and functions and how they work together will be easy to understand.

Now, that header you listed REALLY doesn''t have much in it. Just look at it a piece at a time:

As far as the template declaration goes, you just have to worry about the type &ltT&gt. Just leave the allocator as the default--you won''t need to overload your own custom allocator until you get WAY deep into STL. I''ve never had to do it. So all you really need is template&ltclass T> class list.

You can ignore all the typedefs. They''re for internal use within the library only. Sometimes it''s handy to use them for maps (map::value_type, for inserts), but for a list you don''t need them. At most, you''ll want to typedef your list and then call up MyList::iterator or MyList::const_iterator once in a while.

So, you have your 4 constructors, which are handy to study since they each construct a list differently. That''s one major part of the container.

Next, you should notice that many of the functions are simply overloaded for const-ness. That kinda cuts the rest of the functions in half. For the other functions, there are just some overloads to show multiple ways of doing the same thing (i.e. for assign, you can choose a starting and ending iterator from another container, like a copy, or you can specify a number of copies and a value).

So really, all you have with a list is:
- constructor
- begin, end, rbegin, rend, front, and back, functions that come with every STL container
- your typical list functions, like pushes, pops, inserts, erases, splices.

Now, list is a very special STL class because it doesn''t have a random-access iterator; it only has bi-directional iterators. That means that a great many of the standard STL functions will not work with a list. Therefore, STL''s list has list-specific functions that perform the same task as in the &ltalgorithm> library: remove, remove_if, unique, merge, sort, and reverse. With the other containers, there''s no need for these functions.

Well, that''s list in a nutshell. List is a kinda hard place to start. If I were you, I''d start with a book, then learn the iterators, then look at some of the algorithms, and then jump into the containers in the following order:
vector, deque, list, map/set/multimap/multiset.
(The last 4 are all pretty much the same container).

HTH