眼查看网站开发语言,做跨境网站,网站两侧固定广告代码,标题优化怎样选关键词文章目录 一、引言二、关联式容器的中的 paira.pair 的创建及使用b.pair 间的比较 三、 map 与 set 详解1. map 的基本操作2. set 的基本操作3.关联式容器的迭代器 四、 multimap 与 multiset 的特性五、关联式容器的使用技巧与注意事项1. 键值类型的选择与设计2. 自定义比较函… 文章目录 一、引言二、关联式容器的中的 paira.pair 的创建及使用b.pair 间的比较 三、 map 与 set 详解1. map 的基本操作2. set 的基本操作3.关联式容器的迭代器 四、 multimap 与 multiset 的特性五、关联式容器的使用技巧与注意事项1. 键值类型的选择与设计2. 自定义比较函数与排序规则3.其他注意事项 一、引言
1. 关联式容器的概念与重要性
关联式容器是C标准库中的一种重要数据结构它允许我们存储键值对key-value pair或单独的元素并基于键key来快速访问或检索对应的值value或元素。关联式容器在多种场景下发挥着至关重要的作用特别是在需要高效查找、插入和删除元素时。它们为程序员提供了便捷的工具可以简化复杂的操作并优化程序性能。
关联式容器通过内部的数据结构如红黑树来维护元素的顺序这使得它们能够在常数时间内完成元素的查找、插入和删除操作。与顺序容器如vector、list相比关联式容器在处理大量数据时具有更高的效率。
2. 关联式容器与序列式容器的区别
关联式容器与序列式容器的主要区别在于它们对元素的存储和访问方式的不同。序列式容器按照元素在容器中的位置来存储和访问元素而关联式容器则是根据元素的键来存储和访问元素。
序列式容器如vector、list、deque等其底层为线性序列的数据结构通过索引或迭代器来访问元素里面存储的是元素本身。它们提供了对元素的顺序访问。
关联式容器则通过使用平衡搜索树即红黑树作为其底层结果容器中的元素是一个有序的序列。因此使得元素的存储和访问更加灵活和高效。它们允许我们根据键来快速查找、插入和删除元素。 ⚠️关联容器不支持顺序容器的位置相关操作例如 push_back或 push_front。原因是关联容器中元素是根据关键字存储的这些操作对其没有意义。而且关联式容器也不支持构造函数或插入操作这些接收一个元素在和一个数量值的操作。 3. 常见的关联式容器概览
C标准库提供了多种关联式容器每种容器都有其特定的用途和特性。以下是一些常见的关联式容器及其简要描述
std::map存储键值对的关联容器键是唯一的元素按照键的值进行排序。std::set只存储键的关联容器键是唯一的元素按照键的值进行排序。std::multimap存储键值对的关联容器允许有多个具有相同键的元素。std::multiset只存储键的关联容器允许有多个相同的元素。
这些关联式容器提供了丰富的操作函数如插入、查找、删除和遍历等使得我们可以方便地使用它们来管理数据。通过选择适合的关联式容器我们可以优化程序的性能并简化代码的实现。
后续C11又提供了哈希结构的关联式容器我们将在之后的文章做讲解。 二、关联式容器的中的 pair
在介绍关联容器之前我们需要了解名为 pair的标准库类型它定义在头文件 utility 中。
a.pair 的创建及使用
一个pair保存两个数据成员。类似容器pair是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值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) {}
};一个pair对象包含两个数据成员first和second分别对应键和值。pair的模板参数指定了这两个成员的类型即我们必须提供两个类项名。⚠️两个类型不要求一致
例如你可以创建一个pairstring, int其中first是一个字符串类型的键而second是一个整数类型的值。
#include utility // for std::pair
int main() { std::pairstd::string, int myPair; myPair.first apple; myPair.second 10; // 也可以使用构造函数初始化 std::pairstd::string, int anotherPair(banana, 20); return 0;
}在关联容器中pair扮演着非常重要的角色。关联容器如smap、set、multimap和multiset的元素类型实际上就是pair。对于map和multimap每个元素都是一个pair其中first成员是键second成员是与该键关联的值。
初始化一个 pair 可以使用构造函数也可以使用 make_pair 构造一个 pair 对象其中第一个元素设置为 x第二个元素设置为 y。通过传递参数给 make_pair可以隐式推断模板类型无需显式指定。
当我们向map或multimap插入元素时我们实际上是在插入一个pair对象。同样地当我们从map或multimap中检索元素时我们得到的是一个指向pair的迭代器。
b.pair 间的比较
其中、、、 四个运算符会先比较两个 pair 中的第一个变量在第一个变量相等的情况下再比较第二个变量。 每个操作符重载都需要传入两个 std::pair 对象 lhs 和 rhs它们都具有相同的模板类型 T1, T2。这些操作符重载的返回值都是 bool 类型。
operator判断两个 std::pair 对象是否相等。如果它们的第一个元素和第二个元素都相等则返回 true否则返回 false。operator!判断两个 std::pair 对象是否不相等。如果它们的第一个元素或第二个元素有一个不相等则返回 true否则返回 false。operator判断一个 std::pair 对象是否小于另一个 std::pair 对象。首先比较它们的第一个元素如果第一个元素小于另一个对象的第一个元素则返回 true如果第一个元素相等再比较第二个元素如果第二个元素也小于另一个对象的第二个元素则返回 true否则返回 false。operator判断一个 std::pair 对象是否小于或等于另一个 std::pair 对象。如果一个对象小于另一个对象或两个对象相等则返回 true否则返回 false。operator判断一个 std::pair 对象是否大于另一个 std::pair 对象。如果一个对象不小于另一个对象且两个对象不相等则返回 true否则返回 false。operator判断一个 std::pair 对象是否大于或等于另一个 std::pair 对象。如果一个对象大于另一个对象或两个对象相等则返回 true否则返回 false。
这些操作符的重载使得可以方便地比较 std::pair 对象的成员例如在使用容器时进行查找、排序等操作。 三、 map 与 set 详解
关联式容器定义类如下表示容器关键字和值的类型
类型别名解释key_type此容器类型的关键字类型mapped_type每个关键字关联的类型 仅适用于mapvalue_type对于set与key_type 相同对于map 为 pairconst key_type,mapped_type
对于set 类型key_type 和 value_type 是一样的set 中保存的值就是关键字。在一个map中元素是键值对。即每个元素是一个pair 对象包含一个关键之都一个关联的值。由于我们不能改变一个元素的关键字因此这些 pair 的关键字部分是const 的。
只有 map 家族的类型才有 mapped_type。
1. map 的基本操作
map是C标准库中的一个关联容器它存储的元素都是键值对并且根据键的值自动排序。下面我们将详细讨论std::map的基本操作包括插入与访问元素、查找元素、删除元素以及遍历元素。
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key,T // map::allocator_type class map;Key表示 map 中键的类型即 map::key_type。T表示 map 中值的类型即 map::mapped_type。 Compare用于定义键之间的比较方式默认是 std::lessKey即默认情况下按照键的升序进行排序。可以根据需要传入自定义的比较函数对象。 Alloc表示分配器类型用于管理内存分配。默认情况下使用 allocatorpairconst Key, T 作为默认的内存分配器。
插入元素
插入元素到std::map中通常使用insert成员函数。你可以通过make_pair函数或者初始化列表来创建键值对也可以添加一个元素的范围
#include iostream
#include map
#include string
using namespace std;
int main() {mapstring, int myMap;// 插入元素myMap.insert(make_pair(apple, 10));myMap.insert({pear,30});myMap.insert(pairstring, int(orange,40));myMap.insert(mapstring,int::value_type(cherry,50)); myMap[banana] 20; // 使用下标操作符插入// 访问元素cout The value of apple is: myMap[apple] endl;cout The value of banana is: myMap.at(banana) endl;return 0;
}⚠️insert函数可以接收一对迭代器也可以接收一个初始化列表这两种行为类似的对应构造函数。对于一个给定的关键字只有第一个带此关键字的元素才被插入到容器中。
要注意insert函数的返回值c98 insert返回的值依赖于容器类型和参数
单个元素插入 这种形式会尝试将值为 val 的元素插入到容器中。如果插入成功即容器中原先没有与 val 相等的元素则返回一个指向新插入元素的迭代器和 true如果插入失败容器中已经有一个与 val 相等的元素则返回一个指向已存在元素的迭代器和 false。 带有提示位置的插入 这种形式会尝试将值为 val 的元素插入到 position 所指定的位置之前。如果插入成功则返回指向新插入元素的迭代器如果插入失败则返回一个指向已存在元素的迭代器** 范围插入 这种形式用于一次性插入范围 [first, last) 中的元素。该方法接受两个迭代器参数分别指向要插入元素范围的起始和结束位置。
访问元素
访问元素则可以通过下标操作符[]或者at成员函数如果键不存在下标操作符会创建一个新元素而at则会抛出一个异常。都是通过键找到与键对应的值然后返回其引用
//map::at
mapped_type at (const key_type k);
const mapped_type at (const key_type k) const;//operator[]
mapped_type operator[] (const key_type k);
//使用 operator[] 函数的调用等效于以下操作
(*((this-insert(make_pair(k,mapped_type()))).first)).second;这个操作首先通过 make_pair(k, mapped_type()) 创建一个新的 key-value 对并将其插入到容器中。然后insert 方法返回一个指向新插入元素的迭代器通过解引用 (*...) 操作获取此元素并使用 .second 获取对应映射值的引用。 因此对于一个map使用下标操作其行为与数字和 vector上的下标操作不同。通过使用 operator[]可以轻松地访问和更新 map 容器中的元素如果元素不存在则可以在访问时插入新元素。 查找元素
对于不允许重复关键字的容器可能使用find还是count 没什么区别。但对于允许重复关键字的容器count还会做更多的工作。如果元素在容器中它还会统计有多少个元素有相同的关键字。如果不需要计数最好使用find。它返回一个迭代器指向找到的元素如果未找到元素则返回end()迭代器。此外count成员函数可以用来检查键是否存在于map中
#include iostream
#include map
#include string
using namespace std;
int main() {mapstring, int myMap;myMap[apple] 10;myMap[banana] 20;// 查找元素auto it myMap.find(apple);if (it ! myMap.end()) cout Found apple with value: it-second endl;else cout Apple not found. endl;// 检查键是否存在if (myMap.count(banana) 0) cout Banana exists in the map. endl;else cout Banana does not exist in the map. endl;return 0;
}删除元素
与顺序容器一样我们可以通过传递给erase传入一个常量迭代器或传入两个常量迭代器表示一个范围。这两个版本的 erase 与对应的顺序容器的操作非常相似指定的元素被删除函数返回 void。关联容器提供一个额外的erase操作它接受一个key_type 参数。此版本删除所有匹配给定关键字的元素(如果存在的话)返回实际删除的元素的数量。对于保存不重复关键字的容器erase的返回值总是0或1。若返回值为0则表明想要删除的元素并不在容器中。
#include iostream
#include map
#include string
using namespace std;
int main() {mapstd::string, int myMap;myMap[apple] 10;myMap[banana] 20;// 删除元素myMap.erase(apple); // 删除键为apple的元素// 使用迭代器删除元素auto it myMap.find(banana);if (it ! myMap.end()) {myMap.erase(it);}return 0;
}遍历元素
遍历std::map中的元素通常使用迭代器。由于map中的元素是排序的因此遍历将按照键的顺序进行。
示例代码
#include iostream
#include map
#include stringint main() {std::mapstd::string, int myMap;myMap[apple] 10;myMap[banana] 20;myMap[cherry] 30;// 遍历元素for (const auto kv : myMap) {std::cout kv.first : kv.second std::endl;}return 0;
}在上面的代码中我们使用了范围基于的for循环C11及以后版本来遍历map中的每个键值对。kv是一个常量引用它引用了map中的一个键值对。kv.first是键kv.second是值。 2. set 的基本操作
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type class set;T表示 set 中元素的类型即 set::key_type 和 set::value_type。 Compare用于定义元素之间的比较方式默认是 lessT即默认情况下按照元素的升序进行排序。可以根据需要传入自定义的比较函数对象。 Alloc表示分配器类型用于管理内存分配。默认情况下使用 allocatorT 作为默认的内存分配器。
set与map几近相同不再做赘述。
插入元素
与map相同都是使用insert进行插入。
setint s;
s.insert(1);
s.insert(2);
s.insert(3);
// 尝试插入已存在的元素不会有任何效果
s.insert(2); 查找元素
与map类似使用 find 成员函数来查找 set 中的元素。如果元素存在find 将返回一个指向该元素的迭代器如果元素不存在则返回 end() 迭代器。
setint s {1, 2, 3};
auto it s.find(2);
if (it ! s.end()) cout Element found: *it endl;
else cout Element not found endl; it s.find(4);
if (it s.end()) cout Element not found endl; 删除元素
与map类似使用 erase 成员函数来删除 set 中的元素。你可以通过值或迭代器来指定要删除的元素。set可以将序列中重复性的元素去除掉。因为set要保证其有序因此set中元素不能被直接修改若要修改可以先删除在插入。
setint s {1, 2, 3};
// 通过值删除元素
s.erase(2);
// 或者通过迭代器删除元素
auto it s.find(3);
if (it ! s.end()) { s.erase(it);
} 遍历元素
使用范围基于的 for循环或迭代器来遍历 set 中的元素。
#include iostream
#include set
using namespace std;
int main() { setint s {1, 2, 3}; //1、for (const auto elem : s) cout elem endl; //2、for (setint::iterator it s.begin(); it ! s.end(); it) { cout *it endl; } return 0;
}map中重载了[]运算符因为其需要通过key获取value而set中却没有。map中存储的是键值对set中只储存了key。因map和set的底层结构都是红黑树而红黑树是近似的平衡二叉搜索树故查询时间复杂度为O(log N) 。 3.关联式容器的迭代器
当解引用一个关联容器选代器时我们会得到一个类型为容器的 value_type 的的引用。
对map而言valve_type 是一个 pair 类型其 first 成员保存const的关键字second 成员保存值。此处假设我们有一个名为 words 的 map
mapstring, int words;
auto map_it words.begin(); // *map_it 是 pairconst string , int对象的引用
cout map_it-first map_it-second;
map_it-first another; //错误:关键字是const的不可改变
map_it-second; //正确:可以通过迭代器改变值一个map 的 value_type 是一个 pair我们可以改变 pair的值但不能改变关键字成员的值。 虽然 set 类型同时定义了iterator和const_iterator 类型但两种类型都只允许只读访问 set 中的元素。与不能改变一个 map 元素的关键字一样一个 set 中的关键字也是const的。可以用一个set迭代器来读取元素的值但不能修改
setint s { 0,1,2,3,4,5,6,8,9 };
setint::iterator set_it s.begin();
if (set_it ! s.end()) {*set_it 42; //错误:set中的关键字是只读的 cout *set_it endl; //正确:可以输出
}⚠️当我们使用一个迭代器遍历一个 map、multimap、set、multiset时迭代器按关键字升序遍历元素。 四、 multimap 与 multiset 的特性
multimap 和 multiset 是 C 标准模板库 (STL) 中的两种容器它们分别允许存储多个具有相同键的元素和多个重复的元素。这两种容器对于处理某些特定问题非常有用尤其是当您需要存储多个具有相同键的值或当您想要允许集合中的元素重复时。 multimap 特性 允许多值特性与 map 不同multimap 允许存储多个具有相同键的元素。 主要操作 插入多个相同键值的元素使用 insert 成员函数可以插入具有相同键的多个元素。查找与遍历多值元素可以使用 find 成员函数来查找具有特定键的第一个元素然后使用迭代器来遍历所有具有该键的元素。
⚠️multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。且multimap中没有重载operator[]操作。 multiset 特性 允许多重元素与 set 不同multiset 允许存储多个相同的元素。 主要操作 插入多个相同元素使用 insert 成员函数可以插入多个相同的元素。查找与遍历元素可以使用 find 成员函数来查找特定元素然后使用迭代器来遍历所有元素。 对允许重复关键字的容器使用 erase删除元素的数量可能大于1。 五、关联式容器的使用技巧与注意事项
关联式容器如 map、set、multimap、multiset 等在 C 标准库中提供了基于键值对存储元素的能力。在使用这些容器时有一些重要的技巧和注意事项需要了解。
1. 键值类型的选择与设计
唯一性确保键值是唯一的对于 map 和 set或者可以接受重复键值对于 multimap 和 multiset。可比较性键值类型必须支持比较操作通常是通过定义 运算符或者提供一个自定义的比较函数。内存和性能选择占用内存较小且比较操作效率高的类型作为键值类型。稳定性如果键值类型包含动态分配的内存或资源需要确保在键值比较和容器操作过程中这些资源的管理是安全的。
2. 自定义比较函数与排序规则
自定义比较函数当标准比较不满足需求时可以通过提供自定义的比较函数来定义键值对的排序规则。即使用仿函数。透明性自定义比较函数应该保持透明性即对于相等的键值比较结果应该一致。性能自定义比较函数的性能会影响容器的插入、查找和删除操作的效率。
3.其他注意事项
迭代器失效在修改关联式容器如插入或删除元素时指向容器中元素的迭代器可能会失效。需要小心处理这种情况避免使用失效的迭代器。范围查询关联式容器提供了基于键值的范围查询功能如 lower_bound() 和 upper_bound()。合理利用这些功能可以提高查询效率。
关联容器支持通过关键字高效查找和提取元素。对关键字的使用将关联容器和顺序容器区分开来顺序容器中是通过位置访问元素的。
