Есть ли O (1) способ превратить std :: map & lt; keytype, value & gt; в std :: set & lt; keytype & gt;
Я хотел бы сделать некоторые операции пересечения над ключами std :: map<> экземпляр без дублирования ключей в std :: set<> Заранее.
Это не документировано в API, но есть ли способ за O (1) извлечь ключи из std :: map<> и поместите их в стандартный набор<>?
Решение
Создайте адаптер итератора, который сначала возвращает карту, и используйте его с set_intersection,
Другие решения
Во-первых, нет, нет O(1) операция, чтобы получить набор ключей с карты. Построение набора должно быть Omega(n),
Тем не менее, вы можете сделать set_intersection Вы хотите прямо на карту и другой диапазон, что бы это ни было. Непроверенный код:
template <typename InputIterator, typename Map, typename OutputIterator>
void map_set_intersection(InputIterator first, InputIterator last, const Map &m, OutputIterator o) {
std::set_intersection(
first, last,
m.begin(), m.end(),
o,
KeyCompare<typename Map::value_type, typename std::iterator_traits<InputIterator>::value_type>()
);
}
Вся магия в типе KeyCompare:
template <typename MapValue, typename SetValue>
struct KeyCompare {
bool operator()(const MapValue &lhs, const SetValue &rhs) {
return lhs.first < rhs;
}
bool operator()(const SetValue &lhs, const MapValue &rhs) {
return lhs < rhs.first;
}
};
std::set_difference определяется для копирования значений из первый указан диапазон, который в данном случае является диапазоном, определенным итераторами. Это может быть сделано при условии, что он может сравнивать значения в первом диапазоне со значениями во втором диапазоне в любом порядке (что возможно благодаря KeyCompare). Два диапазона не обязательно должны быть одного типа, поэтому вам не нужен набор ключей с карты.
Если вы уже используете 6-параметрическую форму set_intersectionтогда вам нужно поменять KeyCompare так что после извлечения ключа из записи карты он использует ваш компаратор вместо <,
Если вы используете собственный компаратор или перегружены operator< а также тип значения диапазона итератора совпадает с типом значения карты, тогда это не работает. KeyCompare больше не может использовать типы, чтобы выяснить, в каком порядке предоставлены аргументы и, следовательно, какой из них следует извлечь first снаружи. Я не думаю, что это очень распространенный сценарий, но я также не вижу выхода из него, используя этот подход. Вам понадобится решение Сумасшедшего Эдди, адаптируйте итератор карты. Что составляет этот вопрос: Итерация ключей в карте C ++
Вы можете сделать пересечение O (N) на вашей карте. Помните, что когда вы перебираете карту, ключи располагаются по порядку, поэтому вы можете использовать алгоритм, очень похожий на операцию слияния …
Все, что вам нужно сделать, это поддерживать итератор на каждой карте и увеличивать тот, чей ключ наименьший. Если ключи равны, вы можете добавить к deque, list или же vector (и в этом случае вы увеличиваете оба итератора). Как только один из итераторов достигнет конца своей карты, все готово.