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.

12
  • 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.
    – user395760
    Dec 29, 2013 at 20:50
  • 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<T>::value) { /* do something with iterators */ }.
    – user395760
    Dec 29, 2013 at 21:08
  • 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.
    – user395760
    Dec 29, 2013 at 21:15
  • 3
    This may be an interesting read for you: stackoverflow.com/questions/1039853/… Dec 29, 2013 at 21:17
  • 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.
    – user395760
    Dec 29, 2013 at 21:35

5 Answers 5

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>{});
8
  • 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, 2014 at 15:54
  • 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.
    – mrr
    Jan 18, 2014 at 4:16
  • 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++.
    – mrr
    Jan 20, 2014 at 11:22
  • 1
    Why do you want to write a function which takes a set?
    – mrr
    Jan 20, 2014 at 11:26
  • 4
    I believe this thread is becoming unnecessarily acrimonious and counter-productive.
    – einpoklum
    Jan 20, 2014 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++.

6
  • 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, 2013 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). Dec 29, 2013 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.
    – user395760
    Dec 29, 2013 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 <set> can be said to take sets-the-concept?
    – einpoklum
    Dec 29, 2013 at 21:03
  • @einpoklum No. A function that takes a set doesn't look like this: void foo(AbstractSet<int> s) { ... } because there is no such thing as an AbstractSet. Instead, it'll look like this: template <typename SetType> void foo(SetType s). This is in no way tied to <set>, quite the contrary.
    – user395760
    Dec 29, 2013 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.
10
  • 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, 2013 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. Dec 29, 2013 at 21:09
  • 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. Dec 29, 2013 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). Dec 29, 2013 at 21:20
  • 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++. Dec 29, 2013 at 21:46
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++.

13
  • 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, 2013 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. Dec 29, 2013 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.
    – user395760
    Dec 29, 2013 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, 2013 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. Dec 29, 2013 at 21:01
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.