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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
AnreyKazakov
Заблокирован
#1

vector, list, deque - C++

19.09.2012, 15:04. Просмотров 2939. Ответов 20
Метки нет (Все метки)

Пытаюсь разобраться, куда лучше какой контейнер применять, под какие задачи. Первый вопрос по списку:
Сказано, что список удаляет любой элемент без потери скорости, это значит, что спиок через n-ое количество удалений list великолепно фрагментирует память? как потом эти дыры заполняются если список остается неизменным?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <list>
#include <iterator>
#include <string>
using std::cout;using std::cin;using std::endl; using std::string;
using std::getline;using std::list;
void see(list<string>::iterator ix,list<string>::iterator ixe){
    while(ix!=ixe){cout<<*ix<<" ";++ix;}
    }
int main(){
    string str;
    list<string> list1;
    while(getline(cin,str))list1.push_back(str);
    cin.clear();
    see(list1.begin(),list1.end());
    list<string>::iterator iter, contriter;
    cout<<"Введите слово, которое необходимо удалить"<<endl;
    cin>>str;
    contriter=iter=find(list1.begin(),list1.end(),str);/*ставим итератор на удаляемый элемент*/
    if(iter!=list1.end())list1.erase(iter);/*удаляем элемент*/
//cout<<"удален элемент - "<<*contriter<<" "<<endl; - опасный тип
    list1.push_back("end_element");/*добавляем элемент в конец вектора*/
    see(list1.begin(),list1.end());
    cout<<"удален элемент - "<<*contriter<<" "<<endl;/*итератор указывет на добавленный объект...*/
    return 0;
    }
Т.е. после удаления и добавления объекта итератор будет = list1.push_back() минус 1. (сразу после удаления он мусор выкидывает какой-то...)
Получается, что вроде контейнер заполнен последовательно, а в памяти список хранится как попало....
Самое непонятное, это что такое deque, если очередь хранит элементы в стиле списка, зачем ему нужно смещать при удалении все элементы? Т.е у очереди если сразу после удаления обратиться к итератору он покажет на след элемент, но тогда можно использовать вектор, зачем париться...
Конечно, плюс большой списка, что при удалении объекта с центра, кроме скорости исполнения =) еще и в том, что итераторы остаются актуальными, кроме итератора, указвающего на удаленный объект...
deque так и не понял, он тоже в памяти фрагментированл валяется? Если так, то скорость доступа к его элементам намного ниже чем у вектора... Вот такие вопросы......
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.09.2012, 15:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос vector, list, deque (C++):

vector и list - C++
1) Правильно ли я понимаю, что при расширении вектора все предыдущие указатели портятся? vector&lt;int&gt; a; a.push_back(10); int *ptr...

Контейнеры Vector,List - C++
Как в массиве списков переместить из первой ячейки все элементы которые делятся на 2 в другую ячейку?

Контейнеры Vector и List (C++) - C++
Уважаемые форумчане! Помогите, пожалуйста, реализовать вручную классы Vector и List с основными их методами, дабы получить аналогию...

Сортировка vector и list - C++
Здравствуйте. vector&lt;int&gt; функцией STL медленнее сортируется, чем list&lt;int&gt; собственным методом. #include &lt;cstdlib&gt; #include...

Шаблоны, vector, list - C++
Создать класс Beta таким образом , чтобы при уничтожении последнего объекта на экран выдавалось сообщение о наибольшее количество объектов...

STL vector,list - C++
У меня 2 вопроса: 1) можете рассказать,как подробно работает reverse_iterator?Создал вектор,хочу его распечатать в обратном порядке...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
castaway
Эксперт С++
4884 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
19.09.2012, 15:55 #2
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
как потом эти дыры заполняются если список остается неизменным?
Какие еще дыры? Это же не массив, а двусвязный список.
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Т.е. после удаления и добавления объекта итератор будет = list1.push_back() минус 1.
О каком именно итераторе идет речь?
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.09.2012, 16:04 #3
list обычно реализуется как двусвязный список, он принципиально фрагментирован: элементы расположены где попало в памяти, но благодаря этому и итераторы не протухают при удалении, и удаляется всё быстро.

vector обычно реализуется как однонаправленный буфер (массив, где правая часть как бы пустая). Соответственно, у него более-менее окей получается добавление-удаление с одного конца, где пустая часть, но удаление/вставка в середину вызывают сдвиг всего, что справа от позиции вставки/удаления. Поэтому тормозит в середине, поэтому итераторы протухают (они после сдвига указывают не туда, куда надо), поэтому скорость доступа к произвольному элементы выше.

deque обычно реализуется как циклический буфер (массив, где пустой может быть как часть слева от полезного куска, так и справа, так и иногда даже посередине). Это позволяет добавлять/удалять быстро с обоих концов, а в остальном всё тот же вектор: надо что-то в середине сделать — сдвигаем.
1
AnreyKazakov
Заблокирован
19.09.2012, 16:13  [ТС] #4
Цитата Сообщение от lazybiz Посмотреть сообщение
Какие еще дыры?
Первый вопрос по списку был, попробуй создай список из 10000 элементов и удали каждый второй, он и так как попало элементы свои распологает, а тут еще и дыры будут через один элемент, вот я и спрашиваю, как они потом будут заполнятся. А если потом второй список создать, то как я понимаю в памяти элементы списков будут чередоваться элемент 1 списка1, элемент1списка2, элемент2списка1, элемент2списка2.... , а если список 1 допустим буде long а второй int, тогда как?
Цитата Сообщение от lazybiz Посмотреть сообщение
О каком именно итераторе идет речь?
Который в задаче выделен комментариями contriter

Добавлено через 5 минут
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
а в остальном всё тот же вектор
Он фрагментирован или нет, deque?
Щас смотрел как итераторы себя ведут, интересный случай с вектором....вообще беда, я бы сказал...
Объявил допустим vector<int>::iterator iter=vec1.begin();
а потом добавил элементы в vec1, а он взял и увеличился.... и вдругой кусок памяти себя записал..
а по адресу *iter бяку выдает....
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.09.2012, 16:15 #5
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Он фрагментирован или нет, deque?
Нет. Я ж для кого написал, что если удаляется с середины — там всё сдвигается?

Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Щас смотрел как итераторы себя ведуд, интересный случай с вектором....вообще беда, я бы сказал...
Объявил допустим vector<int>::iterator iter;
а потом добавил элементы, а он взял и увеличился.... и вдругой кусок памяти себя записал..
а по адресу *iter бяку выдает....
Вот именно потому, что расширяется, в документации и написано: любое изменение длины вектора/дека за исключением удаления с концов (с одного конца для вектора) — все итераторы инвалидируются. Не нравится — для непротухающих итераторов есть list. Если б была одна структура данных, работающая идеально во всех случаях, такого зоопарка бы не было, согласитесь.
1
castaway
Эксперт С++
4884 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
19.09.2012, 16:17 #6
В списке элементы расположены не в строгой последовательности друг за другом в памяти, поэтому там и так будут дыры, если ты об этом. А заполнятся они будут новыми элементами, которые будут добавлять к этому списку или другому или еще чем-то другим. Да, так.
1
AnreyKazakov
Заблокирован
19.09.2012, 16:22  [ТС] #7
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
такого зоопарка бы не было

Во, теперь хоть примерно понятно что есть что =)
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
19.09.2012, 16:22 #8
AnreyKazakov, чтоб не было таких вопросов, нужно хоть раз попытаться реализовать данные контейнеры самому. Про дыры - это просто бред.
0
AnreyKazakov
Заблокирован
19.09.2012, 16:44  [ТС] #9
Цитата Сообщение от Toshkarik Посмотреть сообщение
чтоб не было таких вопросов, нужно хоть раз попытаться реализовать данные контейнеры самому. Про дыры - это просто бред.
Лучше бы тебе молчать, если не знаешь, что другой человек делает (а я именно проверкой этих трех контейнеров весь день и занимаюсь) И не говорить про бред, дыры , ну я так куски памяти обозвал , из которых элементы списка удаляются, там пусто щас - значит дыра.

Добавлено через 17 минут
как-то так...
0
panicwassano
592 / 560 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
19.09.2012, 16:45 #10
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
И не говорить про бред, я же не говорю, что ты идиот, дыры , ну я так куски памяти обозвал , из которых элементы списка удаляются, там пусто щас - значит дыра.
там нету дыр, они и так находятся где попало в памяти, правильный дали совет, реализуйте сами и поймете, что и как работает!
0
AnreyKazakov
Заблокирован
19.09.2012, 16:46  [ТС] #11
ты видимо не читаешь, что написано...
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
19.09.2012, 16:49 #12
Память при создании выделяется под каждый элемент рандомно в памяти. Если бы Вы почитали о структуре списка, никаких мыслях о дырах у Вас бы не было.
Стандартная реализация списка: список состоит из узлов, в которых хранятся сами данные а так же указатель на следующий узел ( и на предыдущий, если двунаправленный список ). При удалении, просто удаляется узел, указатель узла, который стоит переда удаляемым, начинает указывать на узел, который стоит после удаляемого. Никакими дырами тут и не пахнет.

PS: и держите Ваши эмоции при себе.
1
AnreyKazakov
Заблокирован
19.09.2012, 16:55  [ТС] #13
За ответ спасибо
Цитата Сообщение от Toshkarik Посмотреть сообщение
PS: и держите Ваши эмоции при себе.
PS А про эмоции, как вы мне пишите так я вам и отвечаю, и в лицо бы не сомневаясь повторил то же самое.
0
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
19.09.2012, 18:34 #14
Все же память в куче выделяется не рандомно, а скорее последовательно, так что после удаления каждого второго элемента куча действительно окажется фрагментирована. Обычно на эту тему не заморачиваются, дефолтный аллокатор худо-бедно справляется с управлением памятью в куче и ладно.
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
19.09.2012, 19:22 #15
yekka, где ОС находит свободную память, там она ее и выделяет для оператора new.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.09.2012, 19:22
Привет! Вот еще темы с ответами:

Разница между list и vector - C++
Подскажите пожалуйста в чем различие между листами и векторами? Сколько не пытался не смог найти реальной разницы между ними. В чем разница...

Удаление vector, list, string - C++
Привет! Такая задача. В программе я описал класс Class1. Класс содержит поля стандартных типов, а также поле std::string и...

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

Задача по контейнерам stl vector и list - C++
Дан сортированный по убыванию массив int'ов размером 100 элементов. Значение начального максимального элемента a, минимального b. На вход...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
19.09.2012, 19:22
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru