《C++进阶之STL》【set/map 使用介绍】

关联容器的核心特征是：

• 非线性逻辑结构：通常基于树（如：红黑树）或哈希表实现，元素间通过键值的有序性或哈希映射建立关联
  • 例如：二叉搜索树中左子树元素键值始终小于根节点，右子树元素键值始终大于根节点，形成紧密的逻辑关联
• 结构敏感性：交换元素会破坏容器的内部逻辑结构（如：树的有序性或哈希表的映射关系），导致后续操作（如：查找、插入）失效
• 关键字驱动访问：元素按关键字（Key）存储和检索，而非位置
  • 例如：map容器通过键值对(key, value)存储数据，查找时直接通过key定位，时间复杂度为

  O(logn)

  （红黑树实现）或平均

  O(1)

  （哈希表实现）

两类容器的核心差异总结：

------------set------------

一、介绍

cplusplus网站上关于C++的set容器的介绍：set - C++ Reference

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码语言：javascript

AI代码解释

template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;

关于 C++ STL 中set容器的模板参数说明：

• 元素类型（T）： set 底层存储的关键字类型，需保证该类型支持比较操作（默认需支持<运算符）

比较器（Compare，默认less<T>）：用于定义元素间的排序规则。

若T不支持默认比较（如：自定义类），或需自定义排序逻辑，可通过仿函数重载比较规则

代码语言：javascript

AI代码解释

struct MyComparator { bool operator()(const T& a, const T& b) const { return a.custom_key < b.custom_key; // 自定义比较逻辑 } }; set<T, MyComparator> mySet; // 使用自定义比较器

内存分配器（Allocator，默认allocator<T>）：负责管理 set 的内存分配与释放。

如需优化内存使用（如：高频插入/删除场景），可自定义分配器（如：内存池）

代码语言：javascript

AI代码解释

set<T, less<T>, MyAllocator<T>> mySet; // 使用自定义分配器

C++ 标准模板库（STL）中的set容器相关知识，主要可以分为以下一个部分：

1. 成员函数：提供了set 容器的各类操作接口，涵盖元素插入、删除、查找、迭代、容量管理等功能。

在这里插入图片描述

1. set容器的常见构造

在这里插入图片描述

代码语言：javascript

AI代码解释

// constructing sets #include <iostream> #include <set> //1.定义一个普通函数作为比较函数，用于比较两个整数的大小 bool fncomp(int lhs, int rhs) { return lhs < rhs; } //2.定义一个函数对象（仿函数）类，用于比较两个整数的大小 struct classcomp { bool operator() (const int& lhs, const int& rhs) const { return lhs < rhs; } }; int main() { /*------------------使用不同的构造函数创建set容器------------------*/ //1.使用“默认构造函数”创建一个空的set，元素类型为int std::set<int> s1; //2.使用“迭代器范围构造函数”创建包含5个元素的set，初始化元素来自数组myints int myints[] = { 10,20,30,40,50 }; std::set<int> s2(myints, myints + 5); //3.使用“拷贝构造函数”创建set容器third，third是second的一个副本 std::set<int> s3(s2); //4.使用“迭代器构造函数”创建set，通过迭代器范围[second.begin(), second.end())初始化 std::set<int> s4(s2.begin(), s2.end()); //注意：这实际上和拷贝构造效果相同 /*------------------使用不同的方式作为set容器的比较器------------------*/ //5.使用“自定义的函数对象”作为比较器 std::set<int, classcomp> s5; //注意：classcomp是一个定义了函数调用运算符的结构体 //6.使用“函数指针”作为比较器 //6.1：首先定义一个函数指针指向fncomp函数 bool(*fn_pt)(int, int) = fncomp; //6.2：然后在模板参数中指定比较器类型，并在构造函数中传入函数指针 std::set<int, bool(*)(int, int)> s6(fn_pt); return 0; }

在这里插入图片描述

2. 容量的操作

std::set::size

在这里插入图片描述

代码语言：javascript

AI代码解释

// set::size #include <iostream> #include <set> int main() { std::set<int> myints; std::cout << "初始状态下的set大小的size为: " << myints.size() << '\n'; for (int i = 0; i < 10; ++i) myints.insert(i); std::cout << "插入10个元素后set大小的size为: " << myints.size() << '\n'; myints.insert(100); std::cout << "插入元素100后set大小的size为: " << myints.size() << '\n'; myints.erase(5); std::cout << "删除5个元素后set大小的size为: " << myints.size() << '\n'; return 0; }

在这里插入图片描述

std::set::empty

在这里插入图片描述

代码语言：javascript

AI代码解释

// set::empty #include <iostream> #include <set> int main() { std::set<int> myset; myset.insert(20); myset.insert(30); myset.insert(10); std::cout << "myset容器中的内容为:"; while (!myset.empty()) { std::cout << ' ' << *myset.begin(); myset.erase(myset.begin()); } std::cout << '\n'; return 0; }

在这里插入图片描述

3. 修改的操作

std::set::clear

在这里插入图片描述

代码语言：javascript

AI代码解释

// set::clear #include <iostream> #include <set> int main() { std::set<int> myset; myset.insert(100); myset.insert(200); myset.insert(300); std::cout << "初始状态下myset容器中的内容为:"; for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; myset.clear(); myset.insert(1101); myset.insert(2202); std::cout << "进行清空和插入操作后myset容器中的内容为:"; for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; return 0; }

在这里插入图片描述

std::set::swap

在这里插入图片描述

代码语言：javascript

AI代码解释

// swap sets #include <iostream> #include <set> int main() { int myints[] = { 12,75,10,32,20,25 }; std::set<int> first(myints, myints + 3); // 10,12,75 std::set<int> second(myints + 3, myints + 6); // 20,25,32 first.swap(second); std::cout << "交换后first容器中的内容为:"; for (std::set<int>::iterator it = first.begin(); it != first.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; std::cout << "交换后second容器中的内容为:"; for (std::set<int>::iterator it = second.begin(); it != second.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; return 0; }

在这里插入图片描述

std::set::insert

在这里插入图片描述

代码语言：javascript

AI代码解释

// set::insert (C++98) #include <iostream> #include <set> int main() { //1.创建一个存储int类型的set容器 std::set<int> myset; //2.定义一个迭代器，用于指向set中的元素 std::set<int>::iterator it; //3.定义一个pair对象，用于接收insert函数的返回值 std::pair<std::set<int>::iterator, bool> ret; /* 注意事项： * 1.第一个元素是迭代器，指向插入的元素或已存在的元素 * 2.第二个元素是bool值，表示插入是否成功 */ /*--------------------插入形式一：单个元素的插入--------------------*/ for (int i = 1; i <= 5; ++i) { myset.insert(i * 10); } //1.尝试插入已存在的元素20（元素已存在） ret = myset.insert(20); /* 注意事项： * 1.返回的pair中bool值为false，表示插入失败 * 2.迭代器指向已存在的元素20 */ //2.如果插入失败，将迭代器it指向已存在的元素20 if (ret.second == false) it = ret.first; std::cout << "myset容器中的内容为:"; for (it = myset.begin(); it != myset.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; /*--------------------插入形式二：带提示位置的插入--------------------*/ myset.insert(it, 25); //注意：提示位置为it（指向元素20），实际插入位置由set的有序性决定 myset.insert(it, 24); //元素24会被插入到20之后（按升序排列） myset.insert(it, 26); /* 注意事项： * 1.提示位置对插入位置没有帮助（26应在25之后） * 2.提示位置仅作为优化建议，不影响最终插入位置 */ std::cout << "myset容器中的内容为:"; for (it = myset.begin(); it != myset.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; /*--------------------插入形式三：范围插入--------------------*/ int myints[] = { 5,10,15 }; myset.insert(myints, myints + 3); //注意：会插入5, 10, 15三个元素，但10已存在，不会重复插入 std::cout << "myset容器中的内容为:"; for (it = myset.begin(); it != myset.end(); ++it) { std::cout << ' ' << *it; } std::cout << '\n'; return 0; }