Данные с неск ключами

[Igors]

Добрый день

Есть такая структурка

Код

C++ (Qt)
struct CData {
 const ClassA * mKeyA;
 const ClassB * mKeyB;
 const ClassC * mKeyC;
 
// какие-то др данные
};
 

В контейнере таких структур (пока неясно в каком) необходимо находить/удалять все CData по каждому из ключей A, B, C плюс по связке ключей A + B. Конечно я могу сделать 4 std::multimap (для каждого ключа), но тогда, найдя элемент, как мне удалить его из всех мапов?

Спасибо

[V1KT0P]

В контейнере таких структур (пока неясно в каком) необходимо находить/удалять все CData по каждому из ключей A, B, C плюс по связке ключей A + B. Конечно я могу сделать 4 std::multimap (для каждого ключа), но тогда, найдя элемент, как мне удалить его из всех мапов?

Завернуть элементы в мини-контейнеры в которые надо будет вложить указатель на все 4-ре мультимапа с ключами по котором требуется удалить. И тогда при удалении мини-контейнера с элементом в деструкторе на основании указателей на мультимапы и ключей удалить записи.
добавлено:
Вот так всегда придумываешь велосипед, затем гуглишь и оказывается что до тебя уже все придумали =).
Значит делается мультиключ, у которого перегружен оператор сравнения меньше. В этом операторе проводишь сравнение в зависимости от параметров ключа. В итоге тебе достаточно будет одного мультимапа, минимальный расход памяти, максимальное быстродействие.
добавлено:
Блин, в час ночи что-то не подумал что не то написал. По моему тебе идеально подойдет "Boost Multi-index Containers Library".

[Igors]

Блин, в час ночи что-то не подумал что не то написал. По моему тебе идеально подойдет "Boost Multi-index Containers Library".

Вероятно да. Не то чтобы я "не хочу" это изучать, но как-то... Ну вопрос/проблема возникла один раз - и может в последний. Мне кажется лучше подумать как самому сделать, а если не выйдет (или слишком коряво) - тогда уже и либы привлекать

[V1KT0P]

Блин, в час ночи что-то не подумал что не то написал. По моему тебе идеально подойдет "Boost Multi-index Containers Library".

Вероятно да. Не то чтобы я "не хочу" это изучать, но как-то... Ну вопрос/проблема возникла один раз - и может в последний. Мне кажется лучше подумать как самому сделать, а если не выйдет (или слишком коряво) - тогда уже и либы привлекать

Вот в голову еще идея пришла как можно сделать свой велосипед:
1) Создаем класс с четырьмя мультимапами.
2) В нем-же список который хранит специальную структуру(указывает на предыдущую и следующую спец структуру).
3) В этой специальной структуре хранится твой объект и четыре итератора мультимапа.
4) При добавлении объекта он заворачивается в спец структуру и указатель на спец структуру с ключами в четыре мультимапа, все четыре итератора полученных после добавления в мультимапы кладем в спец структуру. Эту спец структуру мы добавляем в свой список. Банально в конец и в нашу спец структуру добавляем указатель на предыдущую спец структуру.
5) При удалении спец структуры мы удаляем ее из списка(так как у нас есть указатели на предыдущий и следующий объект в списке, то надо будет просто заменить им указатели друг на друга вместо удаляемой структуры). Также имея четыре итератора мы с помощью них максимально быстро удаляем из мультимапов значения ключа и указателя на спец структуру.
6) Для поиска можно сделать специальные функции, возвращать ли указатель на спец структуру или на твой объект решать тебе. Можешь оба возвращать. Короче дальше уже сам разберешься.
Можно конечно обойтись и без списка, просто с списком удаление будет происходить очень быстро.

[Igors]

Впечатление что мультимапа не помогает, а только мешает. Не заменить ли ее на на std::set? (да, тот самый)

[V1KT0P]

Впечатление что мультимапа не помогает, а только мешает. Не заменить ли ее на на std::set? (да, тот самый)

Вообще-то у std::multimap и std::set разные концепции. std::multimap может содержать несколько одинаковых ключей c разными значениями, в то время как std::set нет. Вот у обычного std::map такая же концепция как и у std::set. Это если я ничего не попутал.

[Igors]

Вообще-то у std::multimap и std::set разные концепции. std::multimap может содержать несколько одинаковых ключей c разными значениями, в то время как std::set нет. Вот у обычного std::map такая же концепция как и у std::set. Это если я ничего не попутал.

На мой взгляд std::set, std::map, std::multimap - это все одна концепция, различия в ф-циоеальности (пусть существенные). Вот напр hash - уже принципиально др алгоритм

Однако вернемся к задаче. Простейшим решением является сохранить в самой структуре все итераторы мультимапов

Код

C++ (Qt)
struct CData {
 const ClassA * mKeyA;
 const ClassB * mKeyB;
 const ClassC * mKeyC;
 
 std::multimap <mKeyA *, CData *>::iterator itA;
 std::multimap <mKeyB *, CData *>::iterator itB;
 std::multimap <mKeyС *, CData *>::iterator itС;
...
};
 

Теперь имея элемент мы можем вычеркнуть его из всех мкльтимапов. Однако будет ли это работать, корректно ли хранить итераторы?

[V1KT0P]

Теперь имея элемент мы можем вычеркнуть его из всех мкльтимапов. Однако будет ли это работать, корректно ли хранить итераторы?

Для мультимапов итератор будет действителен, пока элемент на который он указывает не будет удален. Вот выдержка из стандарта по итераторам стандартных контейнеров: http://kera.name/articles/2011/06/iterator-invalidation-rules/.

[Igors]

Для мультимапов итератор будет действителен, пока элемент на который он указывает не будет удален. Вот выдержка из стандарта по итераторам стандартных контейнеров: http://kera.name/articles/2011/06/iterator-invalidation-rules/.

У меня др источник (cgi) - но результат/смысл тот же (валидно). Значит работать будет. Реализация несложная, как видим, нырять в дуст совсем необязательно  

Хорошо, теперь как мы можем это улучшить? По задаче получается так: одно действие добавляет 100 элементов, у которых ключ B уникален, а A и C одинаковы. Следующее напр еще 100 элементов с теми же A и B но др C. Короче - как правило уникальных A и С с гулькин нос.  Не нравится мне мультимапа своей расходностью...

[fuCtor]

Если правильно понял условие:
Почему бы не реализовать B-Tree для одномерных индексов (в любом случае ключ придется приводить к чему-либо индексируемому) и R-Tree производное для двумерного индекса. Добавляемый элемент будет являться не самой структурой CData, а некоторой оберткой содержащей указатели на родителей в соответствующих индексах + сам указатель на CData.
Таким образом поиск по каждому индексу будет достаточно оптимален, а для удаления достаточно будет найти контейнер-обертку по одному из индексов и используя сохраненные указатели удалится из остальных (без необходимости повторного поиска). Поддержание валидности указателей можно возложить на сами индексы.

[V1KT0P]

Не нравится мне мультимапа своей расходностью...

Какой еще расходностью? Логарифмическая сложность поиска, удаления, добавления. Вроде как должно удовлетворять. Если ты про то, что тебе для нахождения нужно сперва найти по одному ключу, затем из полученного списка по другому. То просто генерируй из двух отдельных ключей один и скорость будет нормальная.
Лучше приведи пример когда мультимап расходует, а то что-то не совсем ясно.

[Igors]

Если правильно понял условие:
Почему бы не реализовать B-Tree для одномерных индексов (в любом случае ключ придется приводить к чему-либо индексируемому) и R-Tree производное для двумерного индекса.

Лихо, наверное Вы пописывали их не один раз? Не видно зачем нужно писать самому если std::map (set) - дерево которое вполне устраивает. А R-tree здесь вообще ни при чем т.к. связка ключей - тоже случай одномерный (совпадение точное). Вот если бы задача была найти "в диапазонах значений (А. С)" - тогда бы выплывало R-tree

Таким образом поиск по каждому индексу будет достаточно оптимален, а для удаления достаточно будет найти контейнер-обертку по одному из индексов и используя сохраненные указатели удалится из остальных (без необходимости повторного поиска). Поддержание валидности указателей можно возложить на сами индексы.

Каким образом? Прошу показать

Какой еще расходностью? Логарифмическая сложность поиска, удаления, добавления. Вроде как должно удовлетворять. Если ты про то, что тебе для нахождения нужно сперва найти по одному ключу, затем из полученного списка по другому. То просто генерируй из двух отдельных ключей один и скорость будет нормальная.

Просьба не тратить время на "подробности для начинающих"  

Лучше приведи пример когда мультимап расходует, а то что-то не совсем ясно.

А я его уже приводил.

одно действие добавляет 100 элементов, у которых ключ B уникален, а A и C одинаковы. Следующее напр еще 100 элементов с теми же A и B но др C.

После "лобового" добавления в 3 мультимапы имеем по 200 элементов в каждой, итого 600. А как обойтись нужным (103)?

[V1KT0P]

одно действие добавляет 100 элементов, у которых ключ B уникален, а A и C одинаковы. Следующее напр еще 100 элементов с теми же A и B но др C.

После "лобового" добавления в 3 мультимапы имеем по 200 элементов в каждой, итого 600. А как обойтись нужным (103)?

Неправильно, после "лобового" добавления в 3 мультимапы имеем по 200 указателей в каждом(я же не думаю что ты решил в каждый мультимап скопировать по одной структуре которая содержит твой объект и итераторы), итого 600 указателей + количество уникальных ключей(я правда не смотрел реализацию мультимапа, но сомневаюсь что там для хранения 100 указателей с одинаковыми ключами он этот ключ создаст 100 раз ибо это не логично да и заморачиваться больше надо).

[Igors]

Неправильно, после "лобового" добавления в 3 мультимапы имеем по 200 указателей в каждом(я же не думаю что ты решил в каждый мультимап скопировать по одной структуре которая содержит твой объект и итераторы), итого 600 указателей + количество уникальных ключей(я правда не смотрел реализацию мультимапа, но сомневаюсь что там для хранения 100 указателей с одинаковыми ключами он этот ключ создаст 100 раз ибо это не логично да и заморачиваться больше надо).

Ну 600 "values" (вместо 103) - уже достаточный аргумент. И я думаю что и 600 ключей он тоже создаст - ведь оператор == для ключа не требуется. Во всяком случае число сравнений (вызовов функтора) для мултимапы с 1 уникальным ключом будет таким же как и для той что все ключи уникальны, и примерно равно пресловутому логарифму. Хотите проверим.

[V1KT0P]

Ну 600 "values" (вместо 103) - уже достаточный аргумент. И я думаю что и 600 ключей он тоже создаст - ведь оператор == для ключа не требуется. Во всяком случае число сравнений (вызовов функтора) для мултимапы с 1 уникальным ключом будет таким же как и для той что все ключи уникальны, и примерно равно пресловутому логарифму. Хотите проверим.

Нет, скорее всего при добавлении если найден уже элемент с таким ключем, то он просто добавляет его в существующий список. Если вдруг это не так, то можешь написать свой map с сравнением и хранением.
Вообще откуда пошло число 103? Смотри у меня 200 структур созданных в куче, я в каждый мультимап кладу 200 указателей на эти структуры(если вдруг какую структуру по какому-то ключу мне не надо искать то я соответственно в этот мультимап и не кладу указатель.). Вот и скажи где здесь накладные расходы?
Смотри, у нас есть 1 объект и нам нужно его искать по трем индексам, в результате кладем три указателя с ключами в три мультимапы, итого 1 объект + 3 указателя. Как можно еще уменьшить я не представляю. Если ты про то что надо хранить ключи в стуктуре, то этого можно и не делать, а доставать их через итераторы. Если тебе мешают итераторы, то и их можешь не хранить, но тогда будет больше времени уходить на удаление объекта из мультимапов.
Вот я и говорю приведи пример где ненужные расходы, ибо я действительно не вижу. И скажи что для тебя важнее: сэкономить память или увеличить скорость операций, ибо одновременно два параметра не улучшить так как тут и так все максимально оптимально сделано.