昆明高端网站设计,企业注册名字查询,西安电商网站,阳泉营销型网站建设pair键值对
std::pair在很多关联容器#xff08;如std::map、std::multimap、std::set、std#xff1a;multiset等#xff09;中被广泛应用。以std::map为例#xff0c;std::map是一个键值对的容器#xff0c;其中每个元素都是一个std::pair#xff0c;键用于唯一标识元…pair键值对
std::pair在很多关联容器如std::map、std::multimap、std::set、stdmultiset等中被广泛应用。以std::map为例std::map是一个键值对的容器其中每个元素都是一个std::pair键用于唯一标识元素值则是与键相关联的数据。
pair是类模板一般用于表示key/value数据其实现是结构体。
pair结构模板的定义如下
template class T1, class T2
struct pair
{ T1 first; // 第一个成员一般表示key。 T2 second; // 第二个成员一般表示value。 pair(); // 默认构造函数。 pair(const T1 val1,const T2 val2); // 有两个参数的构造函数。 pair(const pairT1,T2 p); // 拷贝构造函数。 void swap(pairT1,T2 p); // 交换两个pair。
};
make_pair函数模板的定义如下
template class T1, class T2
make_pair(const T1 first,const T2 second)
{ return pairT1,T2(first, second);
}
示例代码
#include iostream
#includeutilityusing namespace std;template class T1, class T2
struct Pair
{T1 first; // 第一个成员一般表示key。T2 second; // 第二个成员一般表示value。Pair() {cout 调用了有默认的构造函数。\n;}Pair(const T1 val1, const T2 val2) :first(val1), second(val2) {cout 调用了有两个参数的构造函数。\n;}Pair(const PairT1, T2 p) : first(p.first), second(p.second) {cout 调用了拷贝构造函数。\n;}
};template class T1, class T2
PairT1, T2 make_Pair(const T1 first, const T2 second)
{// PairT1, T2 p(first, second);// return p; // 返回局部对象。return PairT1, T2(first, second); // 返回临时对象。
}int main()
{pairint, string p0;cout p0 first p0.first ,second p0.second endl;pairint, string p1(1, 吴彦祖); // 两个参数的构造函数。cout p1 first p1.first ,second p1.second endl;pairint, string p2 p1; // 拷贝构造。cout p2 first p2.first ,second p2.second endl;p2.swap(p0);cout p0 first p0.first ,second p0.second endl;cout p2 first p2.first ,second p2.second endl;auto p3 make_pair(2, 陈冠希);cout 键 p3.first , 值 p3.second endl;
}
运行结果 map容器
map 容器封装了红黑树平衡二叉排序树用于查找。
包含头文件 #includemap
map容器的元素是pair键值对。
迭代器是双向迭代器。
map类模板的声明
template class K, class V, class P lessK, class _Alloc allocatorpairconst K, V
class map : public _Tree_Tmap_traits K, V, P, _Alloc, false
{ …
}
第一个模板参数Kkey的数据类型pair.first。
第二个模板参数Vvalue的数据类型pair.second。
第三个模板参数P排序方法缺省按key升序。
第四个模板参数_Alloc分配器缺省用new和delete。
map提供了双向迭代器。
二叉链表
struct BTNode
{ pairK,V p; // 键值对。 BTNode *parent; // 父节点。 BTNode *lchirld; // 左子树。 BTNode *rchild; // 右子树。
};
一、构造函数
1map(); // 创建一个空的map容器。
2map(initializer_listpairK,V il); // 使用统一初始化列表。
3map(const mapK,V m); // 拷贝构造函数。
4map(Iterator first, Iterator last); // 用迭代器创建map容器。
5map(mapK,V m); // 移动构造函数C11标准。
二、特性操作
size_t size() const; // 返回容器的实际大小已使用的空间。
bool empty() const; // 判断容器是否为空。
void clear(); // 清空容器。
三、元素操作
V operator[](K key); // 用给定的key访问元素。
const V operator[](K key) const; // 用给定的key访问元素只读。
V at(K key); // 用给定的key访问元素。
const V at(K key) const; // 用给定的key访问元素只读。
注意
1[ ]运算符如果指定键不存在会向容器中添加新的键值对如果指定键不存在则读取或修改容器中指定键的值。
2at()成员函数如果指定键不存在不会向容器中添加新的键值对而是直接抛出out_of_range 异常。
示例代码
#include iostream
#include map
using namespace std;int main()
{mapstring, string m({ { 08,冠希 }, { 03,于晏 }, { 01,彦祖 }, { 07,德华 }, { 05,学友 } });cout m[08] m[08] endl; // 显示key为08的元素的value。cout m[09] m[09] endl; // 显示key为09的元素的value。key为09的元素不存在将添加新的键值对。cout m.at(03) m.at(03) endl;//m.at(099);错误m[07] 黎明; // 把key为07的元素的value修改为黎明。m[12] 富城; // 将添加新的键值对。for (auto val : m)cout val.first , val.second ;cout endl;
}运行结果 四、赋值操作
给已存在的容器赋值将覆盖容器中原有的内容。
1mapK,V operator(const mapK,V m); // 把容器m赋值给当前容器。
2mapK,V operator(initializer_listpairK,V il); // 用统一初始化列表给当前容器赋值。
五、交换操作
void swap(mapK,V m); // 把当前容器与m交换。
交换的是树的根结点。
六、比较操作
bool operator (const mapK,V m) const;
bool operator ! (const mapK,V m) const;
七、查找操作
1查找键值为key的键值对
在map容器中查找键值为key的键值对如果成功找到则返回指向该键值对的迭代器失败返回end()。
iterator find(const K key);
const_iterator find(const K key) const; // 只读。
2查找键值key的键值对
在map容器中查找第一个键值key的键值对成功返回迭代器失败返回end()。
iterator lower_bound(const K key);
const_iterator lower_bound(const K key) const; // 只读。
3查找键key的键值对
在map容器中查找第一个键值key的键值对成功返回迭代器失败返回end()。
iterator upper_bound(const K key);
const_iterator upper_bound(const K key) const; // 只读。
4统计键值对的个数
统计map容器中键值为key的键值对的个数。
size_t count(const K key) const;
八、插入和删除
1void insert(initializer_listpairK,V il); // 用统一初始化列表在容器中插入多个元素。
2pairiterator,bool insert(const pairK,V value); // 在容器中插入一个元素返回值pairfirst是已插入元素的迭代器second是插入结果。
3void insert(iterator first,iterator last); // 用迭代器插入一个区间的元素。
4pairiterator,bool emplace (...); // 将创建新键值对所需的数据作为参数直接传入map容器将直接构造元素。返回值pairfirst是已插入元素的迭代器second是插入结果。
例mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple(冰冰, 18));
5iterator emplace_hint (const_iterator pos,...); // 功能与第4个函数相同第一个参数提示插入位置该参数只有参考意义如果提示的位置是正确的对性能有提升如果提示的位置不正确性能反而略有下降但是插入是否成功与该参数元关。该参数常用end()和begin()。成功返回新插入元素的迭代器如果元素已经存在则插入失败返回现有元素的迭代器。
6size_t erase(const K key); // 从容器中删除指定key的元素返回已删除元素的个数。
7iterator erase(iterator pos); // 用迭代器删除元素返回下一个有效的迭代器。
8iterator erase(iterator first,iterator last); // 用迭代器删除一个区间的元素返回下一个有效的迭代器。
示例代码
#include iostream
#include map
using namespace std;int main()
{mapstring, string m({ { 08,冠希 }, { 03,于晏 }, { 01,彦祖 }, { 07,德华 }, { 05,学友 } });// 执行插入操作并检查返回值auto result m.insert(make_pair(08, 富城));// result的类型是std::pairstd::mapstd::string, std::string::iterator, bool// result.first是指向插入位置的迭代器如果插入成功或已存在相同键的迭代器如果插入失败// result.second是一个布尔值表示插入是否成功if (result.second) {std::cout 插入成功 std::endl;}else {std::cout 插入失败键已存在 std::endl;}for (auto val : m)cout val.first , val.second ;cout endl;// 在map容器中查找键值为key的键值对如果成功找到则返回指向该键值对的迭代器失败返回end()。auto it1 m.find(05);if (it1 ! m.end())cout 查找成功 it1-first , it1-second endl;elsecout 查找失败。\n;// 在map容器中查找第一个键值 key的键值对成功返回迭代器失败返回end()。auto it2 m.lower_bound(05);if (it2 ! m.end())cout 查找成功 it2-first , it2-second endl;elsecout 查找失败。\n;// 在map容器中查找第一个键值 key的键值对成功返回迭代器失败返回end()。auto it3 m.upper_bound(05);if (it3 ! m.end())cout 查找成功 it3-first , it3-second endl;elsecout 查找失败。\n;// 统计map容器中键值为key的键值对的个数。cout count(05) m.count(05) endl; // 返回1。cout count(06) m.count(06) endl; // 返回0。
}运行结果 std::map 的 insert 函数在遇到重复键的情况时会根据其内部实现做出相应处理。通常情况下它不会覆盖已有的键值对与 std::unordered_map 不同std::unordered_map 若插入重复键会覆盖原来的值而是会返回一个表示插入结果的对象这个对象包含了一些信息来表明插入操作是否真正成功插入了新元素。 我们可以接受返回值来确认是否插入成功。
在容器中插入一个元素返回值pairfirst是已插入元素的迭代器second是插入结果。
按照字符串的字典序比较规则这也是 std::map 默认用于比较键的规则因为键是 std::string 类型
01 03 05 07 08
所以查找lower和upper时候会找到学友和德华
unordered_map容器
unordered无序
unordered_map容器封装了哈希表查找、插入和删除元素时只需要比较几次key的值。
包含头文件 #includeunordered_map
unordered_map容器的元素是pair键值对。
unordered_map类模板的声明
template class K, class V, class _Hasher hashK, class _Keyeq equal_toK, class _Alloc allocatorpairconst K, V
class unordered_map : public _Hash_Umap_traitsK, V, _Uhash_compareK, _Hasher, _Keyeq, _Alloc, false
{ …
}
第一个模板参数Kkey的数据类型pair.first。
第二个模板参数Vvalue的数据类型pair.second。
第三个模板参数_Hasher哈希函数默认值为std::hashK
第四个模板参数_Keyeq比较函数用于判断两个key是否相等默认值是std::equal_toK。
第五个模板参数_Alloc分配器缺省用new和delete。
创建std::unordered_map类模板的别名
templateclass K,class V
using umap std::unordered_mapK, V;
std::map 和 std::unordered_map 区别
1. 底层数据结构 std::map std::map 的底层数据结构是基于红黑树Red-Black Tree实现的。红黑树是一种自平衡二叉搜索树它在插入和删除节点时会通过一系列的旋转和颜色调整操作来保持树的平衡使得树的高度始终保持在一个相对较低的水平最坏情况下为 O(logn)其中n 是树中节点的数量。这种数据结构的优点是能够保证元素按照键的大小顺序进行有序存储并且在查找、插入和删除操作时平均时间复杂度都为O(logn) 。例如当你插入一个新的键值对到 std::map 中时它会根据键的大小在红黑树中找到合适的位置进行插入并自动调整树的结构以保持平衡和有序。 std::unordered_map std::unordered_map 的底层数据结构是基于哈希表Hash Table实现的。哈希表通过一个哈希函数将键映射到一个特定的桶Bucket中每个桶可以存储一个或多个键值对。理想情况下当哈希函数设计得比较好时查找操作可以在常数时间O(1) 内完成因为可以通过计算键的哈希值直接定位到对应的桶然后在桶内进行查找。然而哈希表存在哈希冲突Hash Collision的问题即不同的键可能通过哈希函数计算得到相同的哈希值从而被映射到同一个桶中。为了解决哈希冲突通常会采用一些冲突解决策略如链地址法将冲突的键值对链接成一个链表存放在同一个桶中或开放地址法通过一定的规则在哈希表中重新寻找空闲的位置来存放冲突的键值对。
2、元素顺序
由于其基于红黑树的实现std::map 中的元素会按照键的大小顺序自动进行排序。unordered_map 中的元素是无序的因为哈希表本身并不保证元素的顺序。键值对在哈希表中的存储位置主要取决于键的哈希值以及冲突解决策略。所以当你遍历 unordered_map 时元素的出现顺序是不确定的可能与插入顺序不同也不一定按照键的任何特定顺序排列。
例如
#include iostream
#include unordered_mapint main() {std::unordered_mapint, std::string myUnorderedMap;myUnorderedMap.insert({ 1, one });myUnorderedMap.insert({ 3, three });myUnorderedMap.insert({ 2, two });// 遍历unordered_map输出所有键值对顺序不确定for (auto it myUnorderedMap.begin(); it ! myUnorderedMap.end(); it) {std::cout 键 it-first , 值 it-second std::endl;}return 0;
} 这个结果每次输出结果都一样这其实是有一定概率会出现的情况。虽然理论上 std::unordered_map 的遍历顺序是不确定的因为它是基于哈希表实现的元素存储位置取决于键的哈希值以及哈希冲突解决策略等因素。但在实际情况中如果数据量比较小而且哈希函数std::unordered_map 默认的哈希函数或者你自定义的哈希函数如果有的话对于你所插入的这些键计算出来的哈希值分布相对比较均匀没有产生过多的哈希冲突那么就有可能每次遍历输出的顺序看起来是一样的。
不过当你插入的数据量逐渐增大或者插入一些特殊的键值使得哈希冲突情况发生变化时就很可能会出现不同的遍历顺序了。
例如
#include iostream
#include unordered_map
#includerandom
#includeutility
int main() {std::unordered_mapint, int myUnorderedMap;for (int i 1; i 1000000; i){std::random_device rd;std::mt19937 gen(rd());// 定义分布范围为1到1000000std::uniform_int_distribution dis(1, 1000000);// 生成随机数int randomNumber dis(gen);myUnorderedMap.insert(std::make_pair(i, randomNumber));}// 遍历unordered_map输出所有键值对顺序不确定for (auto it myUnorderedMap.begin(); it ! myUnorderedMap.end(); it) {std::cout 键 it-first , 值 it-second std::endl;}return 0;
}
如果生成的数足够多顺序是不确定的。
3、查找、插入和删除操作的性能特点 std::map 查找、插入和删除操作的平均时间复杂度都是 O(logn)。这意味着在数据量较大时这些操作的执行时间会随着数据量的增加而以对数级别的速度增长。虽然这种增长速度相对较慢但相比一些常数时间复杂度的操作如理想情况下的哈希表查找还是要慢一些。不过由于 std::map 能够保持元素的有序性在一些需要基于顺序进行查找如查找某个键值对之后的所有键值对或者进行范围查找如查找键在某个区间内的所有键值对的场景下它具有独特的优势。 std::unordered_map 在理想情况下查找操作的时间复杂度可以达到 O(1)即可以在常数时间内完成查找。这是因为通过哈希函数可以直接定位到键值对可能所在的桶然后在桶内进行查找。然而实际情况中由于哈希冲突的存在当哈希冲突比较严重时查找操作可能会退化为链表查找如果采用链地址法解决冲突此时查找时间复杂度可能会变为O(n) 其中 是桶内键值对的数量。插入和删除操作的时间复杂度也类似在理想情况下为 O(1)但在哈希冲突严重时可能会变差。总体来说当哈希函数设计得比较好并且哈希冲突不太严重时std::unordered_map 在查找、插入和删除操作上的性能要优于 std::map。
4. 内存占用 std::map 由于红黑树需要存储节点之间的指针以及用于保持树平衡的额外信息如节点的颜色等相对来说内存占用可能会比 std::unordered_map 要多一些。具体的内存占用情况还会受到键值对类型、树的大小等因素的影响。 std::unordered_map std::unordered_map 的内存占用主要取决于哈希表的大小即桶的数量以及键值对的数量。一般来说为了减少哈希冲突哈希表可能需要设置较大的桶数这可能会导致一定的内存浪费。但总体而言在数据量较大且哈希冲突不严重的情况下std::unordered_map 的内存占用可能相对 std::map 会有一定的优势。
5、总结
std::map 和 std::unordered_map 各有优缺点在实际应用中需要根据具体的应用场景和需求来选择合适的容器。如果需要元素按照键的顺序存储并且对查找、插入和删除操作的平均性能要求不是特别高能够接受O(logn) 的时间复杂度那么 std::map 是一个不错的选择如果更看重查找、插入和删除操作的快速执行希望在理想情况下达到 O(1) 的时间复杂度并且不需要元素按照特定顺序排列那么 std::unordered_map 则更为合适。
