6

I've started coding in C++, coming from a Java background (actually I'd studied C++ at my university, but we never got to the STL etc.)

Anyway, I've gotten to the point where I'm arranging data in all sorts of collections, and I immediately tell myself "Ok, this is a kind of a Set; and this is a List, or an ArrayList; and this is a map etc." In Java, I would simply have whatever class I'm writing implement the Set or Map or List interface; but I would probably not go as far as inheriting ArrayList or HashSet or what-not, the implementations there are kind of involved and I wouldn't want to mess them up.

Now, what do I do in C++ (with the Standard Library)? There do not seem to be abstract base classes for Sets, Maps, Lists etc - the equivalent of Java interfaces; on the other hand, the implementations for the standard containers look pretty horrid. Ok, maybe they're not so horrid once you get to know them, but suppose I just wanted to write something like a non-virtual class extending AbstractSet in C++? Something I would be able to pass to any function which takes a Set? How should I go about doing that?

Just to clarify - I don't necessarily want to do what's common practice in Java. But, on the other hand, if I have an object which, conceptually, is a kind of set, I want to inherit something appropriate, get default implementations gratis, and be guided by my IDE to implement those methods which I should implement.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 2
    Generally speaking, inheritance is not the C++ (or at least C++-standard-library) way of achieving reusability. Generic programming (implemented using templates) is. For example, a function for iterating over a collection doesn't take a abstract class parameter, it's template'd over the iterator type. –  Dec 29 '13 at 20:50
  • @delnan: I don't want to merely achieve reusability, I want to express relations between classes via inheritance. You're not telling me that isn't the C++, way... are you? – einpoklum Dec 29 '13 at 20:59
  • 1
    I am indeed. The generic programming way is to either leave these relations implicit (and risk less-then-ideal error messages, at least until a future revision of the language standard), or to pull type-level metaprogramming tricks which lead to code like `if(is_iterator::value) { /* do something with iterators */ }`. –  Dec 29 '13 at 21:08
  • @delnan: But, if I paraphrase your comment, you're telling me that C++ these days is more of a template-oriented than an Object-oriented language. I'm kind of, well, shocked. – einpoklum Dec 29 '13 at 21:12
  • 1
    That parapharsing is correct, modulo the "these days". Generic programming is nothing new, the standard library embraces it since the first version of the standard and it even predates the standard. Don't be shocked, be glad you get to learn a new programming paradigm ;-) OOP isn't the be be-all and end-all, merely one of many useful tools. –  Dec 29 '13 at 21:15
  • 3
    This may be an interesting read for you: http://stackoverflow.com/questions/1039853/why-is-the-c-stl-is-so-heavily-based-on-templates-and-not-on-interfaces/1039904#1039904 – Benjamin Lindley Dec 29 '13 at 21:17
  • @delnan: I only said 'these days' since I didn't follow the exact progression of the standardization process. Correction accepted. I'm not saying OOP is the be-all and end-all, but what I find surprising is that while C++ may be multi-paradigmatic, OOP seems to be a paradigm it supports only in principle. – einpoklum Dec 29 '13 at 21:24
  • 1
    @einpoklum Depends on what you mean by "only in principle". Nothing forces you to adopt the standard library's conventions: Your code can be as inheritance heavy as you want, and you can create collections using inheritance over generic programming and they'll work just as well as the standard library ones. They obviously won't work with the standard library's algorithms but they won't be second class insofar the language is concerned. –  Dec 29 '13 at 21:27
  • @delnan: Is there an OOPish standard library for C++? If not, then that kind of forces me to use the SL. And lots of code which expects SL containers... – einpoklum Dec 29 '13 at 21:30
  • 3
    @einpoklum Yes, that's the downside of eschewing the accepted convention :-) There are plenty of other libraries offering various collections (two popular ones: boost and Qt), though I don't know offhand if any of them are based on inheritance. As for code expecting SL containers: If they accept iterators, you can adopt almost any container, no matter how perverse, pretty easily: Write an appropriate iterator class. –  Dec 29 '13 at 21:35
  • 1
    @delnan: Thanks. I have been simultaneously enlightened and depressed today. – einpoklum Dec 29 '13 at 21:39
  • 1
    @einpoklum If you want to write C++, you should adopt the conventions of C++. If you find this depressing, you should avoid C++. Simple as that. You obviously *do* think Java-style inheritance-heavy OOP *is* the be-all and end-all of collection libraries, and frankly that's just the wrong way to write C++. That's not how C++ works. It's time for you to forget that way of thinking about things. – Miles Rout Jan 20 '14 at 11:25

5 Answers5

15

The short answer is: there isn't an equivalent, because C++ does things differently.

There's no point arguing about this, it's just the way things are. If you don't like this, use a different language.

The long answer is: there is an equivalent but it's going to make you a little unhappy, because while Java's model of containers and algorithms is heavily based around inheritance, C++'s isn't. C++'s model is heavily based around generic iterators.

Let's say, to take your example, that you want to implement a set. Ignoring the fact that C++ already has std::set, std::multiset, std::unordered_set and std::unordered_multiset, and that these are all customisable with different comparators and allocators, and the unordered ones have customisable hash functions, of course.

So let's say you want to reimplement std::set. Perhaps you're a computer science student and you want to compare AVL trees, 2-3 trees, red-black trees and splay trees, for example.

How would you do this? You would write:

template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>> 
class set {
    using key_type = Key;
    using value_type = Key;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using key_compare = Compare;
    using value_compare = Compare;
    using allocator_type = Allocator;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = std::allocator_traits<Allocator>::pointer;
    using const_pointer = std::allocator_traits<Allocator>::const_pointer;
    using iterator = /* depends on your implementation */;
    using const_iterator = /* depends on your implementation */;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>

    iterator begin() const;
    iterator end() const;
    const_iterator cbegin() const;
    const_iterator cend() const;
    reverse_iterator rbegin() const;
    reverse_iterator rend() const;
    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    void clear();

    std::pair<iterator, bool> insert(const value_type& value);
    std::pair<iterator, bool> insert(value_type&& value);
    iterator insert(const_iterator hint, const value_type& value);
    iterator insert(const_iterator hint, value_type&& value);
    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last);
    void insert(std::initializer_list<value_type> ilist);

    template <class ...Args>
    std::pair<iterator, bool> emplace(Args&&... args);

    void erase(iterator pos);
    iterator erase(const_iterator pos);
    void erase(iterator first, iterator last);
    iterator erase(const_iterator first, const_iterator last);
    size_type erase(const key_type& key);

    void swap(set& other);

    size_type count(const Key& key) const;
    iterator find(const Key& key);
    const_iterator find(const Key& key) const;

    std::pair<iterator, iterator> equal_range(const Key& key);
    std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;

    iterator lower_bound(const Key& key);
    const_iterator lower_bound(const Key& key) const;
    iterator upper_bound(const Key& key);
    const_iterator upper_bound(const Key& key) const;

    key_compare key_comp() const;
    value_compare value_comp() const;
}; // offtopic: don't forget the ; if you've come from Java!

template<class Key, class Compare, class Alloc>
void swap(set<Key,Compare,Alloc>& lhs, 
          set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator==(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator!=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator<(const set<Key,Compare,Alloc>& lhs,
               const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator<=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator>(const set<Key,Compare,Alloc>& lhs,
               const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator>=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

Of course you don't have to write ALL of those, especially if you're just writing something to test parts of them. But if you write all that (and a little bit more I excluded for clarity), then what you will have will be a fully functioning set class. And what is special about that set class?

You can use it anywhere. Anything that works with a std::set will work with your set. It doesn't have to be programmed specially for it. It doesn't need anything. And anything that works on ANY set type should work on it. And any of Boost's algorithms will work on sets.

And any algorithms you write to use on sets will work on your sets and boost's sets and lots of other sets. But not just on sets. If they're written competently they'll work on any container that supports a particular type of iterator. If they need random access they'll require RandomAccessIterators, which std::vector provides, but std::list doesn't. If they need BidirectionalIterators, then std::vector and std::list (and others) will work fine, but std::forward_list won't.

The iterator/algorithm/container thing works really well. Consider the cleanliness of reading a file into a string in C++:

using namespace std;

ifstream file("file.txt");
string file_contents(istreambuf_iterator<char>(file),
                     istreambuf_iterator<char>{});
T.C.
  • 133,968
  • 17
  • 288
  • 421
Miles Rout
  • 1,204
  • 1
  • 13
  • 26
  • So, what you're saying is that - at least in the standard library, and in code in the same spirit - I don't ever write functions which take set pointers or set references, I just write templated functions which take any class, and treat it like it's a set, so that if all the methods are there, it'll work? – einpoklum Jan 17 '14 at 15:54
  • Also, what you find 'clean' in the example, I find ridiculous, because it's sort of like compile-time duck-typing. If we want to have duck typing, just let us have that, and I don't want do bother with the generics hell. And a second reason is that this is anti-object-orientation, since you're telling me to essentially forget about inheritance. – einpoklum Jan 17 '14 at 15:56
  • 3
    Object orientation has **nothing** to do with inheritance. Please, please, please realise that. Object oriented code is code oriented around objects. The code above is oriented around objects. Dynamic polymorphism/inheritance/class-based OO is just one form. Please don't confuse "Java OO" with OO in general. – Miles Rout Jan 18 '14 at 04:16
  • And sure you can write functions that take a reference to a set, but why would you want to do that? – Miles Rout Jan 18 '14 at 04:18
  • Well, I want to write a function which will accept any sets, the whole set, and nothing but a set, so help me Bjarne... and, I want to write it in a .cpp file please, no templating. And none of that duck-typed "if it has the methods you need than you should accept it." – einpoklum Jan 19 '14 at 16:51
  • 7
    Bjarne certainly won't help you, because he, like EVERY OTHER COMPETENT C++ PROGRAMMER, despises the way people try to write Java/Python/C/other languages in C++. If you want to write Java, WRITE JAVA. If you want to write C++, WRITE C++. – Miles Rout Jan 20 '14 at 11:22
  • 1
    Why do you want to write a function which takes a set? – Miles Rout Jan 20 '14 at 11:26
  • 4
    I believe this thread is becoming unnecessarily acrimonious and counter-productive. – einpoklum Jan 20 '14 at 11:46
5

The standard C++ library already implements lists, maps, sets, etc. There is no point in C++ to implement these data structures again. If you implement something like one of these data structures you'd implement the same concept (i.e., use the same function names, order of parameters, names of nested types, etc.). There are various concepts for container (sequence, associative containers, etc.). More importantly, you'd expose the content of your structure using the appropriate iterator concepts.

Note: C++ isn't Java. Don't try to program Java in C++. If you want to program Java, program Java: it works a lot better than trying to do so in C++. If you want to program C++, program C++.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 1
    But, there can be all kinds of lists, maps, sets etc which behave differently than the default; and for whom insertion and deletion have special meaning - perhaps alternative, perhaps additional to the default. So how do I indicate that my class "is a set"? And how can I "pass it off" as a set in code which takes sets? – einpoklum Dec 29 '13 at 20:55
  • @einpoklum: yes, that is why you implement the same concepts and have your functions you pass our custom entities off to be implemented in terms of these concepts. In practise I find it rarely useful to implement function in terms of entirely arbitrary containers beyond being able to look at the sequence of objects which is neatly done in terms of iterators which are, of course, also just concepts (i.e., there is no iterator base class, at least, none which would be useful on its own). – Dietmar Kühl Dec 29 '13 at 21:00
  • 1
    @einpoklum You indicate that it's a set by naming and documenting it accordingly. You don't need to inherit from anything to pass it to code which takes sets: If that code really does take sets-the-concept (instead of set-the-concrete-class), it's templated in the set type. –  Dec 29 '13 at 21:00
  • @delnan: I don't understand your last comment. Do you suppose you could expand it into an answer? What does "templated in the set type" mean? Do you mean only the code in `` can be said to take sets-the-concept? – einpoklum Dec 29 '13 at 21:03
  • @einpoklum No. A function that takes a set doesn't look like this: `void foo(AbstractSet s) { ... }` because there is no such thing as an `AbstractSet`. Instead, it'll look like this: `template void foo(SetType s)`. This is in no way tied to ``, quite the contrary. –  Dec 29 '13 at 21:06
  • @einpoklum: What delnan means is that your code traveling in terms of a specific concept only uses the functionality required to be present to model this concept. You can view concepts as a form of duck typing (although it is not; just because you can apply all operations it doesn't mean it is the thing). – Dietmar Kühl Dec 29 '13 at 21:06
5

You need to try and let go of the Java mindset. You see, the beauty of STL, is that it separates algorithms from containers through iterators.

Long story short: Pass around iterators to your algorithms. Don't inherit.

Here are all the containers: http://en.cppreference.com/w/cpp/container

And here are all the algorithms: http://en.cppreference.com/w/cpp/algorithm

There may be two reasons why you may want to inherit:

  • You want to reuse implementation (bad idea)
  • Reuse existing algorithms by making a behavior available (e.g. inheriting from a base class like AbstractSet)

To briefly touch upon the first point, if you need to store an array of things (say an array of objects in a game scene), do exactly that, have an array of these objects as a member to the Scene object. There is no need to subclass to fully utilize the container. In other words, prefer composition over inheritance. This has been done to death already, and is accepted in the Java world as doing "The Right Thing". See discussion here, it's in the GoF book! Same thing applies to C++.

Example:

To address the second point let's consider a scenario. You are making a 2D sidescroller game, and you have a Scene object, with an array of GameObjects. These GameObjects have positions, and you'd like to sort them by position, and do binary search to find the closest object, as an example.

In the C++ mindset, the storage of elements and manipulation of containers are two separate things. The container classes provide the bare minimum functionality, for creation/insertion/removal. Anything interesting above that is relegated to Algorithms. And the bridge between them are iterators. The idea is that whether you use std::vector<GameObject> (equivalent to Java's ArrayList I think), or your own implementation is irrelevant as long as access to elements is the same. Here is a contrived example:

struct GameObject {
    float x, y;

    // compare just by x position
    operator < (GameObject const& other)
    {
        return x < other.x;
    }
};

void example() {
    std::vector<GameObject> objects = {
        GameObject{8, 2},
        GameObject{4, 3},
        GameObject{6, 1}
    };
    std::sort(std::begin(objects), std::end(objects));
    auto nearestObject = std::lower_bound(std::begin(objects), std::end(objects), GameObject{5, 12});

    // nearestObject should be pointing to GameObject{4,3};
}

Things to note here, the fact that I used std::vector to store my objects, doesn't matter as much as the fact I can perform random access on its elements. The iterators returned by the vector capture that. As a result we can sort and perform binary search.

The essence of the vector is random access to elements

We can swap out the vector for any other random access structure, without inheritance, and the code still works perfectly fine:

void example() {
    // using a raw array this time.
    GameObject objects[] = {
        GameObject{8, 2},
        GameObject{4, 3},
        GameObject{6, 1}
    };
    std::sort(std::begin(objects), std::end(objects));
    auto nearestObject = std::lower_bound(std::begin(objects), std::end(objects), GameObject{5, 12});

    // nearestObject should be pointing to GameObject{4,3};
}

For reference, see the functions I have used:

Why is this a valid alternative to inheritance?

This approach gives two orthogonal directions for extensibility:

  • New containers can be added, without inheritance, just by providing iterator access. All existing algorithms work.
  • New algorithms can be added. All containers supporting these iterators will work with these new algorithms, past, present or future.
Alexander Kondratskiy
  • 4,156
  • 2
  • 30
  • 51
  • Excuse my argumentative tone, but - surely, you jest! You're suggesting that I had the fact that my set is a set! How can that make sense? – einpoklum Dec 29 '13 at 20:58
  • @einpoklum: I don't think Alexander is jesting! The key thing to realize is that there are other forms of polymorphism than inheritance and generic programming is another form which is rooted in concepts. – Dietmar Kühl Dec 29 '13 at 21:09
  • "had the fact" -> "hide the fact". – einpoklum Dec 29 '13 at 21:12
  • @DietmarKühl: But I wanted to write object-oriented code in C++! You're telling me, essentially, that I can't. I have to make do with templated-oriented code with objects. – einpoklum Dec 29 '13 at 21:13
  • 2
    What is "object-oriented code"? People throw around that term without actually thinking about it. It usually means to them "everything is an object and there is lots of inheritance". What it should be is modularity, encapsulation, separation of concerns etc. Inheritance is just a tool. Just because you have an inheritance hammer, problems shouldn't all be nails. – Alexander Kondratskiy Dec 29 '13 at 21:19
  • 1
    @einpoklum: As I said: C++ isn't Java. You'd do things differently. Which doesn't mean that you need to use templates for everything. However, you'd use a custom interface suitable for your problem rather than a container interface which won't suit your problem. BTW, I'd consider generic programming as being object oriented - just not using dynamic polymorphism (yes, I realize that most people consider dynamic polymorphism the heart of object orientation). – Dietmar Kühl Dec 29 '13 at 21:20
  • @DietmarKühl I don't see the need to sell generic programming as OOP in disguise: It's perfectly fine as a separate/orthogornal paradigm (though of course all paradigms can be combined with one another). –  Dec 29 '13 at 21:23
  • @DietmarKühl, AlexanderKondratskiy: Object-Oriented as in "Meaningful and pervasive use of the concepts of objects, inheritance, polymorphism via subclassing." I know that's not quite a definition, just an aspect of it. But if I can't "say" something like "this class is a set, treat it that way please" - then I don't feel the language is object-oriented. – einpoklum Dec 29 '13 at 21:37
  • 1
    @einpoklum That's fine. If you don't feel that's it's object oriented, it doesn't stop it from solving problems differently (much more modularly in my opinion). If you're used to OOP, and are unwilling to look into a different way of solving a problem simply because you're uncomfortable, then that's a different story. Perhaps you should spend some time and understand what the C++ approach gives you, rather than dismiss it and regress to doing Java in C++. – Alexander Kondratskiy Dec 29 '13 at 21:46
  • @DietmarKühl: Also, this question and this answer underline how, at least in C++, OOP and generic programming are more opposed than orthogonal (i.e. \vector{OOP} \cdot \vector{generics} / (\norm{\vector{OOP}} \cdot \norm{\vector{generic}}) > 2^{-1/2} ) – einpoklum Jan 17 '14 at 16:00
3

The C++ standard library (note: it's not called the STL) has many existing container types: vector, array, deque, forward_list, list, set, map, multiset, multimap, unordered_set, unordered_map, unordered_multiset, unordered_multimap, stack, queue, priority_queue. Chances are, you just want to use one of these directly - you certainly never want to derive from them. However, it's certainly possible that you may need to implement your own special container type at some point, and it would be nice if it matched some interface, right?

But no, there aren't some abstract base classes that the containers derive from. However, the C++ standard provides requirements for types (sometimes known as concepts). For example, if you look at section §23.2 of the C++11 standard (or here), you'll find the requirements for a Container. For example, all containers must have a default constructor that creates an empty container in constant time. There are then more specific requirements for Sequence Containers (like std::vector) and Associative Containers (like std::map). You can code your classes to meet these requirements and then people can safely use your containers as they would expect to.

Of course, there are requirements for many things other than containers. For example, the standard provides requirements for different types of iterators, random number generators, and so on.


A number of people on the ISO C++ committee (Study Group 8, in fact) are looking into making these concepts a feature of the language. The proposal would allow you to specify requirements for types that need to be met for them to be used as template type arguments. For example, you would be able to write a template function a little like this:

template <Sequence_container C>
void foo(C container); // This will only accept sequence containers
// or even just:
void foo(Sequence_container container);

However, I'm thinking this is currently beyond your understanding of C++.

Joseph Mansfield
  • 108,238
  • 20
  • 242
  • 324
  • And are the standard containers - set, vector, map etc. - sort of minimally-compliant classes meeting those requirements? And if they are, is it reasonable to inherit them? – einpoklum Dec 29 '13 at 20:52
  • 2
    @einpoklum No, it's not reasonable to inherit them. They are fully-fledged containers. You should be *using* them, not inheriting from them, just like you wouldn't *inherit* an `ArrayList` in Java. – Joseph Mansfield Dec 29 '13 at 20:53
  • @einpoklum In addition to sftrabbit's point, they aren't even minimally compliant implementations of the concepts. For example, `std::vector` has a capacity while the concept makes no mention of that. –  Dec 29 '13 at 20:58
  • So how do I 'express' the fact that my container is, say, a sequential container? express the concept, if you will? I'm confused... – einpoklum Dec 29 '13 at 21:00
  • 2
    @Einpoklum You make sure your container meets the requirements and you state that it's a sequential container in the documentation. – Joseph Mansfield Dec 29 '13 at 21:01
  • @sftrabbit: I'd claim proper concepts are beyond the grasp of the people actually proposing concepts as they propose the wrong thing! Conceptually, you can't deduce whether a class implements a concept from its interface which is what the concept proposals (as well as earlier version thereof from the same source) is about. – Dietmar Kühl Dec 29 '13 at 21:03
  • @DietmarKühl Sure, there's certainly some amount of trust involved. But yes, the Concepts Lite proposal only checks syntactic requirements. – Joseph Mansfield Dec 29 '13 at 21:05
  • @sftrabbit: So, are you telling me to really just wait for C++14 before trying to express/implement concepts? Otherwise, what defines the requirements from a concept? Again, applying Java logic, I would "make sure my container meets the requirements" of a concept by inheriting an interface, i.e. a relevant pure-virtual base class. – einpoklum Dec 29 '13 at 21:08
  • @einpoklum: you can't use virtual functions to model concepts. For example, for a sequence `s` you'd have a `s.front()` method which returns a reference to an object of the sequence's type but there is no common base type (nor should there be). What sftrabbit says is that right now concepts are expressed in documentation only and that there is a proposal to add some form of expressing concepts in the language (I think it won't make it into C++14; I seem to recall that it went into a TS). However, concepts are used since C++98. They are just not expressed in C++. – Dietmar Kühl Dec 29 '13 at 21:12
  • @einpoklum Everything Dietmar Kühl said. And yeah, Concepts Lite has been moved into a Technical Specification to be published around the same time as C++14. – Joseph Mansfield Dec 29 '13 at 21:16
  • @DietmarKühl: Couldn't I get around the lack of a common base type with templates? If the sequence's type is T then s.front returns a T&. N'est pas? – einpoklum Dec 29 '13 at 21:18
  • @einpoklum: you could do some parts this way (`front()` does work; using a `virtual` function would be comparatively expensive, though). Other don't quite work, e.g., `s.insert(begin, end)` (you can attempt making it work but it won't be neither as efficient nor as flexible). – Dietmar Kühl Dec 29 '13 at 21:26
  • @DietmarKühl: Ah, whyever did I fall into the evil trap of this language? :-( – einpoklum Dec 29 '13 at 21:31
0

In C++, collections (aka containers) and generic algorithms that operate on them are implemented in a way that is completely unaware of inheritance. Instead, what connects them are iterators: For each container, specify which category of iterators it provides, for each algorithm, state which category of iterators it works with. So in a way, iterators 'bridge' the other two together and this is how STL affords to keep the number of containers and algorithms to the minimum (N+M instead of N*M). Containers are further defined as sequence containers (vector, deque, list (double linked list), or forward_list (singly linked list) and associative containers (map, set, hashmap, hashset, etc). Sequence containers are concerned with performance (i.e. which one is a better choice for a different situation). Associative containers are concerned with how things get stored in them and its consequence (binary tree vs hashed array). Similar ideas apply for algorithms. This is a gist of generic programming as exemplified by STL by being specifically and intentionally not object oriented. Indeed you would have to distort a pure OO approach to achieve smooth generic programming. Such a paradigm does not ride happily with languages such as Java or Smalltalk