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

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

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

vector, list, deque - C++

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

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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;
}
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() чем перебирать вот так по одному, ну, вдруг там миллиард элементов =)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 11:40     vector, list, deque
Еще ссылки по теме:

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

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

Работа с STL. Поменять vector на list - C++
Программа должна быть написана так, чтобы достаточно было заменить в одном месте vector на list и приложение делало все то же самое. Если...

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

Скорость перебор элементов vector'a и list'a - C++
Видел на форумах пишут что поиск по несортированному вектору быстрее, чем по листу. Логично предположить что все элементы вектора находятся...


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

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
26.09.2012, 11:40     vector, list, deque #21
AnreyKazakov, У вектора если что есть конструктор копии.
Yandex
Объявления
26.09.2012, 11:40     vector, list, deque
Ответ Создать тему
Опции темы

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