序列式容器和关联式容器
序列式容器：
序列式容器是一组用于存储数据的容器，其中的数据按照它们在容器中的位置进行存储和访问。序列式容器提供了对元素的线性访问和操作，其主要特点包括：
- 线性存储： 序列式容器按照元素在容器中的插入顺序线性存储。元素在容器中的位置是固定的，与键值无关。
- 支持重复元素： 序列式容器允许存储重复的元素，同一个值可以出现多次。
- 提供随机访问： 序列式容器支持随机访问，可以通过索引或迭代器快速访问任何位置的元素。
- 不排序元素： 序列式容器不会自动对元素进行排序，元素按照插入的顺序存储。
C++标准库中的序列式容器包括 std::vector、std::deque、std::list、std::array 等。这些容器适用于需要按顺序处理数据的情况，如数组、列表、队列等。
总结：
- 关联式容器适用于需要高效的查找和排序的情况，数据按键值有序存储。
- 序列式容器适用于需要线性存储和随机访问的情况，元素按插入顺序存储。
- 选择容器类型取决于具体的需求和操作。关联式容器适用于需要快速查找和排序的情况，而序列式容器适用于需要按顺序处理数据的情况。
关联式容器：
关联式容器是一组用于存储数据的容器，其中的数据按照某种规则关联起来，通常是基于键值的关联。关联式容器提供了一种高效的方式来查找、插入和删除元素，其主要特点包括：
- 基于键值的存储： 关联式容器通过键值来存储和访问元素。每个元素都有一个关联的键，通过该键可以唯一标识和访问元素。
- 有序存储： 关联式容器通常会按照键值的顺序进行排序。这使得元素可以按照一定的顺序进行迭代，例如升序或降序。
- 高效的查找： 关联式容器提供了高效的查找操作。由于元素按键值有序存储，可以使用二分查找等算法来快速找到特定键对应的元素。
- 不允许重复键： 关联式容器通常不允许存储重复的键值。每个键只能对应一个元素。
C++标准库中的关联式容器包括 std::set、std::multiset、std::map、std::multimap 等。这些容器适用于需要高效查找和排序的情况，如字典、集合等。
键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义
SGI-STL中关于键值对的定义
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} };
树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构
C++标准库提供了四种主要的树形结构关联式容器，它们分别是 std::set、std::multiset、std::map 和 std::multimap。这些容器都是基于树的数据结构，通常使用红黑树实现，用于存储键值对，并提供高效的查找和排序功能。以下是对这四种容器的详细解释：
- std::set：
std::set是一个集合容器，它存储唯一的键值（key），不允许重复的键。- 元素按照键值自动排序（通常升序），这使得查找和插入操作都非常高效。
- 提供了
insert、erase、find等操作来管理元素集合。
- std::multiset：
std::multiset与std::set类似，但允许存储重复的键值。因此，它可以包含相同的键多次。- 元素按照键值自动排序，查找和插入操作也非常高效。
- 提供了
insert、erase、find等操作。
- std::map：
std::map是一个键值对容器，每个键都唯一对应一个值。- 元素按照键值自动排序，通常按照键的升序顺序排列。
- 提供了
insert、erase、find等操作来管理键值对。
- std::multimap：
std::multimap与std::map类似，但允许存储相同的键对应不同的值，因此一个键可以对应多个值。- 元素按照键值自动排序，查找和插入操作非常高效。
- 提供了
insert、erase、find等操作。
这些容器的共同特点是它们的元素是按照键值有序存储的，这使得它们适用于需要快速查找和自动排序的情况。它们使用平衡二叉树（通常是红黑树）来实现这些功能，保持了插入、删除和查找的平均时间复杂度为O(log N)。
选择哪种容器取决于需求。如果需要存储唯一的键或键值对，可以选择 std::set 或 std::map。如果需要允许重复的键或键对应多个值，可以选择 std::multiset 或 std::multimap。这些容器提供了丰富的操作，可以满足各种数据组织和访问的需求。
set
1.set模板参数列表
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;
T（class T）：这是模板的第一个参数，表示存储在set容器中的元素的数据类型。set会存储类型为T的元素。Compare（class Compare = less<T>）：这是模板的第二个参数，表示用于比较元素之间的顺序的比较函数。默认情况下，它采用less<T>，它使用元素的小于运算符<来进行比较。您可以提供自定义的比较函数，以定义元素之间的排序规则。这个比较函数必须是一个可调用的二元谓词，它接受两个参数（const T&类型）并返回一个bool值，指示它们的顺序。Alloc（class Alloc = allocator<T>）：这是模板的第三个参数，表示用于分配和管理内存的分配器类型。默认情况下，它采用std::allocator<T>，这是C++标准库提供的分配器。您可以提供自定义的分配器类型，以满足特定的内存管理需求。
std::set是一个有序容器，它以红黑树（Red-Black Tree）作为底层数据结构来存储元素。红黑树是一种自平衡二叉搜索树，保持了元素的有序性，并且允许高效的插入、删除和查找操作。std::set中的元素是唯一的，即相同的元素只会被存储一次。
成员类型
2.set的构造
关于C++标准库中std::set容器构造函数的不同形式和重载，以及它们的用途的解释：
explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());：
- 这是默认构造函数，创建一个空的
std::set容器。 - 参数
comp用于指定比较函数，它用于确定元素的顺序。默认情况下，使用key_compare()，即容器类型中指定的比较函数。 - 参数
alloc用于指定分配器，用于管理内存。默认情况下，使用allocator_type()，即容器类型中指定的分配器。
#include <iostream> #include <set> int main() { // 使用默认构造函数创建一个空的 set std::set<int> mySet; // 向 set 中插入元素 mySet.insert(5); mySet.insert(2); mySet.insert(8); // 输出 set 的内容 for (const int& value : mySet) { std::cout << value << " "; } std::cout << std::endl; return 0; }
template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());：
- 这是范围构造函数，创建一个
std::set容器，并初始化其内容，从范围[first, last)中的元素。 - 参数
first和last是迭代器，用于指定范围。容器将包含该范围内的元素。 - 参数
comp和alloc与默认构造函数中的含义相同，用于指定比较函数和分配器。
#include <iostream> #include <set> #include <vector> int main() { // 创建一个包含 vector 中元素的 set std::vector<int> vec = {3, 1, 4, 1, 5, 9}; std::set<int> mySet(vec.begin(), vec.end()); // 输出 set 的内容 for (const int& value : mySet) { std::cout << value << " "; } std::cout << std::endl; return 0; }
set (const set& x);：
- 这是拷贝构造函数，创建一个新的
std::set容器，并使用另一个set容器x的内容初始化它。 - 这个构造函数用于创建一个副本，将
x中的所有元素复制到新容器中。
#include <iostream> #include <set> int main() { // 创建一个 set 并初始化 std::set<int> set1 = {1, 2, 3}; // 使用拷贝构造函数创建一个新的 set，复制 set1 的内容 std::set<int> set2(set1); // 输出 set2 的内容 for (const int& value : set2) { std::cout << value << " "; } std::cout << std::endl; return 0; }
- 这些构造函数提供了不同的方式来初始化和创建
std::set容器，以适应不同的需求。您可以根据需要选择适当的构造函数来创建和初始化std::set容器，以存储和管理数据。
赋值运算符重载
set& operator= (const set& x); 是C++标准库中std::set容器的赋值运算符（operator=）重载函数的签名。
这个赋值运算符用于将一个std::set容器的内容复制给另一个std::set容器。具体来说，它将右操作数（x，另一个std::set容器）的内容复制到左操作数（调用该运算符的std::set容器）中，并返回左操作数的引用。
下面是赋值运算符的使用示例：
std::set<int> set1 = {1, 2, 3}; std::set<int> set2; // 使用赋值运算符将 set1 的内容复制到 set2 set2 = set1; // 现在 set2 包含了 set1 的内容
在上面的示例中，set2 = set1 使用赋值运算符将set1的内容复制到set2，使得set2包含了与set1相同的元素。
需要注意的是，赋值运算符会删除左操作数原来的内容，并用右操作数的内容替代它。这意味着在赋值之后，左操作数的内容将与右操作数相同，而原来的内容将被销毁。
这个赋值运算符对于将一个std::set容器的内容复制到另一个容器非常有用，可以用于容器之间的数据交换和拷贝。
3.set迭代器
这些函数是C++标准库中std::set容器的成员函数，用于获取不同类型的迭代器和常量迭代器，以便遍历std::set容器的元素。以下是这些迭代器和常量迭代器的描述：
- begin：返回一个迭代器，指向
std::set容器中第一个元素的位置。 - end：返回一个迭代器，指向
std::set容器中超出最后一个元素的位置。 - rbegin：返回一个反向迭代器，指向
std::set容器中最后一个元素的位置。使用反向迭代器可以逆序遍历容器。 - rend：返回一个反向迭代器，指向
std::set容器中超出第一个元素的位置。它通常与rbegin一起使用，以定义逆序遍历的结束点。 - cbegin：返回一个常量迭代器，指向
std::set容器中第一个元素的位置。常量迭代器用于遍历容器并防止修改容器中的元素。 - cend：返回一个常量迭代器，指向
std::set容器中超出最后一个元素的位置。 - crbegin：返回一个常量反向迭代器，指向
std::set容器中最后一个元素的位置。常量反向迭代器用于逆序遍历容器，并防止修改容器中的元素。 - crend：返回一个常量反向迭代器，指向
std::set容器中超出第一个元素的位置。通常与crbegin一起使用，以定义逆序遍历的结束点。
示例：
#include <iostream> #include <set> int main() { // 创建一个 std::set 容器并初始化 std::set<int> mySet = {5, 2, 8, 1, 9}; // 使用 begin 和 end 迭代器遍历容器 std::cout << "正序遍历：" << std::endl; for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 使用 rbegin 和 rend 反序遍历容器 std::cout << "逆序遍历：" << std::endl; for (std::set<int>::reverse_iterator rit = mySet.rbegin(); rit != mySet.rend(); ++rit) { std::cout << *rit << " "; } std::cout << std::endl; // 使用 cbegin 和 cend 常量迭代器遍历容器 std::cout << "使用常量迭代器：" << std::endl; for (std::set<int>::const_iterator cit = mySet.cbegin(); cit != mySet.cend(); ++cit) { std::cout << *cit << " "; } std::cout << std::endl; // 使用 crbegin 和 crend 常量反序遍历容器 std::cout << "使用常量反序迭代器：" << std::endl; for (std::set<int>::const_reverse_iterator crit = mySet.crbegin(); crit != mySet.crend(); ++crit) { std::cout << *crit << " "; } std::cout << std::endl; return 0; }
输出：
正序遍历： 1 2 5 8 9 逆序遍历： 9 8 5 2 1 使用常量迭代器： 1 2 5 8 9 使用常量反序迭代器： 9 8 5 2 1
这个示例演示了如何使用不同类型的迭代器来遍历std::set容器中的元素。正序遍历使用begin和end迭代器，逆序遍历使用rbegin和rend反向迭代器，常量迭代器使用cbegin和cend，常量反序迭代器使用crbegin和crend。这些迭代器允许您以不同的方式访问容器中的元素，并提供了对元素的只读访问（对于常量迭代器）或读写访问（对于非常量迭代器）
4.set容器函数
这里是关于C++标准库中std::set容器的容量相关成员函数的解释和示例：
- empty（测试容器是否为空）：
bool empty() const是一个公有成员函数，用于测试容器是否为空。- 如果容器为空，返回
true；否则，返回false。
- 示例：
std::set<int> mySet; if (mySet.empty()) { std::cout << "容器为空" << std::endl; } else { std::cout << "容器不为空" << std::endl; }
- size（返回容器大小）：
size_type size() const是一个公有成员函数，用于返回容器中元素的数量。- 返回一个无符号整数类型 (
size_type)，表示容器中元素的个数。
- 示例：
std::set<int> mySet = {1, 2, 3, 4, 5}; std::cout << "容器的大小为: " << mySet.size() << std::endl;
- max_size（返回最大可能大小）：
size_type max_size() const是一个公有成员函数，用于返回容器的最大可能大小。- 返回一个无符号整数类型 (
size_type)，表示容器可以容纳的最大元素数量，这取决于系统和编译器。
- 示例：
std::set<int> mySet; std::cout << "容器的最大可能大小为: " << mySet.max_size() << std::endl;
这些容量相关的成员函数允许您查询容器的状态，例如检查容器是否为空、获取容器的大小以及了解容器可以容纳的最大元素数量。这对于在使用容器时进行状态检查和资源规划非常有用。
5.set修改器函数
std::set容器的修改器（Modifiers）相关成员函数，它们用于修改std::set容器的内容：
- insert（插入元素）：
std::pair<iterator, bool> insert(const value_type& val);iterator insert(iterator position, const value_type& val);template <class InputIterator> void insert(InputIterator first, InputIterator last);- 这些成员函数用于向
std::set容器中插入元素。它们允许插入单个元素或一组元素。 - 如果插入成功，
insert函数返回一个迭代器指向插入的元素（或已存在的元素），以及一个bool值指示是否插入成功。
- erase（删除元素）：
iterator erase(iterator position);size_type erase(const key_type& key);iterator erase(iterator first, iterator last);- 这些成员函数用于从
std::set容器中删除元素。您可以提供要删除的元素的位置或键（key）。 erase函数返回一个迭代器，指向被删除元素之后的位置。
- swap（交换内容）：
void swap(set& x);- 这个成员函数用于交换两个
std::set容器的内容，使它们互相包含对方的元素。
- clear（清除内容）：
void clear();- 这个成员函数用于清除容器中的所有元素，使容器变为空。
- emplace（构造并插入元素）：
template <class... Args> pair<iterator, bool> emplace(Args&&... args);- 这个成员函数用于通过构造新元素并插入容器来添加新元素。它通过接受参数包（parameter pack）来构造元素，并返回插入的元素迭代器和一个
bool值指示是否插入成功。
- emplace_hint（构造并插入元素，带有提示位置）：
template <class... Args> iterator emplace_hint(iterator position, Args&&... args);- 这个成员函数与
emplace类似，但允许提供一个插入位置的提示（iterator position），以便更高效地插入新元素。
示例：
#include <iostream> #include <set> int main() { // 创建一个 std::set 容器并初始化 std::set<int> mySet = {5, 2, 8, 1, 9}; // 输出容器的内容 std::cout << "容器的内容:"; for (const int& value : mySet) { std::cout << " " << value; } std::cout << std::endl; // 使用 insert 插入元素 std::pair<std::set<int>::iterator, bool> result1 = mySet.insert(3); // 插入元素3 std::pair<std::set<int>::iterator, bool> result2 = mySet.insert(5); // 尝试插入重复元素5 if (result1.second) { std::cout << "成功插入元素3" << std::endl; } else { std::cout << "元素3已存在" << std::endl; } if (result2.second) { std::cout << "成功插入元素5" << std::endl; } else { std::cout << "元素5已存在" << std::endl; } // 输出修改后的容器内容 std::cout << "修改后的容器内容:"; for (const int& value : mySet) { std::cout << " " << value; } std::cout << std::endl; // 使用 erase 删除元素 mySet.erase(2); // 删除元素2 // 输出删除元素后的容器内容 std::cout << "删除元素后的容器内容:"; for (const int& value : mySet) { std::cout << " " << value; } std::cout << std::endl; // 使用 emplace 插入元素（构造并插入） mySet.emplace(6); // 插入元素6 // 输出插入元素后的容器内容 std::cout << "插入元素后的容器内容:"; for (const int& value : mySet) { std::cout << " " << value; } std::cout << std::endl; return 0; }
输出：
容器的内容: 1 2 5 8 9 成功插入元素3 元素5已存在 修改后的容器内容: 1 2 3 5 8 9 删除元素后的容器内容: 1 3 5 8 9 插入元素后的容器内容: 1 3 5 6 8 9
