表格线识别通用库文档
载入中...
搜索中...
未找到
Public 成员函数 | 所有成员列表
cm::DisjointSet< T > 模板类 参考

并查集类 更多...

#include <disjoint_set.hpp>

Public 成员函数

 DisjointSet ()
 并查集类的默认构造函数
 
 DisjointSet (const std::vector< T > &list)
 并查集类的带参构造函数
 
template<typename ITERATOR >
 DisjointSet (ITERATOR start_iterator, ITERATOR end_iterator)
 并查集类的带参构造函数
 
 DisjointSet (const std::initializer_list< T > &inital_list)
 并查集类的初始化列表构造函数
 
 DisjointSet (const DisjointSet &disjoint_set)=default
 并查集类的拷贝构造函数
 
 ~DisjointSet ()
 并查集类的析构函数
 
DisjointSet & Reserve (size_t size)
 重置并查集所对应的空间大小
 
DisjointSet & Resize (size_t size)
 调整并查集对象的大小
 
DisjointSet & Assign (const std::vector< T > &list)
 重新赋值并查集
 
template<typename ITERATOR >
DisjointSet< T > & Assign (ITERATOR start_iterator, ITERATOR end_iterator)
 重新赋值并查集
 
DisjointSet & Swap (DisjointSet< T > &disjoint_set)
 交换并查集
 
DisjointSet & Clear ()
 清空所有数据
 
size_t Size () const
 获取并查集类的数据大小
 
T * Data ()
 获取并查集类的数据指针
 
const T * Data () const
 获取并查集类的常数据指针
 
size_t RootIndex (size_t index)
 获取并查集根节点数据索引
 
bool IsUnion (size_t index1, size_t index2)
 判断并查集中两个指定索引数据项是否在同一个集合中
 
DisjointSet & Union (size_t index1, size_t index2)
 合并两个指定索引数据项
 
size_t CollectionSize (size_t index)
 获取单个集合的大小
 
size_t CollectionsSize ()
 获取集合的数量
 
template<typename FUNC >
DisjointSet< T > & UnionAll (const FUNC &is_union)
 根据提供的判断条件对并查集中所有的数据项进行两两合并
 
List< List< T > > GetAllCollections ()
 获取所有集合数据
 

详细描述

template<typename T>
class cm::DisjointSet< T >

并查集类

该类实现了并查集数据结构，用于处理元素之间的相互连接关系。

模板参数
T并查集元素类型
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 34 行定义.

构造及析构函数说明

◆ DisjointSet() [1/5]

template<typename T >
cm::DisjointSet< T >::DisjointSet ( )
inline

并查集类的默认构造函数

该构造函数用于初始化并查集类的对象，将各指针成员初始化为 nullptr。

作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 83 行定义.

◆ DisjointSet() [2/5]

template<typename T >
cm::DisjointSet< T >::DisjointSet ( const std::vector< T > & list)
inlineexplicit

并查集类的带参构造函数

该构造函数用于初始化并查集类的对象，接受一个数组数据作为参数，并将各指针成员初始化为 nullptr，然后调用 Assign 函数进行赋值操作。

参数
list数组数据
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 95 行定义.

函数调用图:

◆ DisjointSet() [3/5]

template<typename T >
template<typename ITERATOR >
cm::DisjointSet< T >::DisjointSet ( ITERATOR start_iterator,
ITERATOR end_iterator )
inlineexplicit

并查集类的带参构造函数

该构造函数用于初始化并查集类的对象，接受起始迭代器和结束迭代器作为参数，并将各指针成员初始化为 nullptr，然后调用 Assign 函数进行赋值操作。

模板参数
ITERATOR迭代器类型
参数
start_iterator开始迭代器
end_iterator结束迭代器
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 113 行定义.

函数调用图:

◆ DisjointSet() [4/5]

template<typename T >
cm::DisjointSet< T >::DisjointSet ( const std::initializer_list< T > & inital_list)
inline

并查集类的初始化列表构造函数

该构造函数用于初始化并查集类的对象，接受一个初始化列表作为参数，并将各指针成员初始化为 nullptr，然后调用 Assign 函数进行赋值操作。

模板参数
T并查集元素类型
参数
inital_list初始化列表
作者
dreamy-xay
日期
2024-01-04

在文件 disjoint_set.hpp 第 129 行定义.

函数调用图:

◆ DisjointSet() [5/5]

template<typename T >
cm::DisjointSet< T >::DisjointSet ( const DisjointSet< T > & disjoint_set)
default

并查集类的拷贝构造函数

◆ ~DisjointSet()

template<typename T >
cm::DisjointSet< T >::~DisjointSet ( )
inline

并查集类的析构函数

该析构函数将释放类对象所占用的空间资源。

作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 141 行定义.

成员函数说明

◆ Assign() [1/2]

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Assign ( const std::vector< T > & list)
inline

重新赋值并查集

该方法用于重新赋值并查集，类似于 STL 容器的 assign 方法。

参数
list要赋值的列表
返回
类自身引用，方便链式调用
注意
如果存在原有数据，则会被清空。
示例
cm::DisjointSet<int> set = {1, 2, 4, 3};
std::vector<int> data = {1, 2, 3, 4, 5};
set.Assign(data); // 重新赋值并查集
cm::Point
点类
Definition point.hpp:52
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 232 行定义.

这是这个函数的调用关系图:

◆ Assign() [2/2]

template<typename T >
template<typename ITERATOR >
DisjointSet< T > & cm::DisjointSet< T >::Assign ( ITERATOR start_iterator,
ITERATOR end_iterator )
inline

重新赋值并查集

该方法用于重新赋值并查集，根据输入的迭代器范围进行初始化，类似于 STL 容器的 assign 方法。

模板参数
ITERATOR迭代器类型
参数
start_iterator开始迭代器
end_iterator结束迭代器
返回
类自身引用，方便链式调用
注意
如果存在原有数据，则会被清空。
示例
cm::DisjointSet<int> set = {1, 2, 4, 3};
std::vector<int> data = {1, 2, 3, 4, 5};
set.Assign(data.begin(), data.end()); // 重新赋值并查集
int array[3] = {3, 2, 1};
set.Assign(array, array + 3); // 重新赋值并查集
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 286 行定义.

◆ Clear()

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Clear ( )
inline

清空所有数据

该方法用于清空当前并查集实例中的所有数据，但保留已分配的空间，类似 STL 容器的 clear 方法。

返回
类自身引用，方便链式调用
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 345 行定义.

◆ CollectionSize()

template<typename T >
size_t cm::DisjointSet< T >::CollectionSize ( size_t index)
inline

获取单个集合的大小

该方法用于获取指定索引数据项所对应的集合的大小，即集合中包含的数据项个数。

参数
index数据项索引
返回
指定索引数据项所对应的集合的大小
注解
如果索引不是根节点，则会进行路径压缩操作，直接连接到根节点上。
注意
如果索引不合法，可能会导致数组越界和内存泄漏。
复杂度
  • 时间复杂度：近似为常数级别，取决于根节点查询和集合大小获取操作
  • 空间复杂度：常数，O(1)
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 500 行定义.

◆ CollectionsSize()

template<typename T >
size_t cm::DisjointSet< T >::CollectionsSize ( )
inline

获取集合的数量

该方法用于获取并查集中包含的集合数量，即返回并查集中不相交集合的个数。

返回
并查集集合的数量
注解
算法流程：遍历并查集中的所有数据项，通过比较每个数据项的根节点是否等于其自身的索引来确定是否为集合的根节点，从而计算出集合的数量。
复杂度
  • 时间复杂度：O(n)，其中 n 为并查集中数据项的个数
  • 空间复杂度：常数，O(1)
作者
dreamy-xay
日期
2024-01-04

在文件 disjoint_set.hpp 第 520 行定义.

◆ Data() [1/2]

template<typename T >
T * cm::DisjointSet< T >::Data ( )
inline

获取并查集类的数据指针

该方法将返回一个指向并查集类数据的指针，可以用于访问和修改数据，类似于 STL 容器的 data 方法。

返回
并查集类的数据指针
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 377 行定义.

◆ Data() [2/2]

template<typename T >
const T * cm::DisjointSet< T >::Data ( ) const
inline

获取并查集类的常数据指针

该方法将返回一个指向并查集类数据的常指针，可以用于访问数据，类似于 STL 容器的 data 方法。

返回
并查集类的常数据指针
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 391 行定义.

◆ GetAllCollections()

template<typename T >
List< List< T > > cm::DisjointSet< T >::GetAllCollections ( )
inline

获取所有集合数据

该方法用于获取并返回所有集合的数据列表。每个集合的数据用一个列表表示，而所有集合则组成了一个列表的列表。

返回
所有集合列表
复杂度
  • 时间复杂度：O(n)，其中 n 为并查集中数据项的个数
  • 空间复杂度：O(n)
示例
cm::DisjointSet<int> set = {2, 3, 4, 5, 6, 7};
// 合并并查集
set.UnionAll([](const int& item1, const int& item2) { return item1 % 2 == item2 % 2; }); // 将奇数合并到同一个集合中，将偶数合并到另外一个集合中
// 合并的结果如下：
// 集合1（偶数）数据项：{2, 4, 6}
// 集合2（奇数）数据项：{3, 5, 7}
// 获取所有集合数据
cm::List<List<int>> collections = set.GetAllCollections(); // 结果为：[[2, 4, 6], [3, 5, 7]]
// 输出结果
for (const auto& collection : collections) {
for (const auto& item : collection) {
std::cout << item << " ";
}
std::cout << "\n";
}
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 607 行定义.

◆ IsUnion()

template<typename T >
bool cm::DisjointSet< T >::IsUnion ( size_t index1,
size_t index2 )
inline

判断并查集中两个指定索引数据项是否在同一个集合中

该方法用于判断给定的两个数据项索引在并查集中是否属于同一个集合，即它们的根节点是否相同。通过比较两个数据项的根节点来确定它们是否在同一个集合中。

参数
index1数据项索引1
index2数据项索引2
返回
是否在同一个集合中
返回值
true在同一个集合中
false不在同一个集合中
注解
如果索引不是根节点，则会进行路径压缩操作，直接连接到根节点上。
注意
如果索引不合法，可能会导致数组越界和内存泄漏。
复杂度
  • 时间复杂度：近似为常数级别，取决于根节点查询的操作次数
  • 空间复杂度：常数，O(1)
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 443 行定义.

◆ Reserve()

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Reserve ( size_t size)
inline

重置并查集所对应的空间大小

该方法用于重置并查集所对应的空间大小，类似于 STL 容器的 reserve 功能，如果需要重置的空间大小小于当前已分配空间大小，则不执行重置操作。

参数
size并查集所对应空间的大小
返回
类自身引用，方便链式调用
注解
该算法的底层实现是通过调用 STL 的 std::vector 类的 reserve 方法来完成，具体细节请参考STL的官方文档。
示例
void Test(const std::vector<int>& data) {
cm::DisjointSet<int> set;
set.Reserve(100); // 调整并查集所对应的空间大小为 100
set.Assign(data);
}
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 166 行定义.

◆ Resize()

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Resize ( size_t size)
inline

调整并查集对象的大小

该方法用于调整并查集对象的大小，类似于 STL 容器的 resize 功能。

参数
size并查集对象的大小
返回
类自身引用，方便链式调用
注解
  • 如果新的大小小于当前大小，则超出部分将被删除；如果新的大小大于当前大小，则新增部分将被默认构造。
  • 该算法的底层实现是通过调用 STL 的 std::vector 类的 resize 方法来完成，具体细节请参考STL的官方文档。
注意
  • 调整大小可能会导致现有元素的丢失，请谨慎使用。
  • 如果新的大小小于当前大小，则超出部分将被删除；如果新的大小大于当前大小，则新增部分将被默认构造。
示例
void Test(const std::vector<int>& data) {
cm::DisjointSet<int> set;
set.Resize(100); // 调整并查集大小为 100
set.Assign(data);
}
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 202 行定义.

◆ RootIndex()

template<typename T >
size_t cm::DisjointSet< T >::RootIndex ( size_t index)
inline

获取并查集根节点数据索引

该方法用于获取指定索引数据项所对应的集合的根节点数据索引。如果索引不是根节点，则会进行路径压缩操作，将其直接连接到根节点上，以提高查询效率。

参数
index数据项索引
返回
并查集中指定索引数据项所对应的集合的根节点数据索引
注解
如果索引不是根节点，则会进行路径压缩操作，直接连接到根节点上。
注意
如果索引不合法，可能会导致数组越界和内存泄漏。
复杂度
  • 时间复杂度：近似为常数级别，取决于路径压缩的操作次数
  • 空间复杂度：近似为常数级别，递归调用栈的消耗
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 414 行定义.

◆ Size()

template<typename T >
size_t cm::DisjointSet< T >::Size ( ) const
inline

获取并查集类的数据大小

该方法用于获取并查集中元素的数量，类似于 STL 容器的 size 方法。

返回
并查集中元素的数量
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 363 行定义.

◆ Swap()

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Swap ( DisjointSet< T > & disjoint_set)
inline

交换并查集

该方法用于交换当前并查集实例与另一个并查集的内容，类似于 STL 容器的 swap 方法，时间复杂度为 O(1)。

参数
disjoint_set另一个并查集
示例
DisjointSet<int> A{1,2,3};
DisjointSet<int> B{4,5,6};
A.Swap(B); // 现在 A 中的元素为 {4,5,6}，B 中的元素为 {1,2,3}
返回
类自身引用，方便链式调用
注意
  • 此函数不会改变两个并查集的容量大小，如果需要更改容量，可以使用　Reserve 函数。
  • 如果两个并查集的元素类型不同，则此函数会导致编译错误。
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 327 行定义.

◆ Union()

template<typename T >
DisjointSet< T > & cm::DisjointSet< T >::Union ( size_t index1,
size_t index2 )
inline

合并两个指定索引数据项

该方法用于将两个指定索引的数据项合并到同一个集合中，即将两个数据项所在的集合合并为一个集合。

参数
index1数据项索引1
index2数据项索引2
返回
类自身引用，方便链式调用
注解
如果索引不是根节点，则会进行路径压缩操作，直接连接到根节点上。
注意
如果索引不合法，可能会导致数组越界和内存泄漏。
复杂度
  • 时间复杂度：近似为常数级别，取决于根节点查询和集合大小更新操作
  • 空间复杂度：常数，O(1)
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 467 行定义.

◆ UnionAll()

template<typename T >
template<typename FUNC >
DisjointSet< T > & cm::DisjointSet< T >::UnionAll ( const FUNC & is_union)
inline

根据提供的判断条件对并查集中所有的数据项进行两两合并

该方法用于根据提供的判断条件来决定是否将所有的数据项两两合并到同一个集合中。判断条件由参数 is_union 指定，可以是函数指针、lambda 表达式、仿函数等形式。如果判断条件返回 true，则将对应的数据项合并到同一个集合中；否则不进行合并操作。

参数
is_union判断是否合并 item1 和 item2 到一个集合中，反之不合并（形式：(const T& item1, const T& item2) -> bool，支持函数指针、lambda表达式、仿函数等）
返回
类自身引用，方便链式调用
复杂度
  • 时间复杂度：O(n^2)，其中 n 为并查集中数据项的个数
  • 空间复杂度：常数级别，O(1)
警告
该算法的时间复杂度为 O(n^2)，仅适用于数据项较少的情况。
示例
cm::DisjointSet<int> set = {2, 3, 4, 5, 6, 7};
// 合并并查集
set.UnionAll([](const int& item1, const int& item2) { return item1 % 2 == item2 % 2; }); // 将奇数合并到同一个集合中，将偶数合并到另外一个集合中
// 合并的结果如下：
// 集合1（偶数）数据项：{2, 4, 6}
// 集合2（奇数）数据项：{3, 5, 7}
作者
dreamy-xay
日期
2023-12-31

在文件 disjoint_set.hpp 第 559 行定义.

该类的文档由以下文件生成: