Abstracting containers in C++

Question

I would like to have a virtual base class (interface) that contains a method that returns an iterable object (a container?). The implementing classes would each handle their containers themselves, for example, class A would implement the container as a vector, class B as a list, etc.

Essentially, I would like to do something like this:

class Base{
  virtual Container getContainer() = 0;
}

class A:Base{
  Vector v;
  Container getContainer() {return v;}
}

A a;
Iterator begin = a.getContainer().begin;
Iterator end = a.getContainer().end;

As in, the caller will be responsible for handling the iterator (calling the begin and end functions for iteration for example)

I assume something like this is possible, but I can't figure out how to do it. Specifically, I assume classes like vector and list inherit from a common interface that defines methods begin() and end(), but I can't figure out what that interface is, and how to handle it.

Check out https://stackoverflow.com/questions/22350712/design-a-base-iterator-for-a-base-class or https://softwareengineering.stackexchange.com/questions/386614/c-iterator-why-is-there-no-iterator-base-class-all-iterators-inherit-from — Fruchtzwerg, Nov 21 '21 at 13:47
You can't abstract the standard containers in that way, since they do not have a common base class. The specification of containers is based on each providing an interface (e.g. a particular set of member functions) but, although there are some common elements in all interfaces, different containers don't have the same interface - and there is no common base class that standard containers (in the c++ standard library) and user-defined containers need to inherit from. — Peter, Nov 21 '21 at 14:04

score 1 · Answer 1 · answered Nov 21 '21 at 13:50

Check out cppreference.com. This common interface is only a convention and some rules, not actual C++ types. So no, you can't use containers polymorphically. The simple reason is efficiency, runtime polymorphism costs performance. For a more detailed insight, there are many documents concerning the design ideas behind the STL, which is reflected there.

If you really want to implement this, not only would you need wrapper classes around the STL-style sequence containers (deque, vector, list, array), but also around the iterators. Iterators are usually hard-tied to the containers, hence this connection. The wrapper classes will also have to provide the various methods you'd find in the underlying containers, like e.g. begin(), end(), size() etc.

Note that not every container supports all methods. For example, some don't support push_front() but only push_back(). All of them have begin() and end(), but a singly-linked list (not currently part of C++) can't have rbegin() and rend(). You could sort those categories into separate pure virtual baseclasses.

Overall, I'd doubt the usefulness of this. If you want to swap implementations, design your code so that the container becomes a template parameter to it. All calls are then resolved at compile time, leading to less code, less memory requirements and more performance.

score 1 · Answer 2 · answered Nov 21 '21 at 13:59

Containers are not polymorphic. There is no common base class. The same is true of iterators.

This is intentional, because iterating element by element turns out to be highly inefficient when done through a virtual method based interface. It can be done, but it is slow.

Boost has any ranges and any iterators, or you can roll your own vis type erasure techniques. I advise against it.

The simplest and cheapest way to get iteration polymorphic is adding a foreach_element(std::function<void(Element const&)>)const method. You can batch up the iteration to reduce overhead with foreach_element(std::function<void(std::span<Element const>)>)const, allowing elements to be clumped by the container. That would be easy to write and faster than fully polymorphic iterators and containers.

Abstracting containers in C++

2 Answers2