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

vector, list, deque - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
AnreyKazakov
Заблокирован
19.09.2012, 15:04     vector, list, deque #1
Пытаюсь разобраться, куда лучше какой контейнер применять, под какие задачи. Первый вопрос по списку:
Сказано, что список удаляет любой элемент без потери скорости, это значит, что спиок через 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 так и не понял, он тоже в памяти фрагментированл валяется? Если так, то скорость доступа к его элементам намного ниже чем у вектора... Вот такие вопросы......
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.09.2012, 15:04     vector, list, deque
Посмотрите здесь:

C++ STL vector,list
C++ vector и list
Разница между list и vector? C++
C++ Контейнеры Vector и List (C++)
Удаление vector, list, string C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,021
Записей в блоге: 10
Завершенные тесты: 1
19.09.2012, 15:55     vector, list, deque #2
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
как потом эти дыры заполняются если список остается неизменным?
Какие еще дыры? Это же не массив, а двусвязный список.
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Т.е. после удаления и добавления объекта итератор будет = list1.push_back() минус 1.
О каком именно итераторе идет речь?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.09.2012, 16:04     vector, list, deque #3
list обычно реализуется как двусвязный список, он принципиально фрагментирован: элементы расположены где попало в памяти, но благодаря этому и итераторы не протухают при удалении, и удаляется всё быстро.

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

deque обычно реализуется как циклический буфер (массив, где пустой может быть как часть слева от полезного куска, так и справа, так и иногда даже посередине). Это позволяет добавлять/удалять быстро с обоих концов, а в остальном всё тот же вектор: надо что-то в середине сделать — сдвигаем.
AnreyKazakov
Заблокирован
19.09.2012, 16:13  [ТС]     vector, list, deque #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 бяку выдает....
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.09.2012, 16:15     vector, list, deque #5
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Он фрагментирован или нет, deque?
Нет. Я ж для кого написал, что если удаляется с середины — там всё сдвигается?

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

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

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

PS: и держите Ваши эмоции при себе.
AnreyKazakov
Заблокирован
19.09.2012, 16:55  [ТС]     vector, list, deque #13
За ответ спасибо
Цитата Сообщение от Toshkarik Посмотреть сообщение
PS: и держите Ваши эмоции при себе.
PS А про эмоции, как вы мне пишите так я вам и отвечаю, и в лицо бы не сомневаясь повторил то же самое.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
19.09.2012, 18:34     vector, list, deque #14
Все же память в куче выделяется не рандомно, а скорее последовательно, так что после удаления каждого второго элемента куча действительно окажется фрагментирована. Обычно на эту тему не заморачиваются, дефолтный аллокатор худо-бедно справляется с управлением памятью в куче и ладно.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
19.09.2012, 19:22     vector, list, deque #15
yekka, где ОС находит свободную память, там она ее и выделяет для оператора new.
AnreyKazakov
Заблокирован
20.09.2012, 14:38  [ТС]     vector, list, deque #16
Еще вопрос по теме, в книжке сказано, что напрямую присвоить значение одного контейнера (например deque) другому (например vector) нельзя, если их тип отличается, а с помощью итераторов можно... главное чтобы их тип допускал преобразование например <char>-><int> и т.п. , можно либо методом assign(,), присвоить, либо при определении объекта, например:
C++
1
2
deque<char> deq1(10,"+100500");
vector<int> vec1(deq1.begin(),deq1.end());
Но, со списком, как я понимаю это не прокатывае, в связи с той же непоследовательностью элементов в памяти, вот бяку код выдает....
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <list>
#include <iterator>
#include <string>
using std::cout;using std::cin;using std::endl;using std::string;using std::getline;
using std::list;using std::vector;
int main(){
    list<string> list1(5,"+100500");
    cout<<"вывод списка:"<<endl;
    for(list<string>::iterator ix=list1.begin();ix!=list1.end();++ix)cout<<*ix<<" ";
    cout<<endl;
    vector<string> vec1(list1.begin(),list1.end());
    cout<<"вывод вектора"<<endl;
    for(vector<string>::iterator ix;ix!=vec1.end();++ix)cout<<*ix<<*ix<<" ";
    cout<<endl;
    return 0;
    }
Получается, что не все контейнеры можно присваивать друг другу?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
20.09.2012, 15:21     vector, list, deque #17
AnreyKazakov, Просто надо правильно писать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <list>
#include <iterator>
#include <string>
#include <iostream>
#include <vector>
 
using std::cout;using std::cin;using std::endl;using std::string;using std::getline;
using std::list;using std::vector;
int main(){
    list<string> list1(5,"+100500");
    cout<<"вывод списка:"<<endl;
    for(list<string>::iterator ix=list1.begin();ix!=list1.end();++ix)cout<<*ix<<" ";
    cout<<endl;
    vector<string> vec1(list1.begin(),list1.end());
    cout<<"вывод вектора"<<endl;
    for(vector<string>::iterator ix=vec1.begin();ix!=vec1.end();++ix)cout<<*ix << " ";
    cout<<endl;
    return 0;
    }
http://liveworkspace.org/code/ce5fc5...375ec3d9a8acee

На ошибки вообще смотрим?
AnreyKazakov
Заблокирован
26.09.2012, 10:34  [ТС]     vector, list, deque #18
Цитата Сообщение от ForEveR Посмотреть сообщение
Просто надо правильно писать.
Да уж такая ошибка =((( Долго не было, не смотрел, обливион проходил =)))
Как тогда вектор считывает элементы листа?
Как я думаю:
1. Вектор видит, что итераторы принадлежат к списку
2. Поэтому он начинает перебор читаем 1 элемент,смотрим где след , ага нашли, читаем второй элемент...
3. Пока не видим адрес последнего итератора....

Спросил, потомучто, мне кажется, что для считывания очереди и вектора компилятор просто будет прибавлять адрес на размер элемента контейнера, пока не достигнет конца, так же быстрей в 100 раз =)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
26.09.2012, 11:18     vector, list, deque #19
AnreyKazakov, Итератор листа - это обычный biderectional итератор. Собственно, просто идет копирование от итератора first до итератора last вот и все. Грубо говоря.

C++
1
2
3
4
for (; first != last; ++first)
{
    push_back(*first);
}
Ну это очень грубо конечно. Там есть определенные оптимизации, но как это реализовано в конкретном компиляторе меня не очень-то интересует

Как минимум вполне может быть так:
C++
1
2
3
4
5
6
resize(static_cast<size_type>(last - first));
Iterator current = begin();
for (; first != last; ++first)
{
   *current++ = *first;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 11:27     vector, list, deque
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
AnreyKazakov
Заблокирован
26.09.2012, 11:27  [ТС]     vector, list, deque #20
Цитата Сообщение от ForEveR Посмотреть сообщение
resize(static_cast<size_type>(last - first));
Iterator current = begin();
for (; first != last; ++first)
{
*current++ = *first;
}
Наверно так и есть.... просто у вектора, при копировании гораздо легче наверно сразу шмоток памяти с такого-то адреса в новое место закопировать размером .end()-.begin() или .size() чем перебирать вот так по одному, ну, вдруг там миллиард элементов =)))
Yandex
Объявления
26.09.2012, 11:27     vector, list, deque
Ответ Создать тему
Опции темы

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