STD的区别:列表STD::配对和STD::C++中的映射

std::map<X, Y> :

• 是一个关于键的有序结构(也就是说,当您对其进行迭代时,键将始终递增)。
• 支持唯一键( X
• 提供快速 find() 方法( O(log n) )它按键查找键值对
• 提供索引运算符 map[key] ,速度也很快

std::list<std::pair<X, Y> > :

• 是一个简单的成对序列 十 Y s。它们按你的顺序排列。
• 在数据库中查找特定密钥 list O(N)
• 提供 splice 方法。

std::pair

是一个限制为2个项目的模板元组结构,称为第一个和第二个:

std::pair<int, std::string> myPair ;
myPair.first = 42 ;
myPair.second = "Hello World" ;

标准::对 被STL(和其他代码)用作“通用容器”来同时聚合两个值,而不必重新定义另一个值 struct

std::map

标准::地图 是一个模板化的关联容器,将键和值关联在一起。最简单(但不是更有效)的例子是:

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;
// ...
std::string strText ;  // strText is ""
strText = myMap[111] ; // strText is now "Hello World"
strText = myMap[42] ;  // strText is now "Fourty Two"
strText = myMap[23] ;  // strText is now "" (and myMap has
                       // a new value "" for key 23)

标准::对 标准::地图

注:这是对未经编辑的原始问题的回答。

这个

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;

myMap.insert(std::make_pair(23, "Bye")) ;

std::map<int, std::string>::iterator it = myMap.find(42) ;
std::pair<int, std::string> keyvalue = *it ;    // We assume 42 does
                                                // exist in the map
int key = keyvalue.first ;
int value = keyvalue.second ;

std::list<std::pair<A,B> > 和 std::map<A,B>

注:问题编辑后。

因此,乍一看,成对的地图和成对的列表看起来是一样的。但事实并非如此:

您可以使用成对的列表来模拟映射的行为,但是请注意,映射通常实现为项目树,而列表是链接的项目列表。因此,像二分法这样的算法在地图中的运行速度要比在列表中快得多。

(

std:pair 正好有两个物体。 std:map 保存成对对象的集合。

不能对pair使用find(),因为找不到任何内容。你想要的对象是 pair.First 或 pair.Second

更新: map<> 和 list<pair<> > :应实现映射以快速查找 key list 只有一个简单的线性列表。在列表中查找项目需要遍历整个列表。但是,std::find()可以同时处理这两种情况。

(澄清后编辑)

std::map 为快速搜索而优化。它有自己的 find 使用其内部结构提供良好性能的方法。一般来说,它只会检查 log(N)

std::list<std::pair> 是一个简单的链表,因此只支持逐元素遍历。你呢 使用单独的 std::find 算法,或 std::find_if 只检查 first 成员以更好地匹配 std::map::find 每一个 任何失败的搜索都要在列表中配对,任何成功的搜索都要平均看一半。

STL映射是关联数组,通常在内部实现为hashmaps。如果你想在一个STL映射上迭代,它会返回一个STL对。

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
        map<string, int> myMap;
        myMap["myKey"] = 1337;

        map<string, int>::iterator myIterator = myMap.begin();

        pair<string, int> myPair = *myIterator;

        cout<<"the key \""<<myPair.first<<"\" maps to the value of "<<myPair.second<<endl;
        cout<<"the key \"myKey"\" maps to the value of "<<myMap["myKey"]<<endl;
        return 0;
}

我建议用google搜索并阅读完整的stlapi参考资料,因为STL(除了在向量中存储布尔值和其他类似的奇怪之处)实现了许多数据结构功能,您可以在任何程序中使用这些功能,而无需重新设计轮子。

Map在O(logn)范围内提供了较好的搜索时间, whilw列表可以有O(n)的搜索时间。

std::pair只用于将正好2个对象组合在一起(例如,“页面上的坐标”由X和Y压缩)。

映射是从一组对象到另一组对象的映射。

但是,如果需要的话,可以使用std::pair作为映射值。