4

Подскажите как правильно реализовать на С++ контейнер, который одновременно может работать как вектор (список), LIFO-стек и FIFO-очередь, максимально используя фичи STL "из коробки" ?

Применение: хочу универсальный тип-контейнер, который может не только хранить вложенные структуры (пока справляется class Obj { string val; vector<Obj*> nested; }), но и уметь специфичные для каждого перечисленного контейнера фичи одновременно:

  • vector: произвольное чтение/вставка/замена по индексу
  • stack: push/pop
  • queue: put/get

2 ответа 2

6

deque - он же double-ended queue

Поддерживает все, что вы перечислили. Названия функций-членов немного не такие, но это, думаю, не принципиально :) push_back, push_front - вставка с любого конца, pop_back, pop_front - снятие.

Словом, смотрите более детальное описание.

1

В стандарте C++ такие абстрактные типы данных, как стек, очередь и приоритетная очередь, определены как адаптеры других контейнеров. По умолчанию таким базовым контейнером является стандартный контейнер std::deque. Вы можете также использовать стандартный контейнер std::list, который реализует все необходимые операции для стека и очереди, но у него отсутствует прямой доступ к элементам.

5
  • Кстати, а не подскажете, можно ли как-то прикрутить к одному контейнеру два адаптера, раз уж они все равно адаптеры? В описаниях написано, что они контейнеры копируют в себя, а просто передать как ссылку нельзя?
    – Mikhajlo
    Commented 4 дек. 2016 в 13:23
  • @Mikhailo Когда вы инициализируете, например, стек выбранным контейнером с помощью конструктора explicit stack(const Container&);, то стек создает свою собственную копию этого контейнера. Поэтому если вы хотите, чтобы стек своими операциями изменял исходный контейнер, вам надо создать "обертку" вокруг этого контейнера, которая будет содержать ссылку на контейнер, и передавать в конструктор стека эту обертку. Commented 4 дек. 2016 в 13:42
  • @Mikhailo Но так как базовые контейнеры имеют все те операции, которые нужны стеку (стек просто переименовывает некоторые операции базового конейнера: например, если в базовом контейнере имеется операция push_front, то стек ее переименовывает в push), то вам даже нет необходимости работать с адаптерами контейнеров такими, как стек. Вы просто можете рассматривать исходный базовый контейнер как стек. Commented 4 дек. 2016 в 13:44
  • Ну, я подумал было, что адаптер - это просто функции для работы со стеком или очередью, которые просто вызывают функции дека. И тогда можно было бы иметь и стек, и очередь на одном объекте. Но сейчас мне кажется, что тогда это будет неправильный стек, и неправильная очередь, потому что не смогут гарантировать, например, что сколько в стек вошло, столько и вышло.
    – Mikhajlo
    Commented 4 дек. 2016 в 17:08
  • @Mikhailo Адаптер - это адаптер существующего стандартного контейнера, некоторый класс, который просто на основе имеющихся методов базового контейнера определяет свои методы, то есть, фактически, просто переименовывает некоторые методы базового контейнера. Например, в базовом контейнере есть метод front, а стек его переименовывает в метод top. Commented 4 дек. 2016 в 17:30

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.