51

std::list<std::pair>和 和有什么不一样std::map？列表也有find方法吗？

4

7 回答 7

127

std::map<X, Y>：

  • 是关于键的有序结构（也就是说，当您迭代它时，键将始终增加）。
  • 仅支持唯一键 ( Xs)
  • 提供快速find()方法 ( O(log n))，通过 Key 找到 Key-Value 对
  • 提供一个索引操作符map[key]，它也很快

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

  • 是配对Xs 和Ys 的简单序列。它们按照您放入的顺序保持不变。
  • 可以容纳任意数量的副本
  • list在 a中找到一个特定的键O(N)（没有特殊方法）
  • 提供splice方法。
于 2010-08-02T16:38:58.760 回答
23

std::pair

std::pair是一个模板化的元组结构，限制为 2 个项目，称为 first 和 second：

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

std::pair被 STL（和其他代码）用作“通用容器”来同时聚合两个值，而无需重新定义另一个struct.

std::map

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::pair和std::map

注意：这是对原始未经编辑的问题的答案。

函数需要同时将std::map迭代器返回到键和值以保持效率......所以显而易见的解决方案是将迭代器返回到对：

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>

注意：在问题编辑后编辑。

因此，乍一看，配对地图和配对列表看起来是一样的。但这种情况并非如此：

映射本质上是由提供的函子排序的，而列表将 [A,B] 对保留在您放置它们的位置。这使得映射的插入 O(log n)，而列表内的原始插入是一个恒定的复杂性（搜索插入它的位置是另一个问题）。

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

因此，在地图中找到一个项目是 O(log n)，而在无序列表中是 O(n)。如果列表是有序的，并且您想使用二分法，您将不会获得预期的性能提升，因为遍历项目列表无论如何都是逐项完成的。

（在我一年前工作的一个项目中，我们用一组相同的有序项目替换了一个有序项目列表，它提高了性能。该集合具有与地图相同的内部树结构，我猜同样的提升将适用于这里）

于 2010-08-02T16:33:29.783 回答
3

（澄清后编辑）

std::map针对快速搜索进行了优化。它有自己的find方法，利用其内部结构提供良好的性能。通常，它只会检查log(N)键，其中 N 是映射中的项目数。

std::list<std::pair>是一个简单的链表，因此只支持逐个元素的遍历。您可以使用单独的std::find算法，或者std::find_if使用仅检查first成员以更好地匹配 语义的自定义谓词std::map::find，但这会非常慢。事实上，它必须查看列表中的每一对以查找任何失败的搜索，并且对于任何成功的搜索，平均会查看一半。

于 2010-08-02T16:23:30.430 回答
3

std:pair恰好持有两个对象。 std:map保存成对对象的集合。

您不能在 pair 上使用 find()，因为没有什么可找到的。你想要的对象是pair.First或者pair.Second

map<>更新：假设您的意思是和之间的区别list<pair<> >：应该实现映射以快速查找key成员。 list只有一个简单的线性列表。在列表中查找一个项目需要遍历整个列表。但是， std::find() 将同时适用于两者。

于 2010-08-02T16:23:39.537 回答
1

STL 映射是关联数组，通常在内部实​​现为哈希映射。如果你想迭代一个 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;
}

我建议使用谷歌搜索并阅读完整的 STL API 参考，因为 STL（除了将布尔值存储在向量中和其他类似的东西中）实现了许多您希望在任何程序中使用的数据结构功能，而无需重新发明轮子。

于 2010-08-02T16:38:26.943 回答
1

map 可以在 O(log n) 的范围内提供更好的搜索时间，而 list 可以有 O(n) 的搜索时间。

于 2014-03-25T05:36:38.327 回答
0

std::pair 仅用于将 2 个对象组合在一起（例如，“页面上的坐标”由 X 和 Y 组成）。

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

尝试在一对上使用 find 方法是没有意义的，因为在您知道顺序的两个事物的列表中查找某些东西有什么意义，即使该 find 方法存在于它不存在的对类中。

但是，如果这是您想要的，您可以使用 std::pair 作为映射值。

于 2010-08-02T16:24:36.807 回答