Хорошие datastructure для ищут идентификатора, отображающегося на набор элементов (C++)

Похоже на задание для std :: map, но ваши замечания, похоже, указывают на то, что вы не хотите его использовать, это это правда?

std::map <key_type, data_type, [comparison_function]>

Ну, это как бы зависит от размера двух наборов (ID * и foo *). Я предполагаю, что у вас есть #ID >> #FOO и #FOO, достаточно большие, чтобы не гарантировать линейный поиск по ним.

Я предполагаю, что ID <-> Foo - это отображение "1 ко многим".

Вы можете сохранить отображение как набор>> и отсортируйте их следующим образом: набор сортируется в порядке возрастания идентификатора * (порядок значений указателя подойдет) набор> сортируется в порядке возрастания значения первого идентификатора * во второй секунде пары.

При поиске вам нужно найти диапазон Foo *, который имеет набор, в котором первый идентификатор * имеет (указатель) значение ниже, чем искомый элемент, а последний - на значение выше. Это, как мы надеемся, приведет к гораздо меньшему набору элементов для итерации по их набору. Затем переберите их и найдите тот, который содержит ID *, который вы ищете.

Вам понадобится компаратор для пары> вроде этого:

typedef Item pair<Foo*, set<ID*> >;

// Sorter in ascending order of first ID*, then ascending order of last ID*
struct IDOrdering: public binary_function<Item, Item, bool> {
  bool operator ()(const Item& lhs, const Item& rhs) {
    return *(lhs.second.begin()) < *(rhs.second.begin())
        || *(lhs.second.rbegin()) < *(rhs.second.rbegin());
  }
};


// your global map
set<Item, FirstIDOrdering> myMap;
typedef set<Item, FirstIDOrdering>::iterator ItemIterator;

// search for the item
Foo* FindXXX(const ID* pId) {
   Item criterion;
   criterion.second.insert(pId);
   ItemIterator start = myMap.lower_bound(criterion);
   while (start != myMap.end() && *(start->second.rbegin()) > pId) {
     if (start->second.count(pId))
       return start->first;
   }
   return NULL;
}

Вы можете сэкономить здесь немного памяти, например Foo * и ID * сохраняются только один раз, но это связано с некоторой сложностью и, вероятно, некоторой производительностью.

Обратите внимание, что этот пример не принимает во внимание все виды пограничных случаев (пустые списки), и вы должны быть осторожны при вставке новый элемент в глобальном myMap, так как вы можете добавить новый ID * в список пары <>, но вам нужно убедиться, что весь набор снова отсортирован, чтобы поиск действительно работал.

Однако трудно сказать, что было бы лучше для вас, так как очень мало информации о том, чего вы пытаетесь достичь: Foo * в миллионах, ID * в миллионах, часто ли вызывается эта функция для преобразования ID * в Foo *? В критически важном для производительности разделе вашей системы? Все это полезно для компромисса с читабельностью, сложностью и производительностью кода.