Заблокирован
|
||||||
1 | ||||||
vector, list, deque19.09.2012, 15:04. Показов 8003. Ответов 20
Метки нет (Все метки)
Пытаюсь разобраться, куда лучше какой контейнер применять, под какие задачи. Первый вопрос по списку:
Сказано, что список удаляет любой элемент без потери скорости, это значит, что спиок через n-ое количество удалений list великолепно фрагментирует память? как потом эти дыры заполняются если список остается неизменным?
Получается, что вроде контейнер заполнен последовательно, а в памяти список хранится как попало.... Самое непонятное, это что такое deque, если очередь хранит элементы в стиле списка, зачем ему нужно смещать при удалении все элементы? Т.е у очереди если сразу после удаления обратиться к итератору он покажет на след элемент, но тогда можно использовать вектор, зачем париться... Конечно, плюс большой списка, что при удалении объекта с центра, кроме скорости исполнения =) еще и в том, что итераторы остаются актуальными, кроме итератора, указвающего на удаленный объект... deque так и не понял, он тоже в памяти фрагментированл валяется? Если так, то скорость доступа к его элементам намного ниже чем у вектора... Вот такие вопросы......
0
|
19.09.2012, 15:04 | |
Ответы с готовыми решениями:
20
vector и list Шаблоны, vector, list Vector, list for beginners Контейнеры Vector,List |
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
19.09.2012, 16:04 | 3 |
list обычно реализуется как двусвязный список, он принципиально фрагментирован: элементы расположены где попало в памяти, но благодаря этому и итераторы не протухают при удалении, и удаляется всё быстро.
vector обычно реализуется как однонаправленный буфер (массив, где правая часть как бы пустая). Соответственно, у него более-менее окей получается добавление-удаление с одного конца, где пустая часть, но удаление/вставка в середину вызывают сдвиг всего, что справа от позиции вставки/удаления. Поэтому тормозит в середине, поэтому итераторы протухают (они после сдвига указывают не туда, куда надо), поэтому скорость доступа к произвольному элементы выше. deque обычно реализуется как циклический буфер (массив, где пустой может быть как часть слева от полезного куска, так и справа, так и иногда даже посередине). Это позволяет добавлять/удалять быстро с обоих концов, а в остальном всё тот же вектор: надо что-то в середине сделать — сдвигаем.
1
|
Заблокирован
|
|
19.09.2012, 16:13 [ТС] | 4 |
Первый вопрос по списку был, попробуй создай список из 10000 элементов и удали каждый второй, он и так как попало элементы свои распологает, а тут еще и дыры будут через один элемент, вот я и спрашиваю, как они потом будут заполнятся. А если потом второй список создать, то как я понимаю в памяти элементы списков будут чередоваться элемент 1 списка1, элемент1списка2, элемент2списка1, элемент2списка2.... , а если список 1 допустим буде long а второй int, тогда как?
Который в задаче выделен комментариями contriter Добавлено через 5 минут Он фрагментирован или нет, deque? Щас смотрел как итераторы себя ведут, интересный случай с вектором....вообще беда, я бы сказал... Объявил допустим vector<int>::iterator iter=vec1.begin(); а потом добавил элементы в vec1, а он взял и увеличился.... и вдругой кусок памяти себя записал.. а по адресу *iter бяку выдает....
0
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
19.09.2012, 16:15 | 5 |
Нет. Я ж для кого написал, что если удаляется с середины — там всё сдвигается?
Вот именно потому, что расширяется, в документации и написано: любое изменение длины вектора/дека за исключением удаления с концов (с одного конца для вектора) — все итераторы инвалидируются. Не нравится — для непротухающих итераторов есть list. Если б была одна структура данных, работающая идеально во всех случаях, такого зоопарка бы не было, согласитесь.
1
|
19.09.2012, 16:17 | 6 |
В списке элементы расположены не в строгой последовательности друг за другом в памяти, поэтому там и так будут дыры, если ты об этом. А заполнятся они будут новыми элементами, которые будут добавлять к этому списку или другому или еще чем-то другим. Да, так.
1
|
Заблокирован
|
|
19.09.2012, 16:22 [ТС] | 7 |
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
19.09.2012, 16:22 | 8 |
AnreyKazakov, чтоб не было таких вопросов, нужно хоть раз попытаться реализовать данные контейнеры самому. Про дыры - это просто бред.
0
|
Заблокирован
|
|
19.09.2012, 16:44 [ТС] | 9 |
Лучше бы тебе молчать, если не знаешь, что другой человек делает (а я именно проверкой этих трех контейнеров весь день и занимаюсь) И не говорить про бред, дыры , ну я так куски памяти обозвал , из которых элементы списка удаляются, там пусто щас - значит дыра.
Добавлено через 17 минут как-то так...
0
|
601 / 569 / 104
Регистрация: 07.11.2010
Сообщений: 2,004
|
|
19.09.2012, 16:45 | 10 |
там нету дыр, они и так находятся где попало в памяти, правильный дали совет, реализуйте сами и поймете, что и как работает!
0
|
Заблокирован
|
|
19.09.2012, 16:46 [ТС] | 11 |
ты видимо не читаешь, что написано...
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
19.09.2012, 16:49 | 12 |
Память при создании выделяется под каждый элемент рандомно в памяти. Если бы Вы почитали о структуре списка, никаких мыслях о дырах у Вас бы не было.
Стандартная реализация списка: список состоит из узлов, в которых хранятся сами данные а так же указатель на следующий узел ( и на предыдущий, если двунаправленный список ). При удалении, просто удаляется узел, указатель узла, который стоит переда удаляемым, начинает указывать на узел, который стоит после удаляемого. Никакими дырами тут и не пахнет. PS: и держите Ваши эмоции при себе.
1
|
Заблокирован
|
|
19.09.2012, 16:55 [ТС] | 13 |
За ответ спасибо
PS А про эмоции, как вы мне пишите так я вам и отвечаю, и в лицо бы не сомневаясь повторил то же самое.
0
|
387 / 151 / 16
Регистрация: 12.05.2011
Сообщений: 450
|
|
19.09.2012, 18:34 | 14 |
Все же память в куче выделяется не рандомно, а скорее последовательно, так что после удаления каждого второго элемента куча действительно окажется фрагментирована. Обычно на эту тему не заморачиваются, дефолтный аллокатор худо-бедно справляется с управлением памятью в куче и ладно.
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
19.09.2012, 19:22 | 15 |
yekka, где ОС находит свободную память, там она ее и выделяет для оператора new.
0
|
Заблокирован
|
|||||||||||
20.09.2012, 14:38 [ТС] | 16 | ||||||||||
Еще вопрос по теме, в книжке сказано, что напрямую присвоить значение одного контейнера (например deque) другому (например vector) нельзя, если их тип отличается, а с помощью итераторов можно... главное чтобы их тип допускал преобразование например <char>-><int> и т.п. , можно либо методом assign(,), присвоить, либо при определении объекта, например:
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
20.09.2012, 15:21 | 17 | |||||
AnreyKazakov, Просто надо правильно писать.
На ошибки вообще смотрим?
1
|
Заблокирован
|
|
26.09.2012, 10:34 [ТС] | 18 |
Да уж такая ошибка =((( Долго не было, не смотрел, обливион проходил =)))
Как тогда вектор считывает элементы листа? Как я думаю: 1. Вектор видит, что итераторы принадлежат к списку 2. Поэтому он начинает перебор читаем 1 элемент,смотрим где след , ага нашли, читаем второй элемент... 3. Пока не видим адрес последнего итератора.... Спросил, потомучто, мне кажется, что для считывания очереди и вектора компилятор просто будет прибавлять адрес на размер элемента контейнера, пока не достигнет конца, так же быстрей в 100 раз =)
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|||||||||||
26.09.2012, 11:18 | 19 | ||||||||||
AnreyKazakov, Итератор листа - это обычный biderectional итератор. Собственно, просто идет копирование от итератора first до итератора last вот и все. Грубо говоря.
Как минимум вполне может быть так:
0
|
Заблокирован
|
|
26.09.2012, 11:27 [ТС] | 20 |
Наверно так и есть.... просто у вектора, при копировании гораздо легче наверно сразу шмоток памяти с такого-то адреса в новое место закопировать размером .end()-.begin() или .size() чем перебирать вот так по одному, ну, вдруг там миллиард элементов =)))
0
|
26.09.2012, 11:27 | |
26.09.2012, 11:27 | |
Помогаю со студенческими работами здесь
20
Контейнеры Vector и List (C++) STL vector,list Сортировка vector и list Разница между list и vector Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |