Почему в DinkumSTL в stack по-умолчанию используется deque, а не vector?

Здравствуйте, Аноним, Вы писали:

А>Почему в DinkumSTL в stack по-умолчанию используется deque, а не vector?
а что тебя удивляет? в STL с VC7.1 тоже по умолчанию deque

> Почему в DinkumSTL в stack по-умолчанию используется deque, а не vector?

Потому что так написано в спецификации. В спецификации так написано, т.к.
std::deque -- контейнер, поддерживающий константное время при вставке/удалении
элементов в конце/начале последовательности. Кроме того, при вставке/удалении
элементов в конце/начале std::deque, ссылки на остальные элементы не инвалидируются.

Здравствуйте, Павел Кузнецов, Вы писали:

>> Почему в DinkumSTL в stack по-умолчанию используется deque, а не vector?

ПК>Потому что так написано в спецификации. В спецификации так написано, т.к.
ПК>std::deque -- контейнер, поддерживающий константное время при вставке/удалении
ПК>элементов в конце/начале последовательности. Кроме того, при вставке/удалении
ПК>элементов в конце/начале std::deque, ссылки на остальные элементы не инвалидируются.

Разве stack вставляет/удаляет в начале последовательности?
Там вроде операции push/pop и полного доступа к контейнеру нет...

ПК>> т.к. std::deque -- контейнер, поддерживающий константное время при
ПК>> вставке/удалении элементов в конце/начале последовательности. Кроме
ПК>> того, при вставке/удалении элементов в конце/начале std::deque, ссылки
ПК>> на остальные элементы не инвалидируются.

> Разве stack вставляет/удаляет в начале последовательности?

В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает возможности
вставки элемента в т.ч. и в конец последовательности за константное время,
плюс инвалидирует ссылки на элементы. Эффективная вставка/удаление в начало
важны для std::queue.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает возможности
ПК>вставки элемента в т.ч. и в конец последовательности за константное время,
ПК>плюс инвалидирует ссылки на элементы. Эффективная вставка/удаление в начало
ПК>важны для std::queue.

... В Джосьютесе прочитал, что vector тоже обеспечивает амортизированное время вставки в конец, как и deque. Кроме этого скорость доступа к элементам в deque чуть медленнее.
А ссылки на элементы инвалидируются точно также, как и у vector... (с)Джосьютис... хм.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Павел Кузнецов, Вы писали:

ПК>>В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает возможности
ПК>>вставки элемента в т.ч. и в конец последовательности за константное время,
ПК>>плюс инвалидирует ссылки на элементы. Эффективная вставка/удаление в начало
ПК>>важны для std::queue.

А>... В Джосьютесе прочитал, что vector тоже обеспечивает амортизированное время вставки в конец, как и deque. Кроме этого скорость доступа к элементам в deque чуть медленнее.

Ключевое слово здесь — амортизированное. То есть, немного упрощая, для vector в среднем сложность вставки в конец O(1), а для deque в худшем случае O(1). Ну а скорость конечно зависит от реализации, но обычно в deque в среднем операция добавления медленнее, чем в vector.

А>А ссылки на элементы инвалидируются точно также, как и у vector... (с)Джосьютис... хм.

An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

Для вектора такой гарантии нет.

Здравствуйте, Аноним, Вы писали:

А>Почему в DinkumSTL в stack по-умолчанию используется deque, а не vector?

В какой-то книжке приводили пример: если надо скопировать один стек в другой, то с деками эта процедура реализуется гораздо проще, тк можно вставлять в начало. А с векторами пришлось бы делать дополнительные операции.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>>> т.к. std::deque -- контейнер, поддерживающий константное время при
ПК>>> вставке/удалении элементов в конце/начале последовательности. Кроме
ПК>>> того, при вставке/удалении элементов в конце/начале std::deque, ссылки
ПК>>> на остальные элементы не инвалидируются.

>> Разве stack вставляет/удаляет в начале последовательности?

ПК>В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает возможности
ПК>вставки элемента в т.ч. и в конец последовательности за константное время,
ПК>плюс инвалидирует ссылки на элементы. Эффективная вставка/удаление в начало
ПК>важны для std::queue.

А зачем для std::queue вставка в начало? В любом случае и std::stack и std::queue имеют операции добавления элементов только с одной стороны и это может быть конец, а не начало.

Здравствуйте, <Аноним>, Вы писали:

А>... В Джосьютесе прочитал, что vector тоже обеспечивает амортизированное время вставки в конец, как и deque. Кроме этого скорость доступа к элементам в deque чуть медленнее.
А>А ссылки на элементы инвалидируются точно также, как и у vector... (с)Джосьютис... хм.
Бедный Коля Йосутиз.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Павел Кузнецов, Вы писали:

ПК>>В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает возможности
ПК>>вставки элемента в т.ч. и в конец последовательности за константное время,
ПК>>плюс инвалидирует ссылки на элементы. Эффективная вставка/удаление в начало
ПК>>важны для std::queue.

А>... В Джосьютесе прочитал, что vector тоже обеспечивает амортизированное время вставки в конец, как и deque. Кроме этого скорость доступа к элементам в deque чуть медленнее.
А>А ссылки на элементы инвалидируются точно также, как и у vector... (с)Джосьютис... хм.

Во-первых, у вектора амортизированное, а у дека всегда единичное.
Во-вторых, стек обращается только к концевому элементу, а у дека эта операция (в отличие от произвольного доступа) быстрая.
В-третьих, не инвалидируются — либо Джосьютис оговорился, либо ты не так понял.

Стандарт 1998: 23.2.1.3:1

An insert in the middle of the deque invalidates all the iterators and references to elements of the deque.
An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

Про время операции — см. там же рядом.

Tom,

??>>> Разве stack вставляет/удаляет в начале последовательности?

ПК>> В конце. Скажем, вектор, в отличие от std::deque, не обеспечивает
ПК>> возможности вставки элемента в т.ч. и в конец последовательности за
ПК>> константное время, плюс инвалидирует ссылки на элементы. Эффективная
ПК>> вставка/удаление в начало важны для std::queue.

T> А зачем для std::queue вставка в начало? В любом случае и std::stack и
T> std::queue имеют операции добавления элементов только с одной стороны и
T> это может быть конец, а не начало.

Как ни поверни, для std::queue элементы будут добавляться с одного конца, а
удаляться -- с другого. Т.е. если вставка будет производиться в начало, то
удаление -- из конца, если вставка -- в конец, то удаление -- из начала. Для
std::deque обе операции производятся за константное время, и не инвалидируют
ссылки, а удаление еще и оставляет валидными итераторы. Для std::vector
единственная операция (из упомянутых), производящаяся за константное время,
и не инвалидирующая ссылки на существующие элементы -- удаление из конца.

P.S.

ПК> Как ни поверни, для std::queue элементы будут добавляться с одного конца,
ПК> а удаляться -- с другого. Т.е. если вставка будет производиться в начало,
ПК> то удаление -- из конца, если вставка -- в конец, то удаление -- из начала.

Перечитав, заметил, что данный фрагмент можно понять так, как будто выбор
куда добавлять, и откуда удалять -- произволен. В общем случае это так, но,
в случае std::queue, выбор уже сделан: добавление производится в конец,
удаление -- из начала.

ПК>Перечитав, заметил, что данный фрагмент можно понять так, как будто выбор
ПК>куда добавлять, и откуда удалять -- произволен. В общем случае это так, но,
ПК>в случае std::queue, выбор уже сделан: добавление производится в конец,
ПК>удаление -- из начала.

Да, с очередью ещё более менее понятно, но автор то говорит про стек. Вот тут выбор по умолчанию в сторону дэки вовсе не понятен.

Tom>Да, с очередью ещё более менее понятно, но автор то говорит про стек. Вот тут выбор по умолчанию в сторону дэки вовсе не понятен.

OK. Ниже реализация std::stack из MSVC 7.1 (немного подчищенная):

template<class T, class Container = std::deque<T> >
class stack
{
public:
    typedef Container container_type;
    typedef typename Container::value_type value_type;
    typedef typename Container::size_type size_type;

    stack() : c_()   { }

    explicit stack(const Container& c) : c_(c) {}

    bool empty() const              { return c_.empty(); }

    size_type size() const          { return c_.size(); }

    value_type& top()               { return c_.back(); }

    const value_type& top() const   { return c_.back(); }

    void push(const value_type& x)  { c_.push_back(x); }

    void pop()                      { c_.pop_back(); }

    Container c_;
};

Сразу договоримся, что мы рассматриваем реализацию по умолчанию — т.е. ту, которая должна работать наиболее оптимально в большинстве случаев использования (одна из основных идей в STL).

Итак чем deque лучше vector-а в данном контексте:
1) Как уже не однократно говорили, он обеспечивает константное время вставки удаления (push_back()/pop_back()). vector (по умолчанию) такого гарантировать не может.
2) Ссылки на элементы контейнера не инвалидируются при вставке нового элемента (тоже говорили). Посмотрите на имплементацию метода top(), который именно ссылки и возвращает.
3) deque обходится с памятью более экономно чем vector.
4) vector<bool> в STL — не вектор и храняться в нем не bool. stack<bool> (основанный на векторе), был бы не тем, что вы ожидаете.

Возможно что-то еще забыл.

Но в целом, почитайте как устроен vector и как устроен deque (размещение в памяти/работа push_back()). Все сразу встанет на свои места.
Способность добавлять к deque элементы с другого конца, в данном случае никакой роли не играет.

--
Stas