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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
CollSpack
 Аватар для CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 17:26     STL List - где он применяется? #1
Учу STL, пришел к list. Во первых, я не нашел нормальных уроков/примеров по нем. По мере его изучения из разных источников мне он показался вообще неудобным и ненужным...
Кликните здесь для просмотра всего текста

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

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

C++ STL vector,list
C++ Работа с STL list
C++ STL List
C++ Где применяется bind
C++ STL list
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.03.2013, 17:29     STL List - где он применяется? #2
Цитата Сообщение от CollSpack Посмотреть сообщение
единственный его плюс это быстрое добавление нового элемента в начало списка
Не только в начало, но и в конец и в прочие места. Т.е. он нужен, когда нужно часто вставлять/удалять элементы. В других ситуациях предпочтительнее вектор.
При вставках/удалениях список хорош не только скоростью, но и тем, что указатели на элементы списка не протухают, в отличие от вектора.
CollSpack
 Аватар для CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 18:02  [ТС]     STL List - где он применяется? #3
А получается тогда на вывод списка (рандом вывод) потребуется больше времени чем на вывод вектора за счет неудобства доступа? В таком случае его применение становится приемлемым когда нужно быстро принимать данные...
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
19.03.2013, 18:59     STL List - где он применяется? #4
std::list - это просто реализация списка (т.н. АТД или ADT по "ихнему"). Поэтому вопрос слегка не корректен. Нужно спрашивать ни где применяется std::list, а где применяется список. А ответ на этот вопрос нужно легко нагуглить.
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.03.2013, 19:56     STL List - где он применяется? #5
неудобства доступа
Раз уж взялся изучать, используй правильные термины, ознакомься с теорией алгоритмов.
Список имеет сложность O(1) на добавление и удаление нового элемента, O(n) на выборку.
Вектор, наоборот, добавляет и удаляет элементы в общем случае за O(n), а выборку делает за O(1).
CollSpack
 Аватар для CollSpack
7 / 7 / 0
Регистрация: 21.01.2013
Сообщений: 55
19.03.2013, 20:49  [ТС]     STL List - где он применяется? #6
Всем спасибо, продолжаю учить STL. Появилось несколько вопросов:
По list: на разных ресурсах встречал 2 разные итератора begin и front. О обеих случаях они возвращают адрес 1го элемента. Пока проверить не могу, но их правда 2 схожих итератора?

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

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

А по поводу вектора и деки я понял, вектор - последовательное задание адресов где работает арифметика указателей, а в деке обьекты как-то разбиваются на небольшие групы, от чего толку от них как от листа... я прав?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
19.03.2013, 22:03     STL List - где он применяется? #9
Цитата Сообщение от CollSpack Посмотреть сообщение
Front — возвращает константную ссылку на первый элемент списка <O(1)>
Ну дык ссылка не есть итератор. Да и кстати может и не константную, там на самом деле 2 метода front().
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11800 / 6779 / 765
Регистрация: 27.09.2012
Сообщений: 16,829
Записей в блоге: 2
Завершенные тесты: 1
19.03.2013, 22:43     STL List - где он применяется? #10
Цитата Сообщение от CollSpack Посмотреть сообщение
от чего толку от них как от листа... я прав?
И если Вам не приходилось использовать List, то это не значит что он не нужен.
Цитата Сообщение от CollSpack Посмотреть сообщение
vector - хорош в работе с последним элементом
С чего вдруг?
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
19.03.2013, 22:51     STL List - где он применяется? #11
CollSpack, Перед изучение stl лучше сначала просто познакомиться с алгоритмами: сортировка, поиск, различные структуры данных.. Причём желательно понять суть. Имхо конечно.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.03.2013, 23:16     STL List - где он применяется? #12
Цитата Сообщение от Croessmah Посмотреть сообщение
С чего вдруг?
Думаю, там имелось ввиду, что вставка в конец вектора занимает амортизированно O(1).

Цитата Сообщение от CollSpack Посмотреть сообщение
А по поводу вектора и деки я понял, вектор - последовательное задание адресов где работает арифметика указателей, а в деке обьекты как-то разбиваются на небольшие групы, от чего толку от них как от листа... я прав?
Да, у вектора главная плюшка — соседние элементы соседствуют в памяти. Деки обычно реализуются или циклическими буферами, или кучкой маленьких массивов, объёдинённых связным списком или вектором. О скорости я бы не говорил так критично, за обозначением O(n) скрываются константы и умелое использование кеша.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11800 / 6779 / 765
Регистрация: 27.09.2012
Сообщений: 16,829
Записей в блоге: 2
Завершенные тесты: 1
20.03.2013, 10:50     STL List - где он применяется? #13
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Думаю, там имелось ввиду, что вставка в конец вектора занимает амортизированно O(1).
Это в лучшем случае. Ведь может быть и перевыделение памяти, с копированием всех элементов O(n).
В списке же такой ситуации не возникнет.
Герц
20.03.2013, 11:15
  #14

Не по теме:

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

Tulosba
:)
Эксперт C++
4377 / 3220 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
20.03.2013, 15:38     STL List - где он применяется? #15
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Да, у вектора главная плюшка — соседние элементы соседствуют в памяти.
Пришлось прибегнуть к мат.индукции Проще говоря, весь вектор занимает непрерывный участок памяти. И можно смело использовать &v[0] для передачи в функции, которые хотят получить сишный-массив.
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
20.03.2013, 16:40     STL List - где он применяется? #16
Следует использовать std::vector::data().
Tulosba
:)
Эксперт C++
4377 / 3220 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
20.03.2013, 17:12     STL List - где он применяется? #17
Цитата Сообщение от Герц Посмотреть сообщение
Следует использовать std::vector::data().
Ну, это начиная с C++11 только.
Croessmah
20.03.2013, 17:16
  #18

Не по теме:

Цитата Сообщение от Tulosba Посмотреть сообщение
Ну, это начиная с C++11 только.
Стандарт не вчера вышел, нужно на него переходить, иначе так и будем все iostream.h инклудить

Tulosba
20.03.2013, 17:39
  #19

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
Стандарт не вчера вышел, нужно на него переходить, иначе так и будем все iostream.h инклудить
Хорошо бы ещё производители компиляторов все на него перешли в полном объеме. Вот, кстати, интересная табличка
Цитата Сообщение от Croessmah Посмотреть сообщение
iostream.h
Так это вроде как в С++03 не обязательно.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2013, 17:52     STL List - где он применяется?
Еще ссылки по теме:

List STL C++
STL list C++
Работа с STL list + пропись List.h C++

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

Или воспользуйтесь поиском по форуму:
Croessmah
20.03.2013, 17:52     STL List - где он применяется?
  #20

Не по теме:

Цитата Сообщение от Tulosba Посмотреть сообщение
Так это вроде как в С++03 не обязательно.
Ну а так если перешли на 03, то на 11 не надо переходить?
Зачем тогда вообще стандарт меняется?

Yandex
Объявления
20.03.2013, 17:52     STL List - где он применяется?
Ответ Создать тему
Опции темы

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