Просто о списках, словарях и множествах или ТОП 5 структур данных

[atygaev]

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

Вот очень жалко, честно говоря.

[anVlad11]

Ох, где вы были пять часов назад, когда я придумывал велосипед для хранения json… Спасибо за весьма полезную статью в любом случае.

[tp7]

мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).

При наличии указателя на это место, т.е. в начало и, возможно, в конец, если список двусвязный. В противном случае требуется проход по всем элементам листа до нужного, что при рандомном расположении элементов в памяти может вылиться в серьезную проблему производительности. И часто получается так, что замечательная структура, предназначенная для быстрой вставки и удаления элементов, проигрывает глупому вектору.

[seyfer]

Как же много скобочек

[PsyHaSTe]

Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу

Вы вроде про структуры данных пытаетесь рассказывать, а постоянно соскальзываете в реализацию. Нигде не сказанно, как хранятся элементы списка, есть только контракт на добавление/удаление элементов. В качестве примера тот же List(T) в шарпе основан на саморасширчющемся массиве, а для описанной вами структуры существует отдельный класс LinkedList(T). А все потому, что связный список является частной реализации структуры данных список

[3al]

Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями.

В том же питоне словарь — это set со всеми вытекающими вроде неупорядоченности.

[DragonFire]

И не только в питоне…

[JC_Piligrim]

Если что, то в питоне есть и OrderedDict, кому нужен словарь как в PHP.

docs.python.org/2/library/collections.html#collections.OrderedDict

[3al]

Но и он — не вектор, а список + словарь.

Я не в курсе, в каких крупных платформах хэшмэп делают через векторы и без хэшей.

[mbait]

Если нет привязки к языку программирования, то обычно оперируют понятиями из классических трудов. У вас же всё свалено к кучу. Например, List в Java всего лишь интерфейс, реализация которого ничего не гарантирует кроме наличия определённых методов. ArrayList — уже реализация о которой можно что-то говорить. Vector — потоко-защищённый ArrayList. Я представляю, какая каша была бы у человека в голове, если бы он использовал эти классы после прочтения вашей статьи.

«Старый паскаль» — это вообще что такое?

Причем для обозначения этого самого числа — индекса используют букву i.

Какой-то карго-культ.

[EvilBeaver]

Какой-то карго-культ.

Эй, эй! Руки прочь от старого доброго i.

[dyadyaSerezha]

Слабенькая статья, очень невнятная и путанная. Автор путает интерфейсы, о которых зачем-то упомянул вначале, и реальные структуры данных, постоянно выдавая черты одного за черты другого.
Молчу уже про «изображение в памяти» std::map. По-хорошему за такое сразу отхабривать надо.
Лажанулся автор и с обильным применением списков, так как сейчас все больше применяются массивы, потому они работают существенно быстрее на современной сильно кэшированной памяти.
Ну и до кучи, «тот-же» и «потому-что» пишутся без дефиса!

[Hertz]

На одном из мест моей работы был программист, считавший себя большим знатоком алгоритмов. Ничего кроме асимптотики он во внимание не брал, да и не умел. Вот и его обошло стороной понимание того, что зачастую асимптотика списка проигрывает cache-friendly доступу к памяти у вектора.

[imgen]

Информация 1го курса любого института, плохо поданная.

[Hertz]

>ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Звучит спорно.

>Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.

Из этого утверждения следует, что вектор бесконечен.

[dax]

А где multiset, он же bag, я вас спрашиваю?! Уж если затронули такие свойства как unique/non-unique и ordered/non-ordered, то извольте расписать все четыре варианта.

[stalkers]

боян и оффтоп

Разницу между стеком и очередью, а также преобразование стека в очередь, хорошо демонстрирует автомат Калашникова.

[pfactum]

> Я очень хочу про все это написать

Пишите, умоляю!

[leventov]

Горшочек, не вари.

[MikhailS]

Поддержу вышеотписавшихся: каша получается какая-то. Я не представляю, как человек, не знающий таких вещей после прочтения этой статьи получит от этого больше пользы, чем каши. Про асимптотики вскользь (а ведь они довольно «стандартизованы»), да и то только про часть операций, примеры с котятами не сильно запоминающиеся (да и их избыток не добавляет статье читабельности, но это уже имхо).
Если уж лезть в реализацию, так давайте объясним как (хотя бы как вариант) могут реализовываться структуры с такими асимптотиками и интерфейсом — куда полезнее, мне кажется, чем. Скажем, почему push_back в std::vector может быть реализован за O(1) в среднем, хотя иногда нам придётся переаллоцировать всё за O(n).
А так получается смесь из статьи вида «STL за 12 часов» (в которой есть и свой смысл, и своя аудитория) и статьи про юзкейсы и ограничения для более знакомых с предметом людей (опять же, свой смысл и своя аудитория).