What is the C++ equivalent of inheriting a Java collection interface (Set, Map, List etc.)? Or extending AbstractCollection?

Question

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.

Answer 1

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>{});

Answer 2

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++.