Комментарии 54
Я студент, так что вопрос возможно глуп. Что значит «надо объединять контейнеры»?
И на мой взгляд схема должна была начинаться с вопроса «Доступ по ключу», ибо зачем вообще кому-то нужен порядок? Это же структура данных
И на мой взгляд схема должна была начинаться с вопроса «Доступ по ключу», ибо зачем вообще кому-то нужен порядок? Это же структура данных
Я студент, так что отвечу. Объединение контейнеров это суть есть сливание содержимого двух контейнеров одного типа в один. В листе выполняется очень быстро, ибо всего-то нужно переразвязать указатели на концах, а вот в векторе нужно полное копирование для переноса.
Думается, что в данном случае не принципиально с какого вопроса из двух начинать. Кто-то начинает выбирать из соображений упорядоченности, кто-то из соображений доступа.
Думается, что в данном случае не принципиально с какого вопроса из двух начинать. Кто-то начинает выбирать из соображений упорядоченности, кто-то из соображений доступа.
В C++11 появились array, forward_list, unordered_map, unordered_set, так что к сожалению табличка уже не актуальна.
Ну, это же Хабра, давайте решим куда добавить — и добавим.
unordered-контейнеры, я так понимаю, дают выигрыш в скорости доступа к отдельному элементу, но уступают по скорости полного прохода по контейнеру. Я так понимаю что они логично Находятся по пути «Порядок важен? — Нет, Надо искать по ключу? Да», и вот тут надо задать вопрос типа «Скорость доступа к отдельному элементу важнее скорости прохода по всему контейнеру?» и, если нет — стрелку на блок «Допустимы дубликаты?», а если да — на блок выбора между unordered_map и unordered_set. Есть другие идеи?
forward_list — блок перед list, вопрос «Нужно итерировать из конца в начало?»
array — блок перед вектором, вопрос «Размер константный?»
Можете предложить более корректные формулировки — прошу, высказывайтесь.
unordered-контейнеры, я так понимаю, дают выигрыш в скорости доступа к отдельному элементу, но уступают по скорости полного прохода по контейнеру. Я так понимаю что они логично Находятся по пути «Порядок важен? — Нет, Надо искать по ключу? Да», и вот тут надо задать вопрос типа «Скорость доступа к отдельному элементу важнее скорости прохода по всему контейнеру?» и, если нет — стрелку на блок «Допустимы дубликаты?», а если да — на блок выбора между unordered_map и unordered_set. Есть другие идеи?
forward_list — блок перед list, вопрос «Нужно итерировать из конца в начало?»
array — блок перед вектором, вопрос «Размер константный?»
Можете предложить более корректные формулировки — прошу, высказывайтесь.
unordered-контейнеры, я так понимаю, дают выигрыш в скорости доступа к отдельному элементу, но уступают по скорости полного прохода по контейнеру
Нет, важнейшее свойство — упорядоченность.
Поиск не по точному значению ключа, а ближайшее (map::lower_bound), а также итерация по записям между двумя заданными значениями ключа (аналог SQL — between)
Нет, важнейшее свойство — упорядоченность.Плюс, отсюда следуют различные требования к элементам контейнера. Для некоторых типов интуитивную операцию сравнения ввести не получится.
Т.е. unordered-контейнеры дают чуть большую скорость ценой потери части функционала — в этом Вы считаете главная суть?
Семантика другая.
Что такое упорядоченный список MD5?
Что такое «ближайший» к данному MD5?
Что такое упорядоченный список MD5?
Что такое «ближайший» к данному MD5?
Эти понятия не имеют смысла. Но ведь «некоторые операции не нужны» — это не повод выбирать другой контейнер. Поводом может быть либо меньшее потребление памяти, либо более высокая скорость определённых операций.
Ну они не только не нужны, их еще просто так и не сделать.
С другой стороны, да, асимптоматика у них разная — скорость поиска/добавления
С другой стороны, да, асимптоматика у них разная — скорость поиска/добавления
ordered_* — O(log(N)). Скорость поиска/добавления в unordetred_* — amort(O(1)).Вы правы. Есть предложения как поправить схему?
По идее, ветку «Надо искать элементы по ключу.» надо расширить на «надо ли производить (упорядоченные) выборки?» — «да —
ordered_*», «нет — unordered_*». Как-то так :)Да, это ровно то место куда я и хотел вставить вопрос и в Вашей формулировке он звучит удачнее. Вечерком поправлю диаграмму.
схема заменена на вариант с контейнерами из С++11
Теперь получилась странная последовательность вопросов:
--> Порядок важен? -> НЕТ -->… --> Нужно производить упорядоченные выборки?
--> Порядок важен? -> НЕТ -->… --> Нужно производить упорядоченные выборки?
Что такое упорядоченный список MD5?
Что такое «ближайший» к данному MD5?
Эти понятия не имеют смысла.
Да хватит вам. Все DTH-сети построены на произвольно выбранной метрике на хешах.
Это давно есть в бусте и те, кому они нужны их используют.
«Надо быстро получить N-ый элемент?» — лишний блок.
Расширять эту схему можно очень долго, например для быстрого поиска лучше подходит сортированный вектор, чем map — habrahabr.ru/post/114518/.
Я бы сказал лучше hash_map, например есть реализации в STL, но не в стандарте, к примеру SGI STL. Или Qt'овский QHash. Но тут все зависит какой тип выбран для ключа, например если выбран целочисленный тип, то тут ясно что сортированный вектор, а если тип string или более сложный то hash_map однозначно быстрее будет на поиске, так как генерирует для него хеш и хранит их список по которым потом происходит быстрый поиск.
В стандарте и реализациях STL есть unordered_map
unordered_map это не совсем hash_map, все дело в хеше ключей. Конечно можно извратится и делать свой класс генерации хеша для сложных типах данных, как я выше писал — string, как тут. Но если есть возможность использовать хеш_мапы и где ключ это сложный тип данных, то это лучшая альтернатива.
У нас в конторе, кстати, есть даже своя обертка (юзаем пока qt4.8) над QVariantHash(он же QHash<QString, QVariant>), так как в подавляющем большинстве имеем дело с xml представлением данных.
Ничего не понял.
Так почему же это не hash_map?
- Для std::unordered_set/unordered_map вторым/третьим шаблонным параметром передается функтор хеширования
- Стандартный std::hash обязан удовлетворять требования функции хеширования
- В стандарте имеется std::hash<string>, который удовлетворяет условиям функции хеширования
- Для любого сложного типа достаточно специализировать std::hash<T>
- std::unordered_set/unorderd_map реализованы через хеш-таблицы
Так почему же это не hash_map?
Какой контейнер мне нужно использовать если мне нужна модель copy-on-write?
Никакой. STL-контейнеры копируют все свои элементы при присвоении и передаче по значению, причём неявно.
Особенно критично это для контейнера std::basic_string, которого нет в этой схеме.
Бесконечные строки, которые порождаются, копируются, выделяют данные в куче.
Тот же QString намного более человеколюбивый контейнер.
Между тем для массива байт куда удачнее идея использовать std::string, чем std::vector, куда я попаду по схеме.
std::vector поэлементно копирует свои данные, неявно приводя их к разрядности системы при присвоении, из-за чего простая операция копирования затягивается почти вдвое.
Так что надо ещё развилку для std::string, если нужно хранить и копировать байты.
Контейнеры std::multiset и std::multimap пишутся слитно. Опять же, если они вам понадобились и «ключи» у вас не уникальные, значит что что-то пошло совсем неоптимально в вашем алгоритме и надо его пересмотреть. Не-уникальные «ключи» как правило не возникают на пустом месте. Возможно где-то сэкономили на времени разработки на первой итерации алгоритма, если есть возможность, нужно вернуться и поправить так, чтобы можно было использовать уникальные ключи, вероятно на шаг раньше, при их наборе.
Никакой. STL-контейнеры копируют все свои элементы при присвоении и передаче по значению, причём неявно.
Особенно критично это для контейнера std::basic_string, которого нет в этой схеме.
Бесконечные строки, которые порождаются, копируются, выделяют данные в куче.
Тот же QString намного более человеколюбивый контейнер.
Между тем для массива байт куда удачнее идея использовать std::string, чем std::vector, куда я попаду по схеме.
std::vector поэлементно копирует свои данные, неявно приводя их к разрядности системы при присвоении, из-за чего простая операция копирования затягивается почти вдвое.
Так что надо ещё развилку для std::string, если нужно хранить и копировать байты.
Контейнеры std::multiset и std::multimap пишутся слитно. Опять же, если они вам понадобились и «ключи» у вас не уникальные, значит что что-то пошло совсем неоптимально в вашем алгоритме и надо его пересмотреть. Не-уникальные «ключи» как правило не возникают на пустом месте. Возможно где-то сэкономили на времени разработки на первой итерации алгоритма, если есть возможность, нужно вернуться и поправить так, чтобы можно было использовать уникальные ключи, вероятно на шаг раньше, при их наборе.
Неуникальные ключи нужны, чтобы построить поисковый индекс поверх существующей структуры данных.
Например, моделируем сервер dropbox. Есть список юзеров, у каждого юзера есть список файлов (имя, размер, md5).
А теперь понадобилась структура, позволяющая по md5 быстро найти юзеров, у которых есть этот файл. multimap<MD5,User*> здесь самое то…
Например, моделируем сервер dropbox. Есть список юзеров, у каждого юзера есть список файлов (имя, размер, md5).
А теперь понадобилась структура, позволяющая по md5 быстро найти юзеров, у которых есть этот файл. multimap<MD5,User*> здесь самое то…
На счёт строк — ну диаграмма ведь для универсальных контейнеров, если нужны строки — конечно, нужно юзать строки.
На счёт массива байтов — а почему в конкретной реализации STL не может быть отдельной реализации вектора байт, который бы копировал одним махом весь массив? Для вектора булов ведь делают кастомную версию.
>пишутся слитно std::multiset и std::multimap
ошибка в оригинале, а я не заметил. Поправлю, спасибо
То что «ключи не уникальные» ещё не признак лажи в архитектуре, если у вас есть 1000 000 людей и есть необходимость быстро выбрать всех Вась, почему бы и не иметь мультимеп по именам?
На счёт массива байтов — а почему в конкретной реализации STL не может быть отдельной реализации вектора байт, который бы копировал одним махом весь массив? Для вектора булов ведь делают кастомную версию.
>пишутся слитно std::multiset и std::multimap
ошибка в оригинале, а я не заметил. Поправлю, спасибо
То что «ключи не уникальные» ещё не признак лажи в архитектуре, если у вас есть 1000 000 людей и есть необходимость быстро выбрать всех Вась, почему бы и не иметь мультимеп по именам?
>std::vector поэлементно копирует свои данные
Возможно я не правильно понял, но всегда думал что копирование POD-типов (коими char-байты являются) осуществляется а-ля memcpy. Этого конечно в Стандарте нет, но любая уважающая себя библиотека должна это реализовывать.
Посмотрел, в VS 2012 копирование идёт через memmove.
Возможно я не правильно понял, но всегда думал что копирование POD-типов (коими char-байты являются) осуществляется а-ля memcpy. Этого конечно в Стандарте нет, но любая уважающая себя библиотека должна это реализовывать.
Посмотрел, в VS 2012 копирование идёт через memmove.
Не хочется изобретать велосипед, но может быть есть в природе подобное по коллекциям C#/Java?
Задумка хорошая. Но часто надо понимать чем они отличаются, как на низком уровне работают. Ну и нынче благодаря auto (а раньше благодаря шаблонам) можно очень быстро проверить один и тот же алгоритм с разными контейнерами на скорость.
Т.е. на мой взгляд эта табличка поможет найти отличия в реализации двух контейнеров, нежели подскажет какой из двух использовать в конкретном случае.
Т.е. на мой взгляд эта табличка поможет найти отличия в реализации двух контейнеров, нежели подскажет какой из двух использовать в конкретном случае.
Между тем, при небольшом размере элементов или при их тривиальном типе, в подавляющем большинстве случаев… Да что я рассказываю, вот тесты, например: www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/.
При небольшом размере контейнеров по барабану вообще всё, если у вас 10 чисел, к которым вы доступаетесь раз в минуту — можно их хранить в строках вида «один», «два», «три» — и пофиг будет. Но мир ведь не стоит на месте, объёмы данных растут, сложность моделей растёт, выигрыш от реализации типа вектор благодаря быстрым операциям на смежных диапазонах рано или поздно проиграет общей теории сложности для разных типов контейнеров.
Я не про размер контейнера, а про размер элемента. Суть в том, что, благодаря кэшу процессора, вектор/дек имеет значительное преимущество перед list. И копирование всех элементов, если они тривиального типа — тоже не так уж страшно.
При последовательном доступе — да, а если нужно миллион раз вставить\удалить элемент в середину?
Я бы больше того сказал. Опыт профилирования показывает, что в стл-е образца студии 2010 и gcc 4.6 вектор даже без преаллокации быстрее дека в случае если не приходится вставлять элемент в начало. Хотя я сам (да и мои коллеги, частенько) ранее ожидал, что в случае если размер контейнера заранее не известен, вставлять элементы можно в конец и контейнер большой (> 1Mb) — std::deque будет быстрее вектора.
После «Отсортирован по ключу -> Да» должно быть «Требуются частые добавления/удаления», где «Да» ведёт на set/map, а «Нет» — на «Отсортированный vector или vector<pair<key, value>>»
Даёшь демократию!
Вот ссылка на диаграмку в онлайн-сервисе, где она делалась: www.gliffy.com/go/publish/4907293
Там же её можно и поправить, и опубликовать свою версию. Вполне можно собрать в этом топике различные варианты «мировозрения», а голоса за комментарии покажут поддержку народа.
Вот ссылка на диаграмку в онлайн-сервисе, где она делалась: www.gliffy.com/go/publish/4907293
Там же её можно и поправить, и опубликовать свою версию. Вполне можно собрать в этом топике различные варианты «мировозрения», а голоса за комментарии покажут поддержку народа.
Если честно, мне не нравится способ представления информации.
Важно понимать свойства стандартных контейнеров, в этом случае диаграмма не нужна. Если их не понимать, то она малополезна.
1. Например, нужно сделать выбор между std::list и std::vector.
Что даёт схема:
— частые вставки/удаления в середине — std::list предпочтительней
— конейнеры нужно «сливать» — std::list предпочтительней
— нужен доступ по индексу — std::vector предпочтительней
О чём схема умалчивает:
— cache-friendly контейнер / быстрый последовательный доступ к элементам — std::vector
— minimal memory overhead — std::vector
— возможность передачи в c-style функцию — std::vector
— быстрый двоичный поиск в отстортированной последовательности — std::vector
— Итераторы должны оставаться валидными при удалении других элементов — std::list
— strong-exception safety guarantee для вставки нескольких элементов — std::list
— частых доступ на всавку/удаление из разных потоков с минимальным временем блокировки — std::list
2. Аналогично std::set vs. std::vector.
Если есть фаза создания сортированной последовательности, и дальнейшего read-only использования, то диаграмма всё равно направит к std::set, хотя std::vector / boost::flat_set будуи намного эффективней.
3. Диаграмма молчит про то, что stack/queue/… — не контейнеры, а адаптеры
Важно понимать свойства стандартных контейнеров, в этом случае диаграмма не нужна. Если их не понимать, то она малополезна.
1. Например, нужно сделать выбор между std::list и std::vector.
Что даёт схема:
— частые вставки/удаления в середине — std::list предпочтительней
— конейнеры нужно «сливать» — std::list предпочтительней
— нужен доступ по индексу — std::vector предпочтительней
О чём схема умалчивает:
— cache-friendly контейнер / быстрый последовательный доступ к элементам — std::vector
— minimal memory overhead — std::vector
— возможность передачи в c-style функцию — std::vector
— быстрый двоичный поиск в отстортированной последовательности — std::vector
— Итераторы должны оставаться валидными при удалении других элементов — std::list
— strong-exception safety guarantee для вставки нескольких элементов — std::list
— частых доступ на всавку/удаление из разных потоков с минимальным временем блокировки — std::list
2. Аналогично std::set vs. std::vector.
Если есть фаза создания сортированной последовательности, и дальнейшего read-only использования, то диаграмма всё равно направит к std::set, хотя std::vector / boost::flat_set будуи намного эффективней.
3. Диаграмма молчит про то, что stack/queue/… — не контейнеры, а адаптеры
Диаграмма, конечно, хуже полного понимания особенностей всех типов контейнеров, но всё же, мне кажется, лучше, чем ничего. Для проектов малой и средней нагруженности вполне пойдёт. По поводу Ваших замечаний — всё правда. Но как это оформить в виде понятной схемы? На ум приходит что-то типа набора критериев, для каждого из которых пользователь может установить его «вес», и по этим весам в итоге будет выбран нужный контейнер. Но, во-первых, тоже не идеально, а во-вторых, в виде статичной картинки — не реализуемо.
Итераторы должны оставаться валидными при удалении других элементов — std::list
Не только std::list, например, set, multiset, map, multimap обладают этим же свойством, а deque обладает этим свойством только при удалении.
А так согласен, одна схема не поможет, нужно четко понимать контейнеры.
Реквестирую
concurrent_hash_map и иже с ним.Со временем будет: Concurrent Unordered Associative Containers for C++
N3709: Minutes for July 2013 Santa Clara SG1 Meeting
Concurrency TS
Part 1: (Publish First, 2014?)
Future Extensions (then, wait_any, wait_all)
Executors
Resumable Functions, await (with futures)
Part 2:
Counters
Queues
Concurrent Vector
Unordered Associatve Containers
N3709: Minutes for July 2013 Santa Clara SG1 Meeting
Concurrency TS
Part 1: (Publish First, 2014?)
Future Extensions (then, wait_any, wait_all)
Executors
Resumable Functions, await (with futures)
Part 2:
Counters
Queues
Concurrent Vector
Unordered Associatve Containers
схема заменена на вариант с контейнерами из С++11
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм выбора STL-контейнера