Имеет ли структура данных набора С++ STL оператор разности наборов?
Разница между наборами C++ STL
Ответы (10)
Да, он есть в <algorithm>
и называется: std::set_difference
. Использование:
#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(result, result.end()));
В конце концов, набор result
будет содержать s1-s2
.
std::inserter
. Никакой квалификации не требуется, так как это функция.
- person rlbond; 26.12.2009
set_difference
требует сортировки обоих контейнеров. Действительно ли set
отсортировано? Это неочевидно.
- person Ayrat; 06.09.2020
Да, в заголовке алгоритмов есть функция set_difference.
Правки:
К вашему сведению, заданная структура данных может эффективно использовать этот алгоритм, как указано в его документации а>. Алгоритм также работает не только с множествами, но и с любой парой итераторов над отсортированными коллекциями.
Как уже упоминалось, это внешний алгоритм, а не метод. Предположительно, это нормально для вашего приложения.
Не "оператор" в смысле языка, но в стандартной библиотеке есть алгоритм set_difference:
http://www.cplusplus.com/reference/algorithm/set_difference.html
Конечно, присутствуют и другие базовые операции над множествами - (объединение и т. д.), как это предлагается в разделе "См. также" в конце связанной статьи.
С++ не определяет оператор разности наборов, но вы можете определить свой собственный (используя код, указанный в других ответах):
template<class T>
set<T> operator -(set<T> reference, set<T> items_to_remove)
{
set<T> result;
std::set_difference(
reference.begin(), reference.end(),
items_to_remove.begin(), items_to_remove.end(),
std::inserter(result, result.end()));
return result;
}
Выбранный ответ правильный, но содержит некоторые синтаксические ошибки.
Вместо
#include <algorithms>
использовать
#include <algorithm>
Вместо
std::insert_iterator(result, result.end()));
использовать
std::insert_iterator<set<int> >(result, result.end()));
std::inserter(result, result.end())
- person rlbond; 26.12.2009
Еще раз, ускорение на помощь:
#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>
std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());
setDifference будет содержать set0-set1.
Не как метод, но есть функция внешнего алгоритма set_difference
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
http://www.sgi.com/tech/stl/set_difference.html
Все ответы, которые я вижу здесь, O (n). Разве так не лучше?:
template <class Key, class Compare, class Allocator>
std::set<Key, Compare, Allocator>
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
const std::set<Key, Compare, Allocator>& rhs) {
if (lhs.empty()) { return lhs; }
// First narrow down the overlapping range:
const auto rhsbeg = rhs.lower_bound(*lhs.begin());
const auto rhsend = rhs.upper_bound(*lhs.rbegin());
for (auto i = rhsbeg; i != rhsend; ++i) {
lhs.erase(*i);
}
return std::move(lhs);
}
Кажется, это правильно. Я не уверен, как быть в случае, когда тип Compare
не полностью определяет его поведение, например, если Compare
является std::function<bool(int,int)>
, но кроме этого, это работает правильно и должно быть похоже на O((num перекрытие) • лог(lhs.size()
)).
В случае, когда lhs
не содержит *i
, вероятно, можно оптимизировать дальнейшую оптимизацию, выполнив поиск O (log (rhs.size()
)) следующего элемента rhs
, который >= следующий элемент lhs
. Это оптимизировало бы случай, когда lhs = {0, 1000}
и rhs = {1, 2, ..., 999}
выполняли вычитание в логарифмическом времени.
мы можем просто использовать
set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).
std::back_inserter
требуется метод push_back()
для целевого контейнера result
. Это не сработает, если result
является std::set
- person Attila; 18.01.2013