拓冰网站定制 
前言「集合类」这个词有歧义先把话说清楚一种理解是数学意义上的集合set——元素不重复、支持添加/删除/判存在/求交并差另一种理解是泛指容器collection——能装东西就行。这两种理解的接口设计和内部结构完全不同本文按前一种set 语义来写因为这是「集合类」这个说法在 C 语境下最常指的东西。另一个需要澄清的误解是「简单」不等于「应该用std::vector硬凑」。标准库已经提供了std::set红黑树有序和std::unordered_set哈希表无序绝大多数场景应该直接用它们。手写一个集合类的价值在于理解「不重复」这个约束是怎么在接口层被维护的、什么时候用线性查找反而更快、以及为什么教材上的实现常常在const正确性和异常安全上出问题。本文给出一个基于std::vector的顺序存储集合类元素个数少几十个以内时它比std::set更快也更好缓存然后逐条讨论接口设计中的取舍最后给出可编译的完整示例和一张与标准容器的对照表。一、集合的核心语义不重复集合与普通容器的唯一区别就是插入时不产生重复元素。这个约束在接口层表现为两点insert需要告诉调用者「到底插进去了没有」所以返回bool或返回「是否新插入」的std::pairiterator, bool这是std::set::insert的返回类型。所有修改操作之后必须能保证「任意两个元素不相等」。「相等」怎么定义对自定义类型C 里有两套语义基于operator的相等equalitystd::find用的是它基于operator的等价equivalencestd::set用的是它。标准库的惯例是关联容器默认用std::lessT也就是operator而无序容器用std::equal_toT加std::hashT。我们的顺序存储实现用operator更直观。这对自定义类型有个实际要求要么定义operator要么在构造时传入一个比较器。下面的实现用默认的std::equal_toT行为等价于。二、用 std::vector 做存储的顺序集合选std::vector做后备存储有三个理由内存连续缓存友好、遍历极快、小规模下常数因子小。代价是查找是线性的 O(n)删除需要移动元素。#include algorithm #include cstddef #include functional #include iostream #include string #include utility #include vector template typename T, typename Equal std::equal_toT class SimpleSet { public: // 插入已存在则返回 false不改变集合 bool insert(const T value) { if (contains(value)) { return false; } data_.push_back(value); return true; } bool insert(T value) { if (contains(value)) { return false; } data_.push_back(std::move(value)); return true; } // 删除返回是否真的删掉了一个元素 bool erase(const T value) { auto it std::find_if(data_.begin(), data_.end(), [value, this](const T x) { return eq_(x, value); }); if (it data_.end()) { return false; } // 用最后一个元素填补空洞O(1)但会打乱顺序 if (it ! data_.end() - 1) { *it std::move(data_.back()); } data_.pop_back(); return true; } bool contains(const T value) const { return std::find_if(data_.begin(), data_.end(), [value, this](const T x) { return eq_(x, value); }) ! data_.end(); } void clear() noexcept { data_.clear(); } std::size_t size() const noexcept { return data_.size(); } bool empty() const noexcept { return data_.empty(); } // 只读遍历暴露常量迭代器防止外部改坏「不重复」这个不变量 std::vectorT::const_iterator begin() const noexcept { return data_.begin(); } std::vectorT::const_iterator end() const noexcept { return data_.end(); } // 集合运算 SimpleSet unionWith(const SimpleSet other) const { SimpleSet result *this; for (const T x : other.data_) { result.insert(x); } return result; } SimpleSet intersect(const SimpleSet other) const { SimpleSet result; for (const T x : data_) { if (other.contains(x)) { result.insert(x); } } return result; } SimpleSet difference(const SimpleSet other) const { SimpleSet result; for (const T x : data_) { if (!other.contains(x)) { result.insert(x); } } return result; } bool equals(const SimpleSet other) const { if (size() ! other.size()) { return false; } for (const T x : data_) { if (!other.contains(x)) { return false; } } return true; } private: std::vectorT data_; Equal eq_{}; };几个设计点值得展开为什么erase用「和最后一个元素交换」而不是data_.erase(it)。vector::erase会把后面的元素整体前移一格是 O(n)而把末尾元素搬到空洞处再pop_back()是 O(1)。代价是集合内部顺序被打乱——这一点必须在文档里写清楚否则用户会依赖遍历顺序。这也是为什么这个类不叫「有序集合」。为什么要判断it ! data_.end() - 1。如果被删的正好是最后一个元素*it std::move(data_.back())就是自移动赋值。对内置类型如int没问题对std::string这类标准库类型虽然标准保证了「有效状态」但结果是指向自身的移动行为微妙且没必要。加一个判断就绕开了。eq_是成员变量而不是静态的。因为Equal可能是有状态的比如忽略大小写的比较器。std::equal_toT是无状态的空类Equal eq_{}不占空间空基类优化在成员对象上不适用但空类成员本身只占 1 字节还要考虑对齐。实际使用时int main() { SimpleSetint a; std::cout a.insert(1) \n; // 1插入成功 std::cout a.insert(1) \n; // 0已存在拒绝 a.insert(2); a.insert(3); SimpleSetint b; b.insert(3); b.insert(4); const SimpleSetint u a.unionWith(b); // {1,2,3,4} const SimpleSetint i a.intersect(b); // {3} const SimpleSetint d a.difference(b); // {1,2} std::cout u.size() i.size() d.size() \n; // 输出4 1 2 a.erase(2); std::cout a.size() a.contains(2) \n; // 2 0 return 0; }注意unionWith、intersect、difference都是返回新集合而不是就地修改。这是刻意选择赋值语义比原地修改更不容易写出别名 bug比如s s.unionWith(s)这种自赋值场景。如果确实需要就地版本再加一个void unionInPlace(const SimpleSet)会更清楚。三、和标准容器怎么选维度本文的顺序集合std::setstd::unordered_set底层结构std::vector线性存储红黑树标准只要求「平衡二叉搜索树」的复杂度哈希表链地址法或开放寻址实现自定插入O(n)O(log n)平均 O(1)最坏 O(n)查找O(n)O(log n)平均 O(1)遍历顺序插入顺序删除会打乱有序按比较器无序内存局部性最好连续差每节点一次分配中等元素类型要求operator或自定义比较器operator或自定义比较器可哈希std::hash特化迭代器失效插入可能全部失效扩容仅被删元素失效仅被删元素失效rehash 时迭代器可能失效元素少几十个以内时的表现通常最快较慢较慢关于上表的最后一行这里不给具体倍数因为那取决于元素类型、元素大小、编译器和数据分布。如果你要验证可以自己写一段插入加查找的循环用std::chrono::steady_clock计时同时用-O2编译——结论会因为元素是int还是std::string而完全不同。原理层面的判断是可靠的std::set每个节点都是一次堆分配而vector是一次分配加顺序访问在元素少到能放进几行缓存时后者的优势几乎总是压倒性的。std::unordered_set的桶增长策略、负载因子上限都是实现定义的libstdc 与 MSVC STL 的默认最大负载因子是 1.0libc 也是 1.0但桶数量的增长序列和 rehash 时机由各家自己决定标准没有规定。所以跨标准库统计「桶数量」写出来的测试不可移植。std::set::insert返回std::pairiterator, bool的设计从 C98 就存在了C17 又给std::set和std::unordered_set加上了extract节点句柄node handle。extract是节点式容器独有的能力——可以把一个元素从容器里「摘下来」再原样「接」到另一个容器上全程不拷贝、不分配。本文的 vector 实现做不到这一点因为它的元素是连续存放的。四、把「不重复」做成类型不变量一个类的质量体现在能不能让非法状态无法表示。对集合类来说就是让外部拿不到data_的非常量引用。上面的实现只暴露了const_iterator所以for (auto x : s) { x 0; }编译不过。这是有意的——但如果集合里的元素本身是可变的比如SimpleSetstd::shared_ptrFoo改*ptr依然会破坏不变量那是元素类型的问题容器管不了。另一个常见做法是把元素设为const但这会让std::vector无法工作vector要求元素可按Erase语法赋值vectorconst T不满足。标准容器的做法正是本节采用的只暴露常量迭代器。剩下的就是拷贝与移动语义。上面的类没有任何自定义的析构、拷贝、移动函数因为成员只有一个std::vector和一个可能为空的比较器——编译器生成的默认版本就是正确的这常被称作「规则零」Rule of Zero。自己写析构函数反而容易破坏它。常见坑点插入接口不返回结果❌void insert(const T v) { data_.push_back(v); }重复元素悄悄进来「集合」名不副实。✅ 返回bool或者像std::set那样返回std::pairiterator, bool。用比较「元素是否相同」却在别处用排序❌ 同一个类里混用两套比较语义std::sort的结果和contains的判断不一致。✅ 全程统一用一套并把比较器做成模板参数。删除时无条件自移动赋值❌*it std::move(data_.back()); data_.pop_back();当it指向最后一个元素时是对自身的移动赋值。✅ 先判断it ! data_.end() - 1。用vector::erase(it)删除❌ 每次删除 O(n) 搬移集合一大就塌方。✅ 交换末尾元素再pop_back()并明确声明「顺序会被打乱」。把begin()写成返回可变迭代器❌std::vectorT::iterator begin() { return data_.begin(); }外加 const 重载用户一改元素就能造出重复。✅ 只提供const_iterator。为「集合运算」写就地修改版本还返回引用❌SimpleSet unionInPlace(const SimpleSet o)遇到s.unionInPlace(s)时正在遍历的容器被修改迭代器失效UB。✅ 要么返回新集合要么自赋值检测后走拷贝再合并。依赖std::unordered_set的遍历顺序❌ 写测试时断言「第一个元素是 X」。桶顺序是实现定义的libstdc / libc / MSVC STL 三家给出的顺序不同。✅ 断言集合内容而非顺序比较前先排序或用std::is_permutation。对自定义类型忘写哈希或比较器❌SimpleSetMyType里MyType没有operator报错信息是一大坨模板实例化堆栈。✅ 定义operator或者把Equal显式传进去。总结要点做法存储std::vector连续内存小规模下缓存友好插入先contains再push_back返回bool告知是否真的插入删除末尾元素填补空洞O(1)代价是顺序被打乱封装只暴露const_iterator把「不重复」变成类型不变量集合运算返回新对象避免别名与迭代器失效语义特化默认用std::equal_toT比较器做成模板参数何时不该手写元素多、需要 O(log n) 或 O(1) 查找时直接用std::set/std::unordered_set手写集合类的意义不在于替代标准库而在于把「不重复」这个约束的维护成本看清楚每一次修改都必须考虑它是否被破坏每一次暴露接口都必须考虑别人能不能绕过它。想明白这两点之后你会发现标准库那些看起来啰嗦的返回类型std::pairiterator, bool和只读迭代器设计都是有原因的。 C++简单集合类的实现方法
前言「集合类」这个词有歧义先把话说清楚一种理解是数学意义上的集合set——元素不重复、支持添加/删除/判存在/求交并差另一种理解是泛指容器collection——能装东西就行。这两种理解的接口设计和内部结构完全不同本文按前一种set 语义来写因为这是「集合类」这个说法在 C 语境下最常指的东西。另一个需要澄清的误解是「简单」不等于「应该用std::vector硬凑」。标准库已经提供了std::set红黑树有序和std::unordered_set哈希表无序绝大多数场景应该直接用它们。手写一个集合类的价值在于理解「不重复」这个约束是怎么在接口层被维护的、什么时候用线性查找反而更快、以及为什么教材上的实现常常在const正确性和异常安全上出问题。本文给出一个基于std::vector的顺序存储集合类元素个数少几十个以内时它比std::set更快也更好缓存然后逐条讨论接口设计中的取舍最后给出可编译的完整示例和一张与标准容器的对照表。一、集合的核心语义不重复集合与普通容器的唯一区别就是插入时不产生重复元素。这个约束在接口层表现为两点insert需要告诉调用者「到底插进去了没有」所以返回bool或返回「是否新插入」的std::pairiterator, bool这是std::set::insert的返回类型。所有修改操作之后必须能保证「任意两个元素不相等」。「相等」怎么定义对自定义类型C 里有两套语义基于operator的相等equalitystd::find用的是它基于operator的等价equivalencestd::set用的是它。标准库的惯例是关联容器默认用std::lessT也就是operator而无序容器用std::equal_toT加std::hashT。我们的顺序存储实现用operator更直观。这对自定义类型有个实际要求要么定义operator要么在构造时传入一个比较器。下面的实现用默认的std::equal_toT行为等价于。二、用 std::vector 做存储的顺序集合选std::vector做后备存储有三个理由内存连续缓存友好、遍历极快、小规模下常数因子小。代价是查找是线性的 O(n)删除需要移动元素。#include algorithm #include cstddef #include functional #include iostream #include string #include utility #include vector template typename T, typename Equal std::equal_toT class SimpleSet { public: // 插入已存在则返回 false不改变集合 bool insert(const T value) { if (contains(value)) { return false; } data_.push_back(value); return true; } bool insert(T value) { if (contains(value)) { return false; } data_.push_back(std::move(value)); return true; } // 删除返回是否真的删掉了一个元素 bool erase(const T value) { auto it std::find_if(data_.begin(), data_.end(), [value, this](const T x) { return eq_(x, value); }); if (it data_.end()) { return false; } // 用最后一个元素填补空洞O(1)但会打乱顺序 if (it ! data_.end() - 1) { *it std::move(data_.back()); } data_.pop_back(); return true; } bool contains(const T value) const { return std::find_if(data_.begin(), data_.end(), [value, this](const T x) { return eq_(x, value); }) ! data_.end(); } void clear() noexcept { data_.clear(); } std::size_t size() const noexcept { return data_.size(); } bool empty() const noexcept { return data_.empty(); } // 只读遍历暴露常量迭代器防止外部改坏「不重复」这个不变量 std::vectorT::const_iterator begin() const noexcept { return data_.begin(); } std::vectorT::const_iterator end() const noexcept { return data_.end(); } // 集合运算 SimpleSet unionWith(const SimpleSet other) const { SimpleSet result *this; for (const T x : other.data_) { result.insert(x); } return result; } SimpleSet intersect(const SimpleSet other) const { SimpleSet result; for (const T x : data_) { if (other.contains(x)) { result.insert(x); } } return result; } SimpleSet difference(const SimpleSet other) const { SimpleSet result; for (const T x : data_) { if (!other.contains(x)) { result.insert(x); } } return result; } bool equals(const SimpleSet other) const { if (size() ! other.size()) { return false; } for (const T x : data_) { if (!other.contains(x)) { return false; } } return true; } private: std::vectorT data_; Equal eq_{}; };几个设计点值得展开为什么erase用「和最后一个元素交换」而不是data_.erase(it)。vector::erase会把后面的元素整体前移一格是 O(n)而把末尾元素搬到空洞处再pop_back()是 O(1)。代价是集合内部顺序被打乱——这一点必须在文档里写清楚否则用户会依赖遍历顺序。这也是为什么这个类不叫「有序集合」。为什么要判断it ! data_.end() - 1。如果被删的正好是最后一个元素*it std::move(data_.back())就是自移动赋值。对内置类型如int没问题对std::string这类标准库类型虽然标准保证了「有效状态」但结果是指向自身的移动行为微妙且没必要。加一个判断就绕开了。eq_是成员变量而不是静态的。因为Equal可能是有状态的比如忽略大小写的比较器。std::equal_toT是无状态的空类Equal eq_{}不占空间空基类优化在成员对象上不适用但空类成员本身只占 1 字节还要考虑对齐。实际使用时int main() { SimpleSetint a; std::cout a.insert(1) \n; // 1插入成功 std::cout a.insert(1) \n; // 0已存在拒绝 a.insert(2); a.insert(3); SimpleSetint b; b.insert(3); b.insert(4); const SimpleSetint u a.unionWith(b); // {1,2,3,4} const SimpleSetint i a.intersect(b); // {3} const SimpleSetint d a.difference(b); // {1,2} std::cout u.size() i.size() d.size() \n; // 输出4 1 2 a.erase(2); std::cout a.size() a.contains(2) \n; // 2 0 return 0; }注意unionWith、intersect、difference都是返回新集合而不是就地修改。这是刻意选择赋值语义比原地修改更不容易写出别名 bug比如s s.unionWith(s)这种自赋值场景。如果确实需要就地版本再加一个void unionInPlace(const SimpleSet)会更清楚。三、和标准容器怎么选维度本文的顺序集合std::setstd::unordered_set底层结构std::vector线性存储红黑树标准只要求「平衡二叉搜索树」的复杂度哈希表链地址法或开放寻址实现自定插入O(n)O(log n)平均 O(1)最坏 O(n)查找O(n)O(log n)平均 O(1)遍历顺序插入顺序删除会打乱有序按比较器无序内存局部性最好连续差每节点一次分配中等元素类型要求operator或自定义比较器operator或自定义比较器可哈希std::hash特化迭代器失效插入可能全部失效扩容仅被删元素失效仅被删元素失效rehash 时迭代器可能失效元素少几十个以内时的表现通常最快较慢较慢关于上表的最后一行这里不给具体倍数因为那取决于元素类型、元素大小、编译器和数据分布。如果你要验证可以自己写一段插入加查找的循环用std::chrono::steady_clock计时同时用-O2编译——结论会因为元素是int还是std::string而完全不同。原理层面的判断是可靠的std::set每个节点都是一次堆分配而vector是一次分配加顺序访问在元素少到能放进几行缓存时后者的优势几乎总是压倒性的。std::unordered_set的桶增长策略、负载因子上限都是实现定义的libstdc 与 MSVC STL 的默认最大负载因子是 1.0libc 也是 1.0但桶数量的增长序列和 rehash 时机由各家自己决定标准没有规定。所以跨标准库统计「桶数量」写出来的测试不可移植。std::set::insert返回std::pairiterator, bool的设计从 C98 就存在了C17 又给std::set和std::unordered_set加上了extract节点句柄node handle。extract是节点式容器独有的能力——可以把一个元素从容器里「摘下来」再原样「接」到另一个容器上全程不拷贝、不分配。本文的 vector 实现做不到这一点因为它的元素是连续存放的。四、把「不重复」做成类型不变量一个类的质量体现在能不能让非法状态无法表示。对集合类来说就是让外部拿不到data_的非常量引用。上面的实现只暴露了const_iterator所以for (auto x : s) { x 0; }编译不过。这是有意的——但如果集合里的元素本身是可变的比如SimpleSetstd::shared_ptrFoo改*ptr依然会破坏不变量那是元素类型的问题容器管不了。另一个常见做法是把元素设为const但这会让std::vector无法工作vector要求元素可按Erase语法赋值vectorconst T不满足。标准容器的做法正是本节采用的只暴露常量迭代器。剩下的就是拷贝与移动语义。上面的类没有任何自定义的析构、拷贝、移动函数因为成员只有一个std::vector和一个可能为空的比较器——编译器生成的默认版本就是正确的这常被称作「规则零」Rule of Zero。自己写析构函数反而容易破坏它。常见坑点插入接口不返回结果❌void insert(const T v) { data_.push_back(v); }重复元素悄悄进来「集合」名不副实。✅ 返回bool或者像std::set那样返回std::pairiterator, bool。用比较「元素是否相同」却在别处用排序❌ 同一个类里混用两套比较语义std::sort的结果和contains的判断不一致。✅ 全程统一用一套并把比较器做成模板参数。删除时无条件自移动赋值❌*it std::move(data_.back()); data_.pop_back();当it指向最后一个元素时是对自身的移动赋值。✅ 先判断it ! data_.end() - 1。用vector::erase(it)删除❌ 每次删除 O(n) 搬移集合一大就塌方。✅ 交换末尾元素再pop_back()并明确声明「顺序会被打乱」。把begin()写成返回可变迭代器❌std::vectorT::iterator begin() { return data_.begin(); }外加 const 重载用户一改元素就能造出重复。✅ 只提供const_iterator。为「集合运算」写就地修改版本还返回引用❌SimpleSet unionInPlace(const SimpleSet o)遇到s.unionInPlace(s)时正在遍历的容器被修改迭代器失效UB。✅ 要么返回新集合要么自赋值检测后走拷贝再合并。依赖std::unordered_set的遍历顺序❌ 写测试时断言「第一个元素是 X」。桶顺序是实现定义的libstdc / libc / MSVC STL 三家给出的顺序不同。✅ 断言集合内容而非顺序比较前先排序或用std::is_permutation。对自定义类型忘写哈希或比较器❌SimpleSetMyType里MyType没有operator报错信息是一大坨模板实例化堆栈。✅ 定义operator或者把Equal显式传进去。总结要点做法存储std::vector连续内存小规模下缓存友好插入先contains再push_back返回bool告知是否真的插入删除末尾元素填补空洞O(1)代价是顺序被打乱封装只暴露const_iterator把「不重复」变成类型不变量集合运算返回新对象避免别名与迭代器失效语义特化默认用std::equal_toT比较器做成模板参数何时不该手写元素多、需要 O(log n) 或 O(1) 查找时直接用std::set/std::unordered_set手写集合类的意义不在于替代标准库而在于把「不重复」这个约束的维护成本看清楚每一次修改都必须考虑它是否被破坏每一次暴露接口都必须考虑别人能不能绕过它。想明白这两点之后你会发现标准库那些看起来啰嗦的返回类型std::pairiterator, bool和只读迭代器设计都是有原因的。