С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
#1

STL List - где он применяется? - C++

19.03.2013, 17:26. Просмотров 1251. Ответов 23
Метки нет (Все метки)

Учу STL, пришел к list. Во первых, я не нашел нормальных уроков/примеров по нем. По мере его изучения из разных источников мне он показался вообще неудобным и ненужным...
Кликните здесь для просмотра всего текста

Мое понимание list:
это обьекты хаотично хранящиеся в памяти, связаны между собой адресами указывающими на предыдущий и следующий обьекты из списка... единственный его плюс это быстрое добавление нового элемента в начало списка

Хочется посмотреть на реальное его применение, а не способы его использования, а также какой то минипроэкт(задачу) чтобы освоить его.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2013, 17:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос STL List - где он применяется? (C++):

Работа с STL list + пропись List.h - C++
Здравствуйте! Помогите, пожалуйста, разобраться с STL list. Нужно сделать программу в которой будет содержаться класс Student, прописать...

Где применяется bind - C++
Можете пожалуйста привести пример, где boost::bind (или сейчас уже std::bind) необходим и без него не обойтись. Просто, понимаю как...

STL List - C++
Вот в чем проблема, была дана задача, решить которую надо было с помощью Deque и List, Deque надобыло оформить через STL, а List написать...

STL list - C++
как вставить элемент в середину списка list STL? float list_insert_rand(int num) { srand (time(NULL)); int rand_num, rand_pos; ...

STL list - C++
Доброго времени суток, пока имею поверхностное представление о алгоритмах STL и функциях для контейнеров, но есть задача: требуется...

List STL - C++
В общем нужно создать класс STL c помощью list: CStudent.h #include <string> using namespace std; enum number_type{G1, G2,...

23
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.03.2013, 17:29 #2
Цитата Сообщение от CollSpack Посмотреть сообщение
единственный его плюс это быстрое добавление нового элемента в начало списка
Не только в начало, но и в конец и в прочие места. Т.е. он нужен, когда нужно часто вставлять/удалять элементы. В других ситуациях предпочтительнее вектор.
При вставках/удалениях список хорош не только скоростью, но и тем, что указатели на элементы списка не протухают, в отличие от вектора.
2
CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 18:02  [ТС] #3
А получается тогда на вывод списка (рандом вывод) потребуется больше времени чем на вывод вектора за счет неудобства доступа? В таком случае его применение становится приемлемым когда нужно быстро принимать данные...
0
Kastaneda
Jesus loves me
Эксперт С++
4697 / 2901 / 238
Регистрация: 12.12.2009
Сообщений: 7,386
Записей в блоге: 2
Завершенные тесты: 1
19.03.2013, 18:59 #4
std::list - это просто реализация списка (т.н. АТД или ADT по "ихнему"). Поэтому вопрос слегка не корректен. Нужно спрашивать ни где применяется std::list, а где применяется список. А ответ на этот вопрос нужно легко нагуглить.
1
Герц
524 / 341 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.03.2013, 19:56 #5
неудобства доступа
Раз уж взялся изучать, используй правильные термины, ознакомься с теорией алгоритмов.
Список имеет сложность O(1) на добавление и удаление нового элемента, O(n) на выборку.
Вектор, наоборот, добавляет и удаляет элементы в общем случае за O(n), а выборку делает за O(1).
1
CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 20:49  [ТС] #6
Всем спасибо, продолжаю учить STL. Появилось несколько вопросов:
По list: на разных ресурсах встречал 2 разные итератора begin и front. О обеих случаях они возвращают адрес 1го элемента. Пока проверить не могу, но их правда 2 схожих итератора?

Еще 1 вопрос не по теме, но по STL:
vector - хорош в работе с последним элементом, а deque с последним и первым, почему тогда не отказались от векторов если deque делает тоже что и vector и даже больше?
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.03.2013, 20:53 #7
Цитата Сообщение от CollSpack Посмотреть сообщение
О обеих случаях они возвращают адрес 1го элемента.
Неправда, begin() возвращает итератор на первый элемент, а front() - сам элемент

Цитата Сообщение от CollSpack Посмотреть сообщение
deque делает тоже что и vector и даже больше?
deque делает это менее эффективно. Банально для получения элемента по индексу потребуется больше операций.
К тому же во всяких студиях дек на редкость убого реализован и беспощадно тормозит.
1
CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 21:56  [ТС] #8
Цитата Сообщение от diagon Посмотреть сообщение
а front() - сам элемент
Цитата с ресурса:
Front — возвращает константную ссылку на первый элемент списка <O(1)>
???

А по поводу вектора и деки я понял, вектор - последовательное задание адресов где работает арифметика указателей, а в деке обьекты как-то разбиваются на небольшие групы, от чего толку от них как от листа... я прав?
0
Kastaneda
Jesus loves me
Эксперт С++
4697 / 2901 / 238
Регистрация: 12.12.2009
Сообщений: 7,386
Записей в блоге: 2
Завершенные тесты: 1
19.03.2013, 22:03 #9
Цитата Сообщение от CollSpack Посмотреть сообщение
Front — возвращает константную ссылку на первый элемент списка <O(1)>
Ну дык ссылка не есть итератор. Да и кстати может и не константную, там на самом деле 2 метода front().
1
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
19.03.2013, 22:43 #10
Цитата Сообщение от CollSpack Посмотреть сообщение
от чего толку от них как от листа... я прав?
И если Вам не приходилось использовать List, то это не значит что он не нужен.
Цитата Сообщение от CollSpack Посмотреть сообщение
vector - хорош в работе с последним элементом
С чего вдруг?
1
xtorne21st
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
19.03.2013, 22:51 #11
CollSpack, Перед изучение stl лучше сначала просто познакомиться с алгоритмами: сортировка, поиск, различные структуры данных.. Причём желательно понять суть. Имхо конечно.
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.03.2013, 23:16 #12
Цитата Сообщение от Croessmah Посмотреть сообщение
С чего вдруг?
Думаю, там имелось ввиду, что вставка в конец вектора занимает амортизированно O(1).

Цитата Сообщение от CollSpack Посмотреть сообщение
А по поводу вектора и деки я понял, вектор - последовательное задание адресов где работает арифметика указателей, а в деке обьекты как-то разбиваются на небольшие групы, от чего толку от них как от листа... я прав?
Да, у вектора главная плюшка — соседние элементы соседствуют в памяти. Деки обычно реализуются или циклическими буферами, или кучкой маленьких массивов, объёдинённых связным списком или вектором. О скорости я бы не говорил так критично, за обозначением O(n) скрываются константы и умелое использование кеша.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
20.03.2013, 10:50 #13
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Думаю, там имелось ввиду, что вставка в конец вектора занимает амортизированно O(1).
Это в лучшем случае. Ведь может быть и перевыделение памяти, с копированием всех элементов O(n).
В списке же такой ситуации не возникнет.
0
Герц
20.03.2013, 11:15
  #14

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Думаю, там имелось ввиду, что вставка в конец вектора занимает амортизированно O(1).
Это в лучшем случае. Ведь может быть и перевыделение памяти, с копированием всех элементов O(n).
В списке же такой ситуации не возникнет.
http://en.wikipedia.org/wiki/Amortized_analysis

0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
20.03.2013, 15:38 #15
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Да, у вектора главная плюшка — соседние элементы соседствуют в памяти.
Пришлось прибегнуть к мат.индукции Проще говоря, весь вектор занимает непрерывный участок памяти. И можно смело использовать &v[0] для передачи в функции, которые хотят получить сишный-массив.
0
20.03.2013, 15:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2013, 15:38
Привет! Вот еще темы с ответами:

stl::list erase() - C++
вот такой код есть, но не работает. как подправить? list&lt;int&gt; ls; list&lt;int&gt;::iterator it; for(int i=0; i&lt;5; i++) { ...

Программа с List из STL - C++
Здравствуйте ребята. Прошу помочь мне с моим кодом. ошибок вроде нету, но не работает удаление по дате и поиск файла с наибольшим...

STL List Iterator - C++
Как в STL list из итератора получить номер элемента, на который он указывает? Вот пример с вектором: cliext::vector&lt;int&gt;::iterator it; ...

Удаление list STL - C++
Из списка, содержащего 100 тыс. элементов, удалить все элементы путем многократного удаления элемента из случайной позиции. Случайная...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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