STL set :: find переопределенный поиск
Моя программа основана на наборе пар, а именно
typedef std::pair<int,int> innerPair;
typedef std::pair<innerPair,int> setElement;
std::set<setElement> Foo;
innerPair element — это то, что действительно определяет setElement, но мне нужно прикрепить идентификатор группы к каждому элементу, следовательно, последний setElement определение.
В оставшейся части программы мне нужно найти innerPair независимо от их идентификатора группы, поэтому мне в основном нужна функция
std::set<setElement>::iterator find(innePair);
который найдет innerPair независимо от его идентификатора группы. В его нынешнем виде я мог бы просто перебирать все доступные идентификаторы группы и выполнять несколько вызовов find (), но это далеко не эффективно.
Есть ли краткий способ определения find( ... ) функция-член, которая выполняет какую-то безразличных поиск или мне нужно перегрузить его собственным определением?
Решение
Если у вас есть несколько элементов с одинаковой внутренней парой и различным идентификатором группы, вы можете использовать std::multimap<innerPair, int>.
Это позволяет хранить несколько элементов с одинаковыми innerPair,
Это также упрощает поиск с lower_bound/upper_bound или же equal_range.
Другие решения
Я вижу два возможных варианта для этого. Один может быть более применимым, чем другой.
Это может быть более подходящим для innerPair быть структурой с 3 членами (первый, второй и идентификатор группы) или std::tuple<int, int, int>, Является ли идентификатор группы частью innerPair объекты? Если так, то я полагаю, что это лучший дизайн.
Если нет (и, честно говоря, я думаю, что в вашей ситуации это не так), вы должны использовать std::map<innerPair,int> создать отображение из innerPair объекты для групповых идентификаторов. Затем вы можете легко найти элемент с помощью:
std::map<innerPair,int> mapping;
// Fill your map
innerPair key = {1, 2};
auto found_iter = mapping.find(key);
Вы также можете получить идентификатор группы для конкретного innerPair с:
int group_id = mapping[key];
Вам не нужно предоставлять собственный компаратор, потому что operator< уже определено для std::pair ,
Если вы хотите искать по частичному объекту, вам, вероятно, лучше всего не использовать std::set<...> а скорее std::map<...>:
std::map<std::pair<int, int>, int>
Это имеет почти тип значения, на которое вы нацелены std::set<...> в любом случае (разница в том, что first участник объявлен const).
Если вы действительно настаиваете на использовании std::set<...> вам нужно создать тип компаратора, который игнорирует последний second член. Я не уверен, если std::set<...> поддерживает смешанные сравнения типов (я считать Это не).
Вы могли бы использовать multisetс пользовательской функцией сравнения или функтором, например:
struct innerPairCompare
{
bool operator () (const setElement &a, const setElement &b)
{
const innerPair &a_ = a.first;
const innerPair &b_ = b.first;
return (a_.first > b_.first || a_.first = b_.first && a_.second > b_.second);
}
};
затем используйте его для своего multiset:
std::multiset<setElement,innerPairCompare> Foo;
Он будет хранить все setElementс тем же innerPair в том же списке.
Кроме того, если вам нужно все innerPair с данным GroupID, используйте функцию сравнения по groupID.
Наконец, если вам не нужно GroupID и innerPair вместе вы могли бы использовать map (или же multimap), с использованием GroupID или innerPair как Key,
Если вы хотите продолжать использовать std::set тогда вы можете использовать std::find_if с пользовательским предикатом, посмотрите на это ответ.
В основном вы будете определять функцию
bool pairCorresponds(std::pair<int,int> element)
это сделает работу за вас.