Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.83/41: Рейтинг темы: голосов - 41, средняя оценка - 4.83
Заблокирован
1

vector, list, deque

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

Author24 — интернет-сервис помощи студентам
Пытаюсь разобраться, куда лучше какой контейнер применять, под какие задачи. Первый вопрос по списку:
Сказано, что список удаляет любой элемент без потери скорости, это значит, что спиок через 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.09.2012, 15:04
Ответы с готовыми решениями:

vector и list
1) Правильно ли я понимаю, что при расширении вектора все предыдущие указатели портятся? ...

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

Vector, list for beginners
Доброго времени суток. Поскольку самоучитель Лафоре не подходит для начинающих (...

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

20
Эксперт С++
4985 / 3092 / 456
Регистрация: 10.11.2010
Сообщений: 11,169
Записей в блоге: 10
19.09.2012, 15:55 2
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
как потом эти дыры заполняются если список остается неизменным?
Какие еще дыры? Это же не массив, а двусвязный список.
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
Т.е. после удаления и добавления объекта итератор будет = list1.push_back() минус 1.
О каком именно итераторе идет речь?
0
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
19.09.2012, 16:04 3
list обычно реализуется как двусвязный список, он принципиально фрагментирован: элементы расположены где попало в памяти, но благодаря этому и итераторы не протухают при удалении, и удаляется всё быстро.

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

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

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

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

Добавлено через 17 минут
как-то так...
0
601 / 569 / 104
Регистрация: 07.11.2010
Сообщений: 2,004
19.09.2012, 16:45 10
Цитата Сообщение от AnreyKazakov Посмотреть сообщение
И не говорить про бред, я же не говорю, что ты идиот, дыры , ну я так куски памяти обозвал , из которых элементы списка удаляются, там пусто щас - значит дыра.
там нету дыр, они и так находятся где попало в памяти, правильный дали совет, реализуйте сами и поймете, что и как работает!
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
За ответ спасибо
Цитата Сообщение от Toshkarik Посмотреть сообщение
PS: и держите Ваши эмоции при себе.
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(,), присвоить, либо при определении объекта, например:
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;
    }
Получается, что не все контейнеры можно присваивать друг другу?
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
20.09.2012, 15:21 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/... c3d9a8acee

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

Спросил, потомучто, мне кажется, что для считывания очереди и вектора компилятор просто будет прибавлять адрес на размер элемента контейнера, пока не достигнет конца, так же быстрей в 100 раз =)
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
26.09.2012, 11:18 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;
}
0
Заблокирован
26.09.2012, 11:27  [ТС] 20
Цитата Сообщение от ForEveR Посмотреть сообщение
resize(static_cast<size_type>(last - first));
Iterator current = begin();
for (; first != last; ++first)
{
*current++ = *first;
}
Наверно так и есть.... просто у вектора, при копировании гораздо легче наверно сразу шмоток памяти с такого-то адреса в новое место закопировать размером .end()-.begin() или .size() чем перебирать вот так по одному, ну, вдруг там миллиард элементов =)))
0
26.09.2012, 11:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.09.2012, 11:27
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru