-1

I'm trying to make a doubly linked list in C++, and I'm trying to do it right. Therefore, I thought I should adhere to any interface structure recommended by any "official" C++ guideline, such as an interface. In Java, there are such interfaces which one is free to use and which sort of standardise abstract data types (such as https://docs.oracle.com/javase/8/docs/api/java/util/List.html).

My question: Is there anything like this in C++? Startpageing found me this link:

https://en.cppreference.com/w/cpp/container/list

But it doesn't seem to use any inheritance.

AlgebraicsAnonymous
  • 179
  • 8
  • 6
    Most of the standard library does not use polymorphism (interfaces). Instead, most sections just have a [list of requirements](https://timsong-cpp.github.io/cppwp/container.requirements) that the implementation must adhere to. – NathanOliver Sep 16 '21 at 14:50
  • 2
    maybe what corresponds to it in C++ is duck typing, which is almost the opposite of having an abstract interface as you do in Java. – 463035818_is_not_an_ai Sep 16 '21 at 14:50
  • 4
    Almost none of the structures defined in standard use inheritance, because it's an unnecessary runtime cost. What you would be expected to do is to implement all the same functions that `std::list` has and then it can be used interchangeably with the original one in templates for example. – Yksisarvinen Sep 16 '21 at 14:51
  • 1
    C++20, incidentally, does use concepts, which are similar in spirit. And I have to somewhat object to the notion that C++ fails to use polymorphism. C++ (pre-20) doesn't use Java-style interfaces, but to claim that C++ has no polymorphism is nearsighted. The language has templates, virtual functions, and overloaded functions. – Silvio Mayolo Sep 16 '21 at 14:52
  • 3
    See also [Why is the C++ STL is so heavily based on templates? (and not on *interfaces*)](https://stackoverflow.com/questions/1039853/why-is-the-c-stl-is-so-heavily-based-on-templates-and-not-on-interfaces) – Richard Critten Sep 16 '21 at 14:52
  • @SilvioMayolo the standard library doesn't use polymorphism for containers, thats what OP is asking for. Of course you can write containers that rely on polymorphism also in C++ – 463035818_is_not_an_ai Sep 16 '21 at 14:53
  • 1
    In C++ there's container adapters, such as `std::queue` which implements a common interface... for a queue. `std::deque`, `std::vector`, `std::list`... Shove it into an `std::queue` and it just works. Barring performance diferences of each. Maybe what you want is closer to C++20 [`concepts` and `requires`](https://en.cppreference.com/w/cpp/language/constraints)? That's relatively new, but powerful, and may achieve what you want to do. There's also `std::span` for sequences of various types that's similar to `std::string_view`, but for arbitrary types. – Kaihaku Sep 16 '21 at 14:56
  • Java's collection hierarchy is broken, and frequently ignores the "abstract" part of "abstract data type". It was created during the worst object-obsessive craze of the late twentieth century, and is not a good reference model. – molbdnilo Sep 16 '21 at 15:15
  • Separation of concerns. Why should a container know or care that it's contents are polymorphic? Its job is to hold stuff, and the less it knows about what it holds, the simpler the code is going to be. – user4581301 Sep 16 '21 at 15:30
  • I bet that in a later version of Java, they will add some sort of syntax changes to the language to allow generic containers and duck-typing, similar to C++. That would make everything much simpler. Java did similar to emulate, as best as possible, deterministic destruction using try-with-resources when Java programmers were complaining about the lack of RAII, but the implementation (IMO) is poor/clumsy compared to what comes naturally in C++. – PaulMcKenzie Sep 16 '21 at 16:09

3 Answers3

5

The standard library is designed in a way to avoid needing such inheritance in the first place.

More often than not, you can get essentially the same behavior as interfaces, without any of the runtime overhead of indirect calls, by duck-typing on the container type:

#include <vector>
#include <list>
#include <iostream>

template<typename Collection>
void do_something(const Collection& data) {
  for(const auto& v : data) {
     std::cout << v << "\n";
  }
}

int main() {
  std::vector<int> a;
  std::list<int> b;

  do_something(a);
  do_something(b);
}

If you are approaching this from a Java perspective, you can think of it as being "generics on steroids", where a function can generically accept anything that looks like a collection.

There are a few other approaches possible involving iterators and ranges, but the principles remain the same.

  • 2
    Because the concept has come up a few times in the comments and answers, [Wikipedia page on Duck Typing](https://en.wikipedia.org/wiki/Duck_typing). – user4581301 Sep 16 '21 at 15:26
2

Is there anything like this in C++?

Depends on what level of similarity you're looking for and where you're looking for it.

The Java collection interfaces are based on runtime polymorphism. In C++ terms, such API is based on inheritance and virtual member functions.

The containers provided by the standard library serve a similar function as the collections in Java. However, they do not provide an API based on inheritance and virtual member functions. Instead, their API is based on compile time polymorphism i.e. templates which are somewhat similar to generics in Java. In the analogy of Java collections and C++ standard containers, the concepts aka named requirements specified in the standard are analogous to the interfaces in Java.

It is possible to implement interfaces - such as they are in Java - in C++. The C++ equivalents are simply abstract classes with no non-pure member functions. You must use virtual inheritance in order to share bases in the way that you can share interfaces in Java. It is also possible to implement a container API based on runtime polymorphism. But such container API is not provided by the standard library.

I'm trying to make a doubly linked list in C++

Other than for exercise purposes you rarely need to, because the standard library already comes with an implementation of double linked list. It's the std::list whose reference page you've linked in the question.

and I'm trying to do it right.

"Right" is relative, but you'll likely do fine by copying what the standard library does.

If you do wish to follow the example shown by the standard library, then you should provide an API based on concepts (aka named requirements) and templates. Your class (template) should conform to the Container concept, and more specifically the SequenceContainer concept.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • Actually there are some reasons why one would like to make one's own doubly linked lists. First of all, I want the computer to go leftward when looking for an element with index > length/2, and then I want the size to be an mpz_t, so that the program is robust for when we discover an infinitude of alternate universes, allowing for really big lists (OK I just want to familiarise myself with the GNU MP, I'll admit it). – AlgebraicsAnonymous Sep 16 '21 at 15:16
  • @AlgebraicsAnonymous Fair enough. I amended the wording of the answer. – eerorika Sep 16 '21 at 15:18
0

In C++, you can implement it as your own interface (keep in mind to add public before the actual implementation).

To make a great job, you can define your own abstract methods in you own abstract class, like:

class ExampleAbstractClass {
   public:
      virtual string myFunction() = "To be implemented";
   
      void notAbstractMethod(int aNumber) {
         aNumber = h;
      }
   
   protected:
      int aNumber;
};

class ExapleClass: public ExampleAbstractClass{
   // abstract implementation
   public:
      string myFunction() { 
         return "That's now customly implemented!"; 
      }
}
Adrian Mole
  • 49,934
  • 160
  • 51
  • 83
Tia
  • 44
  • 2