珠海制作公司网站,长安网站建设好吗,wordpress最简易主题,把网站制作成app目录 1. 关联式容器
2. 键值对pair
3. 树形结构的关联式容器
4. set
4.1 set的介绍
4.2 set的构造
4.3 set的迭代器
4.4 set的容量
4.5 set的常用函数
5. multiset
6. map
6.1 map的介绍
6.2 map的构造
6.3 map的迭代器
6.4 map的容量
6.5 map的operator[]
6.6…目录 1. 关联式容器
2. 键值对pair
3. 树形结构的关联式容器
4. set
4.1 set的介绍
4.2 set的构造
4.3 set的迭代器
4.4 set的容量
4.5 set的常用函数
5. multiset
6. map
6.1 map的介绍
6.2 map的构造
6.3 map的迭代器
6.4 map的容量
6.5 map的operator[]
6.6 map的常用函数
7. multimap 1. 关联式容器
在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、 forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面 存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别
关联式容器associative containers与序列式容器sequential containers是C标准库中的两种不同类型的容器。 序列式容器是一种按照元素在容器中的位置进行存储和访问的容器。它们按照元素的插入顺序进行存储并且支持顺序访问元素的特性。常见的序列式容器有vector、deque、list和forward_list。 关联式容器是一种按照键值key进行存储和访问的容器。它们通过一对键值对key-value pair来存储元素其中的键key用于唯一标识元素并且支持根据键值进行快速检索的特性。常见的关联式容器有set、multiset、map和multimap。 2. 键值对pair
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然 有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first; //keyT2 second; //value//构造函数pair() : first(T1()), second(T2()){}pair(const T1 a, const T2 b) : first(a), second(b){}
};
所以C 中的键值对是通过 pair 类来表示的。
pair包含两个成员变量first和second分别表示两个值的类型T1和T2。我们可以使用pair来创建键值对或者存储两个值。
int main()
{// 创建一个键值对pairint, string student(1, Alice);// 访问键值对的值cout student.first : student.second endl;// 修改键值对的值student.first 2;student.second Bob;// 创建临时键值对pairint, string temp(3, Charlie);// 使用make_pair创建临时键值对auto temp2 make_pair(4, David);return 0;
}
pair可以用于存储键值对也可以用于其他需要存储两个不同类型的值的场景。它在C标准库中被广泛使用例如在map、unordered_map等容器中存储键值对。
此外库中还设计了一个函数模板 make_pair, 可以根据传入的参数去调用 pair 构建对象并返回。
template class T1, class T2
constexpr pairV1, V2 make_pair(T1 t1, T2 t2);make_pair接受两个参数t1和t2并将它们打包为一个pair对象并返回。make_pair会自动推导出pair对象中的第一个值和第二个值的类型。 以下是使用make_pair创建pair对象的示例
int main()
{// 创建pair对象auto p1 make_pair(1, Alice);// 创建pair对象并指定类型pairint, string p2 make_pair(2, Bob);// 输出pair对象的值cout p1.first : p1.second endl;cout p2.first : p2.second endl;return 0;
}
make_pair可以方便地创建pair对象无需显式指定类型编译器会根据参数类型进行类型推导。它常用于在容器中插入键值对或者返回键值对的函数中。
3. 树形结构的关联式容器
根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结 构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一 个容器。
4. set
4.1 set的介绍
set容器它是一个关联容器用于存储唯一的元素且按照一定的顺序排列。set容器中的元素按照默认的排序顺序存储或者可以通过自定义的排序函数进行排序。set容器实际上是一个红黑树red-black tree实现的。
set容器中的元素会自动按照键的顺序进行排序保持元素的有序性。同时set容器中的元素是唯一的即相同的元素只能出现一次。 4.2 set的构造
set容器可以使用多种方式进行构造以下是常见的构造方式
1. 默认构造函数
setint mySet; // 创建一个空的set容器2. 使用迭代器构造
vectorint vec {1, 2, 3, 4, 5};
setint mySet(vec.begin(), vec.end()); // 使用vec容器中的元素构造set容器3. 使用初始化列表构造
setint mySet {1, 2, 3, 4, 5}; // 使用初始化列表中的元素构造set容器4. 拷贝构造函数
setint mySet1 {1, 2, 3, 4, 5};
setint mySet2(mySet1); // 使用另一个set容器的副本构造新的set容器需要注意的是set容器中的元素默认按照升序进行排序。如果希望使用自定义的排序规则可以在构造过程中提供一个比较函数对象作为参数或者通过重载元素类型的比较运算符来实现。
例如如果要创建一个按照降序排序的set容器可以使用以下方式构造
struct Compare
{bool operator()(int a, int b) const {return a b;}
};setint, Compare mySet; // 使用自定义的比较函数对象构造set容器4.3 set的迭代器
set容器提供了两种类型的迭代器正向迭代器和反向迭代器。
正向迭代器
begin()返回指向set容器中第一个元素的迭代器。end()返回指向set容器中最后一个元素之后位置的迭代器。
int main()
{setint s1 { 1, 4, 2, 3, 5 };setint::iterator it s1.begin();while (it ! s1.end()){cout *it ;it;}cout endl;return 0;
} 反向迭代器
rbegin()返回指向set容器中最后一个元素的迭代器。rend()返回指向set容器中第一个元素之前位置的迭代器。
int main()
{setint s1 { 1, 4, 2, 3, 5 };setint::reverse_iterator rit s1.rbegin();while (rit ! s1.rend()){cout *rit ;rit;}cout endl;return 0;
} 4.4 set的容量
set容器提供了以下几个容量函数来获取容器的大小和容量信息
size()返回set容器中元素的个数。empty()判断set容器是否为空如果为空返回true否则返回false。max_size()返回set容器能够容纳的最大元素个数这个值取决于系统或者编译器的限制。
int main()
{setint mySet { 1, 4, 2, 3, 5 };// 使用size()函数获取set的大小cout Set的大小 mySet.size() endl;// 使用empty()函数判断set是否为空if (mySet.empty()) {cout Set为空 endl;}else {cout Set不为空 endl;}// 使用max_size()函数获取set的最大容量cout Set的最大容量 mySet.max_size() endl;return 0;
} 4.5 set的常用函数
set容器提供了一些常用的函数来进行元素的插入、删除、查找等操作。下面是set容器的一些常用函数 插入元素 insert(val)将元素val插入到set容器中。 insert(first, last)将区间[first, last)内的元素插入到set容器中。 删除元素 erase(val)删除set容器中与val相等的元素。 erase(iterator)删除指定迭代器指向的元素。 erase(first, last)删除区间[first, last)内的元素。 clear()清空set容器中的所有元素。 查找元素 find(val)在set容器中查找与val相等的第一个元素如果找到返回指向该元素的迭代器否则返回end()迭代器。 count(val)返回set容器中与val相等的元素的个数由于set容器中元素的唯一性所以返回值只能是0或1。 lower_bound(val)返回一个迭代器指向set容器中第一个不小于val的元素如果不存在这样的元素则返回set容器的end()迭代器。 upper_bound(val)返回一个迭代器指向set容器中第一个大于val的元素如果不存在这样的元素则返回set容器的end()迭代器。 equal_range(val)返回一个pair对象包含一个迭代器范围表示与val相等的元素在set容器中的位置。如果不存在这样的元素则返回一个pair对象两个迭代器都指向set容器的end()位置。
需要注意的是set容器中的元素是按照一定的排序方式进行存储的默认情况下是按照升序排列。另外由于set容器中元素的唯一性所以插入重复的元素时只会插入一个。
int main()
{setint mySet;// 插入元素到setmySet.insert(10);mySet.insert(20);mySet.insert(30);// 查找元素setint::iterator it mySet.find(20);if (it ! mySet.end()) {cout 元素存在 endl;}else {cout 元素不存在 endl;}// 删除元素mySet.erase(20);// 获取set的大小cout set的大小为 mySet.size() endl;// 清空setmySet.clear();// 判断set是否为空if (mySet.empty()) {cout set为空 endl;}else {cout set不为空 endl;}return 0;
}
5. multiset
multiset是C STL中的容器它是一个有序的集合可以存储多个相同的元素。
此外multiset 查找冗余的数据时返回的是中序遍历中第一次出现的元素 。
multiset的特点包括
元素的插入是有序的插入操作会将元素按照一定的顺序插入到容器中。允许存储重复的元素即可以插入相同的元素多次。multiset中的元素是自动排序的默认按照元素的升序进行排序也可以通过指定比较函数来按照其他方式进行排序。支持快速的插入和删除操作时间复杂度为O(logN)。
int main()
{multisetint numbers;// 向multiset中插入元素numbers.insert(1);numbers.insert(3);numbers.insert(2);numbers.insert(2);cout multiset中的元素 endl;for (auto it numbers.begin(); it ! numbers.end(); it) {cout *it ;}cout endl;// 查找multiset中的元素auto it numbers.find(2);if (it ! numbers.end()) {cout 找到元素2 endl;}else {cout 未找到元素2 endl;}// 删除multiset中的元素numbers.erase(2);cout 删除元素2后的multiset endl;for (auto it numbers.begin(); it ! numbers.end(); it) {cout *it ;}cout endl;return 0;
}
6. map
6.1 map的介绍
map容器它是一个关联容器用于存储键值对key-value pairs。其中的每个元素都由一个键key和一个值value组成。map容器中的元素按照键的顺序进行排序并且每个键只能在map中出现一次。因此可以通过键快速查找和访问对应的值。map容器实际上是一个红黑树red-black tree实现的。
map的特点包括 键唯一性每个键只能在map中出现一次如果插入相同键的元素后面的插入会覆盖前面的。 按键排序map中的元素按照键的大小进行排序默认是按照升序排序。 二叉搜索树实现map内部使用红黑树Red-Black Tree来实现元素的存储和排序因此插入、查找和删除等操作的时间复杂度都是O(log n)。 动态大小map的大小可以根据需要动态地增加或减小。 key: 键值对中key的类型 T 键值对中value的类型 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户 自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的 空间配置器 6.2 map的构造
在C中可以使用多种方式构造一个map对象。下面列举几种常用的构造方式
1. 默认构造函数创建一个空的map对象。
mapKey, Value myMap;2. 初始化列表构造函数通过初始化列表创建一个包含多个键值对的map对象。
mapint, string myMap { {1, one}, {2, two}, {3, three} };3. 使用迭代器构造函数通过指定起始和结束迭代器创建一个包含其他容器中元素的map对象。
vectorpairint, string vec { {1, one}, {2, two}, {3, three} };
mapint, string myMap(vec.begin(), vec.end());4. 复制构造函数以另一个map对象作为参数创建一个与其相同的map对象。
mapint, string anotherMap(myMap);5. 移动构造函数以另一个map对象的右值引用作为参数创建一个新的map对象同时将原来的map对象置为空。
mapint, string newMap(move(myMap));需要注意的是在使用map构造函数时键值对的顺序并不影响map中元素的插入顺序因为map内部是按照键的排序顺序进行存储和访问的。
此外使用map的构造函数创建新的map对象时会根据键的类型进行比较和排序默认是使用lessKey来进行比较。如果键的类型没有定义比较函数则需要通过自定义比较函数或提供自定义的比较类作为额外的模板参数来使用。
6.3 map的迭代器
map提供了两种类型的迭代器正向迭代器和反向迭代器
正向迭代器
begin()返回指向map中第一个元素的迭代器。end()返回指向map中最后一个元素之后位置的迭代器相当于尾后迭代器。
int main()
{mapint, string myMap { {1, one}, {2, two}, {3, three} };auto it myMap.begin();while (it ! myMap.end()){cout it-first : it-second endl;it;}return 0;
}
反向迭代器
rbegin()返回指向map中最后一个元素的迭代器。rend()返回指向map中第一个元素之前位置的迭代器相当于尾前迭代器。
int main()
{mapint, string myMap { {1, one}, {2, two}, {3, three} };auto rit myMap.rbegin();while (rit ! myMap.rend()){cout rit-first : rit-second endl;rit;}return 0;
}
另外C11引入了范围-based for循环可以更简洁地遍历map对象。
int main()
{mapint, string myMap { {1, one}, {2, two}, {3, three} };for (const auto pair : myMap) {cout pair.first : pair.second endl;}return 0;
}
这种写法可以自动推导出迭代器的类型并且使用引用避免了元素的复制。
6.4 map的容量
获取容量信息
size()函数返回map中键-值对的数量。empty()函数如果map为空则返回true否则返回false。
int main()
{mapint, string myMap { {1, one}, {2, two}, {3, three} };cout Size of map: myMap.size() endl;cout Is map empty? (myMap.empty() ? Yes : No) endl;return 0;
}
6.5 map的operator[]
map的 operator[] 函数用于访问 map 中指定键的值。如果键存在则返回对应的值如果键不存在则会插入一个新的键值对并返回默认构造的值。
int main()
{mapint, string map;// 插入键值对map[1] Alice;map[2] Bob;map[3] Charlie;// 访问指定键的值string name1 map[1];cout 键 1 对应的值是 name1 endl;string name4 map[4];cout 键 4 对应的值是 name4 endl;// 修改指定键的值map[1] Alex;// 输出所有键值对cout 所有键值对 endl;for (const auto pair : map) {cout 键: pair.first 值: pair.second endl;}return 0;
} 6.6 map的常用函数
map是C STL提供的关联容器提供了一系列的成员函数来操作和管理map。以下是一些map常用的函数 插入元素 insert()将键值对插入到map中。 emplace()在map中就地构造元素。 emplace_hint()在指定位置之前插入元素。 访问元素 at()返回给定键对应的值并进行边界检查。 operator[]根据键访问对应的值如果键不存在则插入对应的键值对。 find()查找给定键的位置并返回一个迭代器。 count()返回给定键在map中出现的次数。 删除元素 erase()删除map中指定的元素或者一个范围内的元素。 clear()清空map中的所有元素。
int main()
{mapstring, int scores;// 添加学生的成绩scores[Alice] 90;scores[Bob] 85;scores[Charlie] 95;scores[David] 80;// 更新学生的成绩scores[Alice] 5;// 查找学生的成绩string studentName Bob;if (scores.find(studentName) ! scores.end()) {cout studentName 的成绩是 scores[studentName] endl;}else {cout 找不到 studentName 的成绩 endl;}// 删除学生的成绩scores.erase(David);// 遍历输出所有学生的成绩cout 所有学生的成绩 endl;for (const auto pair : scores) {cout pair.first 的成绩是 pair.second endl;}return 0;
} 7. multimap
multimap是C标准库中的一个关联容器它允许存储一对键-值对其中键可以重复。multimap内部会根据键的排序规则自动对元素进行排序并且可以高效地进行插入、删除和查找操作。
与map不同multimap允许多个键相同的元素存在因此它可以用于存储重复键的场景。multimap的实现基于红黑树保证了元素的有序性并提供了一系列函数来操作和访问multimap中的元素。
multimap的特点包括
元素有序multimap中的元素按照键的排序规则自动进行排序可以通过自定义比较函数来指定键的排序规则。允许重复键multimap允许存储多个键相同的元素。动态大小multimap可以动态地添加或删除元素它会自动调整内部的存储空间。高效的插入和删除multimap内部使用红黑树实现可以在O(log n)的时间复杂度内进行插入、删除和查找操作。查找效率高multimap提供了快速的查找操作可以在O(log n)的时间复杂度内查找指定键的元素。
由于键可以重复因此无法使用operator[]函数来直接访问元素因为这样会产生歧义。 operator[]函数通常用于访问和修改容器中的元素。对于map容器来说它的每个键只能对应一个值因此可以使用operator[]通过键直接访问和修改对应的值。但是对于multimap容器一个键可以对应多个值如果使用operator[]来访问某个键那么返回的应该是一个值的集合而不是单个的值。这就会导致使用operator[]函数的结果不明确。 为了解决这个问题multimap提供了equal_range函数来查找某个键对应的所有值的范围然后可以通过迭代器遍历该范围内的所有值。
int main()
{// 创建一个multimap对象multimapint, std::string scores;// 插入元素scores.insert(std::make_pair(85, Alice));scores.insert(std::make_pair(92, Bob));scores.insert(std::make_pair(77, Alice));scores.insert(std::make_pair(92, Charlie));scores.insert(std::make_pair(80, Alice));// 遍历输出元素cout Multimap Elements: endl;for (const auto score : scores) {cout Score: score.first , Student: score.second endl;}// 查找并输出分数为92的学生auto range scores.equal_range(92);if (range.first ! scores.end()) {cout Students with score 92: endl;for (auto it range.first; it ! range.second; it) {cout Student: it-second endl;}}return 0;
}
