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

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:

• std::sort
• std::lower_bound

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.

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

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

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

Since there's currently a bounty asking what's new in this area in C++20... The answer is "not much."

The STL Way Of Doing Things remains static polymorphism, not inheritance. The STL doesn't provide any kind of "BaseContainer" for your new container to derive from. Instead, it specifies a bunch of syntactic and semantic requirements, which your new container must conform to.

The classical-OOP-inheritance approach is:

struct BaseContainer { virtual void push_back(Object) = 0; virtual BaseIterator begin() = 0; virtual BaseIterator end() = 0; virtual ~BaseContainer() = default; }; void sort(BaseContainer& ctr) { ~~~~ ctr.begin(); ~~~~ } 

But that's not what the STL does. The STL uses templates:

// NOTA BENE: To instantiate this `sort` template, you must pass it // a `ctr` such that `ctr.begin()` and `ctr.end()` are well-formed // expressions that return iterators, and `ctr.end()` is reachable // by repeatedly incrementing from `ctr.begin()`. ~~~~ template<class Container> void sort(Container& ctr) { ~~~~ auto it = ctr.begin(); ~~~~ } 

Starting in C++20, the language does provide a nice syntax for encoding part of that comment into compiler-readable C++. The syntax is called a requires-expression.

template<class Container> void sort(Container& ctr) requires requires { { ctr.begin() }; { ctr.end() }; } { ~~~~ auto it = ctr.begin(); ~~~~ } 

This encodes the syntactic requirement that ctr.begin() and ctr.end() must both be well-formed expressions. (Of course, that requirement was already encoded implicitly in the body of the function template. If you passed a ctr such that ctr.begin() wasn't well-formed, the function would refuse to compile. But now it refuses even to participate in overload resolution, which is, uh, different.)

There remains no way to encode semantic requirements in C++ — obviously, as the syntax of a programming language can only ever encode syntactic requirements. (The history of programming languages is the history of figuring out how to constrain things such that semantics becomes expressible in syntax.)

Pre-C++20 (and also post-C++20), C++ specifies the notion of "iterator requirements." For example, in order for it to meet the iterator requirements, it must be the case that

++it; 

is a well-formed expression and returns a reference to it itself. The former is a syntactic requirement; the latter is a semantic requirement.

(Nit: Technically it's legal for ++it to return a reference to some other iterator, instead of to it, and it'll still meet the Cpp17InputIterator requirements (although not the Cpp17ForwardIterator requirements). I don't know if that's an oversight or what.)

Starting in C++20, the syntactic requirements are formalized in named concepts such as std::input_iterator and std::forward_iterator. The semantic requirements aren't expressed in those concepts (being semantic, they can't be), but the Standard does, on paper, associate a list of semantic requirements with each named concept, and basically says that if your type satisfies the syntactic requirements of a named concept without also modeling the semantic requirements, then all bets are off: the library is allowed to assume that any type satisfying input_iterator also models the semantic requirements of input_iterator, and so on.

So it is reasonably correct to say that C++20 changes the game with respect to writing your own iterator types. You can write your type like

struct MyIterator { ~~~~ }; 

and then add a simple assertion at the end of the class definition:

static_assert(std::forward_iterator<MyIterator>); 

and if that assertion passes, then you know your type is "iterator-ish enough" for every piece of client code in the STL.

(Of course in practice that's not true at all. You can write an iterator that works with C++20 ranges::sort but fails with C++17 std::sort, or vice versa. You can write an iterator that satisfies std::forward_iterator's syntactic requirements but accidentally fails to model the semantic requirements — like, maybe you reversed the sense of its operator==. And so on. But still, C++20's named concepts are really a big step forward compared to what C++17 gave you.)

But: C++20 doesn't add named concepts for "containers" at all! The situation for containers in C++20 (and C++23/26) is still the status quo ante: there's a big table of "container requirements" in the Standard, but there is no named concept (say, "std::container") that encodes all of those requirements into a requires-expression. Nor, really, could there be — because different containers (unlike different iterators) support different operations. vector lacks push_front. deque lacks capacity. forward_list even lacks size!

So if you want to write a concept expressing the syntactic requirements of a "container," you'll have to do it yourself — and it still probably won't capture everything that's the same about all STL containers. Let alone the semantics, which are impossible to capture in code, and would have to be expressed through documentation. (For example, "After calling v.clear(), the value of v.size() must be zero.")

TL;DR — the answer to your question hasn't changed in the past ten years. That answer is that you don't derive from some kind of ContainerBase; instead, you write your own type from scratch, and then manually compare its functionality against the Standard's paper list of container requirements to see if you've correctly modeled them all.

But if you just want to check that your type correctly satisfies the syntactic requirements of a C++20 range, that turns out to be easy, because there's a named concept for that:

static_assert(std::ranges::range<MyContainerType>);