Хорошая структура данных для поиска соответствия идентификатора множеству элементов (c ++)

Question

Нет повышения, просто обычный STL, пожалуйста.

У меня есть класс Foo *, отображающий набор указателей класса ID.

и мне нужно сопоставить указатель на экземпляр ID с классом FOO.

скажи, у меня есть эта функция:

void FindXXX(const ID* pID)
{

 /*find the containing FOO class quickly, but not at expense of an ugly code*/

}

сейчас я сопоставляю каждый идентификатор * с FOO *, получая что-то подобное

map myMap; который я считаю уродливым и излишним.

Пожалуйста, предложите

Answer 1

прямо сейчас я сопоставляю каждый идентификатор * с FOO * таким образом имея что-то подобное

map myMap; который я считаю своего рода некрасиво и излишне.

Полагаю, у вас есть что-то вроде этого:

map<ID*, Foo*> myMap;

Почему это было бы ужасно?

Answer 2

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

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

Answer 3

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

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

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

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

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

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, так как вы можете добавить новый идентификатор * в список пары <>, но вам нужно убедиться, что весь набор снова отсортирован, чтобы поиск действительно работал.

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