Tell me how to properly implement a C ++ container that can simultaneously work as a vector (list), a LIFO stack and a FIFO queue, making maximum use of the STL features out of the box?

Application: I want a universal container type that can not only store nested structures (while the class Obj { string val; vector<Obj*> nested; } manages), but also to know the features specific to each listed container at the same time :

  • vector: arbitrary read / insert / replace by index
  • stack: push / pop
  • queue: put / get

    2 answers 2

    deque - it's double-ended queue

    Supports everything you listed. The names of the member functions are a little different, but this, I think, is not important :) push_back , push_front - insertion from any end, pop_back , pop_front - removal.

    In a word, see a more detailed description .

      In the C ++ standard, such abstract data types as stack, queue, and priority queue are defined as adapters of other containers. By default, this base container is the standard std::deque container. You can also use the standard container std::list , which implements all the necessary operations for the stack and the queue, but it does not have direct access to the elements.

      • By the way, and do not tell me, is it possible to somehow tie two adapters to one container, since they are still adapters? The descriptions say that they are copying containers into themselves, but it is impossible to simply transfer them as a link? - Mikhailo
      • @Mikhailo When you initialize, for example, the stack with the selected container using the explicit stack (const Container &); constructor, the stack creates its own copy of this container. Therefore, if you want your operations to change the stack of the original container, you need to create a “wrapper” around this container, which will contain a reference to the container, and transfer this wrapper to the stack constructor. - Vlad from Moscow
      • @Mikhailo But since the base containers have all the operations that the stack needs (the stack simply renames some operations of the base container: for example, if the base container has a push_front operation, then the stack renames it push), you don't even need to work with adapters containers such as stack. You can simply treat the original base container as a stack. - Vlad from Moscow
      • Well, I thought that the adapter was just functions for working with a stack or a queue that simply called the deck functions. And then it would be possible to have both the stack and the queue on the same object. But now it seems to me that then it will be the wrong stack, and the wrong queue, because they cannot guarantee, for example, how many went on the stack, so much has gone. - Mikhailo
      • The @Mikhailo Adapter is an adapter of an existing standard container, some class that simply defines its methods based on the base container's existing methods, that is, in fact, simply renames some methods of the base container. For example, the base container has a front method, and the stack renames it the top method. - Vlad from Moscow