M>>>Можно самому запилить контейнер с вектором или декой, рядом с которым лежит unordered_map и отображает имена на индексы, но что-то лень. O>>Лучше вектор с итераторами на unordered_map, мало ли потом захочется удаление и вставку. Итераторы на unordered_map остаются валидными все время существования мапы и указываемого элемента в ней. M>В принципе, идея годная. Только придётся делать свои обёртки типа итераторов для обхода вектора. M>А готового ничего нет?
boost::multi_index разве что, но вектор+мапа будет эффективнее — и по скорости и по памяти
как вариант в обычную мапу в качестве ключа положить pair<string, size_t> и искать гетерогенным поиском по имени или по индексу.
Как много веселых ребят, и все делают велосипед...
O>>Итераторы на unordered_map остаются валидными все время существования мапы и указываемого элемента в ней. NB>это точно? а если рехешинг случится?
А ну значит поинтеры надо в вектор класть:
References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.
Как много веселых ребят, и все делают велосипед...
Re[5]: Контейнер типа вектора, но с поиском по ключу
O>>А ну значит поинтеры надо в вектор класть: R>И как потом по поинтеру сделать удаление из мапы? Мы же ради этого решили хранить итераторы в векторе?
Хранить в векторе указатель на value_type (std::pair<first, second>, значит иметь под рукой ключ и значение. Удалять соответственно по ключу.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Marty, Вы писали:
Pzz>>В Питоне есть. Тамошний dict (dictionary, ассоциативный массив) — ровно то, что тебя надо.
M>И как я его в плюсах буду использовать?
Мне нужен вектор для добавления элементов (никакого удаления, вставки и тп), наверное подойдёт (а может даже и лучше — объекты жирные) и дека — порядок добавления важен.
Но иногда (и довольно часто) надо искать и по имени.
Основные операции — добавление (с ключом), полный перебор, и поиск по имени. Больше, наверное, ничего и не потребуется.
Ключ обычно лежит в самих элементах в виде поля string name;
Поиск по имени будет использоваться: а) для определения, есть ли уже такое имя или нет; б) для получения элемента по имени (через индекс) — вот тут дека уже не очень. Поиск по имени будет конечно чаще. А получение элемента по имени или индексу будет заметно реже, чем добавление в конец.
Можно самому запилить контейнер с вектором или декой, рядом с которым лежит unordered_map и отображает имена на индексы, но что-то лень.
Может, есть что готовое похожее?
ЗЫ Мне нужно хранить различные дефиниции моего мега DSL языка.
M>Можно самому запилить контейнер с вектором или декой, рядом с которым лежит unordered_map и отображает имена на индексы, но что-то лень.
Лучше вектор с итераторами на unordered_map, мало ли потом захочется удаление и вставку. Итераторы на unordered_map остаются валидными все время существования мапы и указываемого элемента в ней.
Как много веселых ребят, и все делают велосипед...
Re[2]: Контейнер типа вектора, но с поиском по ключу
Здравствуйте, ononim, Вы писали:
M>>Можно самому запилить контейнер с вектором или декой, рядом с которым лежит unordered_map и отображает имена на индексы, но что-то лень. O>Лучше вектор с итераторами на unordered_map, мало ли потом захочется удаление и вставку. Итераторы на unordered_map остаются валидными все время существования мапы и указываемого элемента в ней.
В принципе, идея годная. Только придётся делать свои обёртки типа итераторов для обхода вектора.
Здравствуйте, night beast, Вы писали:
NB>это точно? а если рехешинг случится?
По документам инвалидируются, но на деле всё равно остаются. Я не знаю а как их написать-то надо чтоб ссылка на элемент осталась, а итератор инвалидировался.
Хотя мне попадалась мапа в которой итератор инвалидировался, но я не помню с чем это было связано и даже какой это был компилятор.
В общем на это надеяться я б не стал
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[6]: Контейнер типа вектора, но с поиском по ключу
Здравствуйте, ononim, Вы писали:
R>>И как потом по поинтеру сделать удаление из мапы? Мы же ради этого решили хранить итераторы в векторе? O>Хранить в векторе указатель на value_type, значит иметь под рукой ключ и значение. Удалять соответственно по ключу.
Тоже верно.
--
Справедливость выше закона. А человечность выше справедливости.
Re[2]: Контейнер типа вектора, но с поиском по ключу
Здравствуйте, Pzz, Вы писали:
M>>Может, есть что готовое похожее?
Pzz>В Питоне есть. Тамошний dict (dictionary, ассоциативный массив) — ровно то, что тебя надо.
Здравствуйте, Marty, Вы писали:
M>Здравствуйте!
M>Мне нужен вектор для добавления элементов (никакого удаления, вставки и тп), наверное подойдёт (а может даже и лучше — объекты жирные) и дека — порядок добавления важен.
M>Но иногда (и довольно часто) надо искать и по имени.
M>Основные операции — добавление (с ключом), полный перебор, и поиск по имени. Больше, наверное, ничего и не потребуется.
M>Ключ обычно лежит в самих элементах в виде поля string name;
M>Поиск по имени будет использоваться: а) для определения, есть ли уже такое имя или нет; б) для получения элемента по имени (через индекс) — вот тут дека уже не очень. Поиск по имени будет конечно чаще. А получение элемента по имени или индексу будет заметно реже, чем добавление в конец.
M>Можно самому запилить контейнер с вектором или декой, рядом с которым лежит unordered_map и отображает имена на индексы, но что-то лень.
M>Может, есть что готовое похожее?
M>ЗЫ Мне нужно хранить различные дефиниции моего мега DSL языка.
Если используется boost — то multiindex отлично подходит под такую задачу.
Re[6]: Контейнер типа вектора, но с поиском по ключу
Здравствуйте, ononim, Вы писали:
R>>И как потом по поинтеру сделать удаление из мапы? Мы же ради этого решили хранить итераторы в векторе? O>Хранить в векторе указатель на value_type (std::pair<first, second>, значит иметь под рукой ключ и значение. Удалять соответственно по ключу.
Тогда, получается, что не обязательно использовать unordered_map, можно и простой map, если мне нужно упорядочивание по ключу (про разницу в сложности поиска этих map я в курсе)? По идее, в обычной map там же ноды в куче выделяются, а при изменении дерева только перенастраиваются указатели в нодах?
M>Тогда, получается, что не обязательно использовать unordered_map, можно и простой map, если мне нужно упорядочивание по ключу (про разницу в сложности поиска этих map я в курсе)? По идее, в обычной map там же ноды в куче выделяются, а при изменении дерева только перенастраиваются указатели в нодах?
Если нужно обращение по индексам, то не важно — простой map или unordered, все равно или вектор городить рядом, или boost::multi_index.
Если тебе (внезапно) просто нужна сортировка по именам, простой map, конечно же.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
O>Если нужно обращение по индексам, то не важно — простой map или unordered, все равно или вектор городить рядом, или boost::multi_index. O>Если тебе (внезапно) просто нужна сортировка по именам, простой map, конечно же.
Нет, сортировка особо не нужна, но мало ли, вдруг потом захочется. Я просто уточнил, что если хранить указатель на pair, то можно использовать любой стандартный map, получается
Здравствуйте, Marty, Вы писали:
M>Ключ обычно лежит в самих элементах в виде поля string name;
Тогда буст-мутииндекс, если ключ располагается в самом объекте.
M>ЗЫ Мне нужно хранить различные дефиниции моего мега DSL языка.
Насколько я понял, порядковый номер нужен редко или даже однократно?
Тогда для каждой дефиниции добавить целочисленное поле и хранить в нём значение монотонного счётчика, которое для каждой дефиниции начинается с 0-ля.
Ну и, когда надо будет — построить map по этому индексу (т.е. отсортировать элементы) и пройтись затем по ним в исходном порядке.
Тут смысл в том, чтобы не хранить данные в некоем вспомогательном контейнере, потому что оно не требуется, но усложняет логику.
