std :: set_intersection на двух совершенно разных контейнерах
У меня было простое требование, где мне нужно найти вхождение строк в одном векторе из основного списка строк в другом векторе. Сначала я смог легко это сделать с помощью:
vector<string> custom_list;
set<string> master_list;
vector<string> target_list;
std::sort(custom_list.begin(), custom_list.end());
std::set_intersection(custom_list.begin(), custom_list.end(), master_list.begin(),
master_list.end(), back_inserter(target_list));
Это работало просто отлично. Но позже оказалось, что каждая строка в master_list была связана с идентификатором. Я надеялся, что смогу использовать std :: set_intersection таким образом, чтобы я мог использовать пересеченные элементы в target_list в качестве индекса для получения их идентификаторов. В сущности, я решил изменить master_list на карту, вот так:
map<string, SomeCustomId> master_list;
и быть в состоянии сделать что-то вроде:
auto I_want_this_id = master_list[target_list[0]);
Но теперь я не уверен, смогу ли я использовать set_intersection для сравнения двух совершенно разных контейнеров (custom_list, vector и master_list, map), даже если я напишу свою собственную функцию сравнения. Что-то вроде:
struct mycomparer {
bool operator()(string const& lhs, pair<string, SomeCustomId> const& rhs) {
return lhs == rhs.first;
}
};
Это не совсем работает (я получил множество ошибок компилятора) и интуитивно, что-то в этом мне показалось неправильным.
Есть ли лучший способ выполнить то, что я пытаюсь сделать?
Решение
std::set_intersection ожидает компаратор, который возвращает true если lhs < rhsне если lhs == rhs, Он также должен иметь возможность сравнивать два аргумента независимо от порядка (в конце концов, определение эквивалентности аргументов выполняется (!comp(a, b) && !comp(b, a))).
Таким образом, вы хотели бы что-то вроде
struct mycomparer {
bool operator()(string const& lhs, pair<string const, SomeCustomId> const& rhs) {
return lhs < rhs.first;
}
bool operator()(pair<string const, SomeCustomId> const& lhs, string const& rhs) {
return lhs.first < rhs;
}
};
Изменить: Обновленный демо-код, чтобы включить все необходимые заголовки. (<iterator> а также <string> пропали без вести. Вероятно, они были включены другими заголовками в GCC, но не в VC ++.)
VC ++ 2012 при выполнении отладочной сборки, похоже, запускает некоторые дополнительные тесты для предоставленного предиката. Это приводит к сбою компиляции с такими ошибками, как error C2664: 'bool mycomparer::operator ()(const std::pair<_Ty1,_Ty2> &,const std::string &)' : cannot convert parameter 1 from 'std::basic_string<_Elem,_Traits,_Alloc>' to 'const std::pair<_Ty1,_Ty2> &', (Он прекрасно компилируется при сборке релиза, как только заголовки исправлены, и я переключился на старый стиль инициализации.)
Чтобы исправить это, поставьте перегрузки operator () принимая все четыре возможных комбинации параметров:
struct mycomparer {
bool operator()(string const& lhs, pair<string const, SomeCustomId> const& rhs) {
return lhs < rhs.first;
}
bool operator()(pair<string const, SomeCustomId> const& lhs, string const& rhs) {
return lhs.first < rhs;
}
bool operator()(string const& lhs, string const& rhs) {
return lhs < rhs;
}
bool operator()(pair<string const, SomeCustomId> const& lhs,
pair<string const, SomeCustomId> const& rhs) {
return lhs.first < rhs.first;
}
};
Редактировать 2: Если вы можете использовать Boost.Range, это гораздо проще. Просто:
boost::set_intersection(custom_list,
master_list | boost::adaptors::map_keys,
back_inserter(target_list));
Пользовательские предикаты не требуются, а также очень удобочитаемы. демонстрация.
Другие решения
Алгоритмы на самом деле не заботятся о контейнерах. Они заботятся об итераторах, и до тех пор, пока оба типа контейнеров удовлетворяют требованиям итератора алгоритма, а ваши типы элементов соответствуют компаратору, совместимость не должна быть проблемой.
Так что, в принципе, то, что вы делаете, это нормально.
Вы должны исправить логику в своем компараторе, хотя; operator() предполагается реализовать менее чем предикат. И, как и Т.С. указывает на то, что вам необходимо реализовать обратное сравнение в явном виде, поскольку типы элементов неявно не могут быть преобразованы друг в друга.