STL Set 算法运算符
5.00/5 (7投票s)
重载运算符，
目录
引言
自从我开始使用 Python 并且这促使我思考如何重新设计我的库使其更具 Python 风格，如果让我从头开始实现它们的话。在本系列的第一篇文章中，我想将 Python 中用于处理集合代数的奇妙且直观的运算符引入 C++ 世界。 这些运算符不过是语法糖，可以减少需要编写的代码量。
集合交集
- 可交换
set_intersection 是一种算法，它产生一个由两个集合共有的元素组成的集合。 它是可交换的，这意味着即使两个集合的位置互换，该算法也会返回相同的结果。
void intersection_example()
{
std::vector<int> v1{ 1,2,3,4,5,6,7,8 };
std::vector<int> v2{ 5, 7, 9,10 };
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::vector<int> v_intersection;
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v_intersection));
for (int n : v_intersection)
std::cout << n << ' ';
}
输出
5 7
这是使用 & 运算符进行交集的示例。
void intersection_example()
{
std::vector<int> v1{ 1,2,3,4,5,6,7,8 };
std::vector<int> v2{ 5, 7, 9,10 };
std::vector<int> v_intersection = s(v1) & s(v2);
for (int n : v_intersection)
std::cout << n << ' ';
}
我跳过了显示运算符示例的输出，因为它与上述相同。
s 是一个函数，而不是类。 如果 s 是一个类，要实例化它，必须指定一个容器类型（见下文）。
std::vector<int> v_intersection = s<std::vector<int>>(v1) & s<std::vector<int>>(v2);
为了利用自动类型推导，s 必须是一个除了返回 wrapper 类之外什么都不做的函数。
#include <algorithm>
#include <iterator>
template<typename T>
struct wrapper
{
wrapper(T& container) : cont(container) {}
T& cont;
};
template<typename T>
wrapper<T> s(T& s_cont)
{
return wrapper<T>(s_cont);
}
& 运算符函数检查是否对容器进行排序。 由于 std::sort 仅适用于随机访问迭代器，因此我们不能将此函数与具有非随机访问迭代器的 STL list 和 slist 一起使用。 在我 15 年的工作中，我还没有在任何代码库中看到对 list 的任何使用。
template<typename T>
T operator&(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
T v_intersection;
std::set_intersection(c1.begin(), c1.end(),
c2.begin(), c2.end(),
std::back_inserter(v_intersection));
return v_intersection;
}
所有集合算法的先决条件都要求范围已排序，因此需要此 is_sorted 检查。
集合并集
- 可交换
set_union 是一种算法，它产生一个由两个集合的元素组成的集合。 对于出现在交集中的元素，它总是从第一个集合中选择它们，而不是从第二个集合中选择。
void union_example()
{
std::vector<int> v1 = { 1, 2, 3, 4, 5 };
std::vector<int> v2 = { 3, 4, 5, 6, 7 };
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::vector<int> dest1;
std::set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(dest1));
for (const auto &i : dest1) {
std::cout << i << ' ';
}
std::cout << '\n';
}
输出
1 2 3 4 5 6 7
所需的代码量少得多，因此代码更简洁。
void union_example()
{
std::vector<int> v1 = { 1, 2, 3, 4, 5 };
std::vector<int> v2 = { 3, 4, 5, 6, 7 };
std::vector<int> dest1 = s(v1) | s(v2);
for (int n : dest1)
std::cout << n << ' ';
}
| 运算符几乎类似于 & 运算符，只是算法不同。
template<typename T>
T operator|(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
T dest1;
std::set_union(c1.begin(), c1.end(),
c2.begin(), c2.end(),
std::back_inserter(dest1));
return dest1;
}
集合差集
- 不可交换
set_difference 返回 第一个集合中不在第二个集合中的元素，并用 Python 中的减号运算符表示。 由于显而易见的原因，当参数交换位置时，结果是不同的。 set_difference 像减号运算一样是不可交换的。
void set_difference_example()
{
std::vector<int> v1{ 1, 2, 5, 5, 5, 9 };
std::vector<int> v2{ 2, 5, 7 };
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::vector<int> diff;
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::inserter(diff, diff.begin()));
for (auto i : v1) std::cout << i << ' ';
std::cout << "minus ";
for (auto i : v2) std::cout << i << ' ';
std::cout << "is: ";
for (auto i : diff) std::cout << i << ' ';
std::cout << '\n';
}
输出
1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9
这是一个带有减号运算符的示例。
void set_difference_example()
{
std::vector<int> v1{ 1, 2, 5, 5, 5, 9 };
std::vector<int> v2{ 2, 5, 7 };
std::vector<int> diff = s(v1) - s(v2);
for (auto i : v1) std::cout << i << ' ';
std::cout << "minus ";
for (auto i : v2) std::cout << i << ' ';
std::cout << "is: ";
for (auto i : diff) std::cout << i << ' ';
std::cout << '\n';
}
减号运算符的代码如下所示
template<typename T>
T operator-(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
T diff;
std::set_difference(c1.begin(), c1.end(),
c2.begin(), c2.end(),
std::back_inserter(diff));
return diff;
}
集合对称差
C++ 参考: std::set_symmetric_difference
- 可交换
set_symmetric_difference 计算存在于任一集合中但不同时存在于两个集合中的元素。
void set_symmetric_difference_example()
{
std::vector<int> v1{ 1,2,3,4,5,6,7,8 };
std::vector<int> v2{ 5, 7, 9,10 };
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::vector<int> v_symDifference;
std::set_symmetric_difference(
v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v_symDifference));
for (int n : v_symDifference)
std::cout << n << ' ';
}
输出
1 2 3 4 6 8 9 10
set_symmetric_difference 由逻辑异或运算符表示。
void set_symmetric_difference_example()
{
std::vector<int> v1{ 1,2,3,4,5,6,7,8 };
std::vector<int> v2{ 5, 7, 9,10 };
std::vector<int> v_symDifference = s(v1) ^ s(v2);
for (int n : v_symDifference)
std::cout << n << ' ';
}
逻辑异或运算符的代码如下所示
template<typename T>
T operator^(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
T v_symDifference;
std::set_symmetric_difference(c1.begin(), c1.end(),
c2.begin(), c2.end(),
std::back_inserter(v_symDifference));
return v_symDifference;
}
超集和子集
- 不可交换
STL includes 可用于确定一个集合是否是超集（返回一个布尔值）。 要检查它是否是子集，只需切换这两个集合。
void is_superset_example()
{
std::vector<char> v1{ 'a', 'b', 'c', 'f', 'h', 'x' };
std::vector<char> v2{ 'a', 'b', 'c' };
std::vector<char> v3{ 'a', 'c' };
std::vector<char> v4{ 'g' };
std::vector<char> v5{ 'a', 'c', 'g' };
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::sort(v3.begin(), v3.end());
std::sort(v4.begin(), v4.end());
std::sort(v5.begin(), v5.end());
for (auto i : v1) std::cout << i << ' ';
std::cout << "\nincludes:\n" << std::boolalpha;
for (auto i : v2) std::cout << i << ' ';
std::cout << ": "
<< std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n';
for (auto i : v3) std::cout << i << ' ';
std::cout << ": "
<< std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << '\n';
for (auto i : v4) std::cout << i << ' ';
std::cout << ": "
<< std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n';
for (auto i : v5) std::cout << i << ' ';
std::cout << ": "
<< std::includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << '\n';
auto cmp_nocase = [](char a, char b) {
return std::tolower(a) < std::tolower(b);
};
std::vector<char> v6{ 'A', 'B', 'C' };
for (auto i : v6) std::cout << i << ' ';
std::cout << ": (case-insensitive) "
<< std::includes(v1.begin(), v1.end(), v6.begin(), v6.end(), cmp_nocase)
<< '\n';
}
输出
a b c f h x
includes:
a b c : true
a c : true
g : false
a c g : false
A B C : (case-insensitive) true
>= 运算符示例在下面。 本文未显示 <= 运算符示例。
void is_superset_example()
{
std::vector<char> v1{ 'a', 'b', 'c', 'f', 'h', 'x' };
std::vector<char> v2{ 'a', 'b', 'c' };
std::vector<char> v3{ 'a', 'c' };
std::vector<char> v4{ 'g' };
std::vector<char> v5{ 'a', 'c', 'g' };
for (auto i : v1) std::cout << i << ' ';
std::cout << "\nincludes:\n" << std::boolalpha;
for (auto i : v2) std::cout << i << ' ';
std::cout << ": " << (s(v1) >= s(v2)) << '\n';
for (auto i : v3) std::cout << i << ' ';
std::cout << ": " << (s(v1) >= s(v3)) << '\n';
for (auto i : v4) std::cout << i << ' ';
std::cout << ": " << (s(v1) >= s(v4)) << '\n';
for (auto i : v5) std::cout << i << ' ';
std::cout << ": " << (s(v1) >= s(v5)) << '\n';
auto cmp_nocase = [](char a, char b) {
return std::tolower(a) < std::tolower(b);
};
std::vector<char> v6{ 'A', 'B', 'C' };
for (auto i : v6) std::cout << i << ' ';
std::cout << ": (case-insensitive) "
<< std::includes(v1.begin(), v1.end(), v6.begin(), v6.end(), cmp_nocase)
<< '\n';
}
如不区分大小写的示例所示，用户目前无法选择在 >= 和 <= 重载运算符中使用自定义比较器。 在这种情况下，必须直接调用 includes。
// Returns true if left is superset of right?
template<typename T>
bool operator>=(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
return std::includes(
c1.begin(), c1.end(),
c2.begin(), c2.end());
}
// Returns true if left is subset of right?
template<typename T>
bool operator<=(wrapper<T>& left, wrapper<T>& right)
{
T& c1 = left.cont;
T& c2 = right.cont;
if (!std::is_sorted(c1.begin(), c1.end()))
std::sort(c1.begin(), c1.end());
if (!std::is_sorted(c2.begin(), c2.end()))
std::sort(c2.begin(), c2.end());
return std::includes(
c2.begin(), c2.end(),
c1.begin(), c1.end());
}
“我用不着这些！”
在您急于声称您不需要这些集合算法之前，我想向您展示一个典型的选择示例，您可以在其中使用它。 想象一下，您正在为大学生编写一个选课网站。 在表格上，目前有学生添加的已选科目，以及学生可以选择的可用科目下拉列表。 添加后从可用下拉列表中删除科目是有意义的，因为您不希望学生意外地两次添加相同的科目。 计算可供选择的剩余科目的一种方法是，仅使用本文中介绍的减号运算符从完整科目集中减去已选科目集。
文章源代码托管在 Github
与集合交集性能相关的文章： 有序集合的交集
历史
- 2017 年 12 月 30 日: 第一个版本
- 2018 年 6 月 16 日: 1.1 版本 移除返回期间的
std::move以启用“命名返回值优化”