Каково различие между двухсторонней очередью и списком контейнеры STL?
Обнуление только происходит для globals. Таким образом, если Ваш объект будет объявлен в глобальной области видимости, то ее участники будут обнулены:
class Blah
{
public:
int x;
int y;
};
Blah global;
int main(int argc, char **argv) {
Blah local;
cout<<global.x<<endl; // will be 0
cout<<local.x<<endl; // will be random
}
5 ответов
Из (датированной, но все еще очень полезной) SGI STL сводки deque :
Двухсторонняя очередь очень похожа на вектор: как вектор, это последовательность, которая поддерживает произвольный доступ к элементам, постоянное время вставки и удаления элементов в конце последовательности, а также линейную временную вставку и удаление элементов в середине.
Основной способ, которым deque отличается от vector заключается в том, что deque также поддерживает постоянную вставку и удаление элементов в начале последовательности. Кроме того, deque не имеет никаких функций-членов, аналогичных функциям vector capacity () и reserve (), и не предоставляет никаких гарантий правильности итератора, связанных с этими функциями-членами.
Вот сводка по списку . с того же сайта:
Список - это двусвязный список. То есть это Последовательность, которая поддерживает как прямой, так и обратный обход, а также (амортизированную) вставку и удаление элементов с постоянным временем в начале, в конце или в середине. Списки имеют важное свойство: вставка и сращивание не делают недействительными итераторы для элементов списка, и даже удаление делает недействительными только итераторы, указывающие на удаляемые элементы. Порядок итераторов может быть изменен (то есть у list :: iterator может быть другой предшественник или преемник после операции со списком, чем раньше), но сами итераторы не будут аннулированы или сделаны так, чтобы указывать на другие элементы, если это недействительность или мутация явная.
Таким образом, контейнеры могут иметь общие процедуры, но гарантии времени для этих процедур различаются от контейнера к контейнеру . Это очень важно при рассмотрении того, какой из этих контейнеров использовать для задачи: принимая во внимание , как контейнер будет использоваться наиболее часто (например, больше для поиска, чем для вставки / удаления) имеет большое значение в направляет вас к нужному контейнеру.
Позвольте мне перечислить различия:
- Deque управляет своими элементами с помощью динамический массив , предоставляет случайный доступ , и имеет почти такой же интерфейс как вектор.
- Список управляет своими элементами как двусвязный список и не предоставить произвольный доступ .
- Deque обеспечивает быструю вставку и удаление в и конец, и начало. Вставка и удаление элементов в середина относительно медленная, потому что все элементы до любого из обоих концы могут быть перемещены, чтобы освободить место или заполните пробел.
- В List вставка и удаление элементов выполняется быстро в каждой позиции, включая оба конца.
- Deque : Любая вставка или удаление элементов кроме начала или конца делает недействительными все указатели, ссылки, и итераторы, которые относятся к элементам двухсторонней очереди.
- Список : при вставке и удалении элементов не аннулировать указатели, ссылки, и итераторы к другим элементам.
Сложность
Insert/erase at the beginning in middle at the end
Deque: Amortized constant Linear Amortized constant
List: Constant Constant Constant
std :: list по сути является двусвязным списком.
std :: deque , с другой стороны, реализован больше как std :: вектор . Он имеет постоянное время доступа по индексу, а также возможность вставки и удаления в начале и в конце, что обеспечивает резко отличающиеся характеристики производительности от списка.
Нет. Двусторонняя очередь поддерживает только вставку и удаление O (1) спереди и сзади. Это может быть, например, реализовано в векторе с циклическим переходом. Поскольку он также гарантирует произвольный доступ O (1), вы можете быть уверены, что это '
The performance differences have been explained well by others. I just wanted to add that similar or even identical interfaces are common in object-oriented programming -- part of the general methodology of writing object-oriented software. You should IN NO WAY assume that two classes work the same way simply because they implement the same interface, any more than you should assume that a horse works like a dog because they both implement attack() and make_noise().