Russian Qt Forum

Добрый день

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

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

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

Спасибо

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

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

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

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

Вообще-то у 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С;
...
};
 

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

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

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

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

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

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

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

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

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

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

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

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

Это легко проверить, ведь ссылка на ключ доступна

C++ (Qt)
#include <stdio.h>
#include <map>
 
int main()
{
	typedef std::multimap <int, int> TMap;
	TMap test;
	for (size_t i = 0; i < 10; ++i)
		test.insert(std::make_pair(0, 0));
 
	for (TMap::iterator it = test.begin(); it != test.end(); ++it)
		printf("&key = %p, &val = %p\n", &it->first, &it->second);
 
	return 0;
}
 

У меня адреса всех ключей уникальны (как и значений). А у Вас?

Если для Вас такое написание тривиально (для меня нет), то мне было бы интересно посмотреть "как" (ну хотя бы набросок). А без этого - звучит несерьезно :)

Эта дежурная фраза в данном случае неудачна/неуместна - мультимапа не только жрет в неск раз больше памяти, но "зато" и работает медленнее (больше элементов - больше шагов поиска).

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

А не поплохеет от STL-вского кода? :)  Да и сама идея, на мой взгляд, ошибочна. Map не должен знать равны ключи или нет, он просто использует функтор (по умолчанию оператор <).

Ну что же Вы так "мордой в салат" (то есть в дуст) :'(  Ведь правильная (по моему мнению) мысль у Вас была, Вы ее просто потеряли. Можно сделать чтобы памяти съедало раз в 5 меньше и по скорости быстрее (так бывает).

И как по твоему происходит поиск ключа? Вот именно так и определять =).

Если ты про уменьшение размера ключа до int то это ясно, иначе я не знаю на чем ты сможешь с экономить.
Нет, можно конечно при условии что уникальных ключей намного меньше объектов пытаться найти их в мапе если есть то достать оттуда список и добавить, а если нету то создать список добавить туда объект и этот список уже добавить в мап. Но это надо на реальных данных смотреть какая выгода получится.