Форум программистов, компьютерный форум CyberForum.ru

Разница между list и vector? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Mar-12
 Аватар для Mar-12
-21 / 5 / 1
Регистрация: 14.03.2013
Сообщений: 131
25.05.2013, 17:45     Разница между list и vector? #1
Разница между list и vector?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2013, 17:45     Разница между list и vector?
Посмотрите здесь:

C++ STL vector,list
C++ Разница между list и vector
C++ vector, list, deque
C++ vector и list
C++ Контейнеры Vector и List (C++)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11824 / 6803 / 769
Регистрация: 27.09.2012
Сообщений: 16,871
Записей в блоге: 2
Завершенные тесты: 1
25.05.2013, 17:46     Разница между list и vector? #2
list - это двусвязный список.
vector - это своего рода динамической массив
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
25.05.2013, 17:48     Разница между list и vector? #3
У list нету перегруженного operator[]
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11824 / 6803 / 769
Регистрация: 27.09.2012
Сообщений: 16,871
Записей в блоге: 2
Завершенные тесты: 1
25.05.2013, 17:53     Разница между list и vector? #4
Что касается реализации, то они так же предоставляют разные типы итераторов.
У листа нет capacity ну и сопутствующего функционала.

Добавлено через 2 минуты
Зато есть push_front, pop_front
Убежденный
Системный программист
 Аватар для Убежденный
14191 / 6206 / 985
Регистрация: 02.05.2013
Сообщений: 10,339
Завершенные тесты: 1
25.05.2013, 18:02     Разница между list и vector? #5
Если по-простому:

list - связный список.
Реализован как последовательность элементов с указателями, ссылающимися друг
на друга, из-за этого вставка и удаление элементов в любом месте выполняются за
постоянное и относительно небольшое время, а вот доступ к произвольным элементам
получается дорогой, так как каждый раз приходится выполнять проход по списку с
самого начала. На базе связных списков выгодно строить такие структуры данных,
как стеки и очереди.

vector - динамический массив.
Реализован как непрерывная последовательность элементов.
Произвольный доступ к элементам осуществляется за постоянное время, но
вставка и удаление ведет к накладным расходам, так как приходится
выполнять сдвиг части массива, а еще выполнять перераспределение памяти.
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
25.05.2013, 19:47     Разница между list и vector? #6
Цитата Сообщение от Убежденный Посмотреть сообщение
но
вставка и удаление ведет к накладным расходам, так как приходится
выполнять сдвиг части массива, а еще выполнять перераспределение памяти.
а если добавлять в конец вектора?
Убежденный
Системный программист
 Аватар для Убежденный
14191 / 6206 / 985
Регистрация: 02.05.2013
Сообщений: 10,339
Завершенные тесты: 1
25.05.2013, 19:51     Разница между list и vector? #7
От перераспределения памяти это все равно не спасает, если только при
создании вектора не зарезервировать достаточно памяти.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
25.05.2013, 19:52     Разница между list и vector? #8
Цитата Сообщение от mat_for_c Посмотреть сообщение
а если добавлять в конец вектора?
Если size < capacity, то просто копируется один объект. Иначе - выделение нового участка памяти, копирование в него существующих объектов вместе с новым, освобождение старой памяти...
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
25.05.2013, 20:00     Разница между list и vector? #9
Цитата Сообщение от 0x10 Посмотреть сообщение
Если size < capacity, то просто копируется один объект. Иначе - выделение нового участка памяти, копирование в него существующих объектов вместе с новым, освобождение старой памяти...
Причем выделяется не столько же памяти, а с запасом. Например, size = 32, capacity = 32, в конец вставляется новый элемент. Так как size = capacity, то нужно выделять память в новом участке. Если коэффициент = 2, то выделится память под 64 элемента. Потом со старого участка элементы копируются (или же переносятся (move), если у типа элементов предусмотрена такая возможность).
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
25.05.2013, 20:19     Разница между list и vector? #10
Цитата Сообщение от Убежденный Посмотреть сообщение
От перераспределения памяти это все равно не спасает, если только при
создании вектора не зарезервировать достаточно памяти
т.е. с преаллокацией должно пошустрее работать, чем постоянно push_back() вызывать?
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
25.05.2013, 20:27     Разница между list и vector? #11
mat_for_c, можно "преаллоцировать" (reserve) и push_back вызывать, и не будет перераспределения памяти, пока за capacity не вылезете.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.05.2013, 09:38     Разница между list и vector? #12
Цитата Сообщение от Убежденный Посмотреть сообщение
На базе связных списков выгодно строить такие структуры данных, как стеки и очереди.
Насколько мне известно, std::stack строится на базе std::deque, который в свою очередь обычно реализуется через вектор векторов. Поправьте, если не так.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 09:55     Разница между list и vector?
Еще ссылки по теме:

Сортировка vector и list C++
C++ Контейнеры Vector,List
Шаблоны, vector, list C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.05.2013, 09:55     Разница между list и vector? #13
Цитата Сообщение от Tulosba Посмотреть сообщение
Насколько мне известно, std::stack строится на базе std::deque, который в свою очередь обычно реализуется через вектор векторов. Поправьте, если не так.
а с чего ты взял что речь об std::stack ? тут и у ТС не указано что за лист и что за вектор.
так что одна фигня
Yandex
Объявления
26.05.2013, 09:55     Разница между list и vector?
Ответ Создать тему
Опции темы

Текущее время: 13:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru