C++ STL中std::list<std::pair>和std::map有什么区别？

Question

std::list<std::pair>和std::map有什么区别？列表中也有find方法吗？

- Boolean

Answer 1

std::map<X, Y>:

• 有序结构，按照键（即在迭代时，键会逐渐增加）排序。
• 仅支持唯一键(X)
• 提供快速的find()方法 (O(log n))，它可以通过键找到Key-Value对
• 提供索引运算符map[key]，同样是快速的

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

• 是一系列成对的简单序列X和Y。它们保留您放置它们的顺序。
• 可以持有任意数量的重复项
• 查找list中特定键的时间复杂度为O(N)(没有特殊方法)
• 提供了splice方法

- jpalecek

---

为了完整性：std::vector<std::pair<X, Y>>提供O(log n)的查找，对于不可变数据而言，它比map更小（并且应该更快）。例如，对于静态、频繁使用的查找非常有用。但在证明优化会带来实际好处之前，请使用map。 - Alice Purcell

@chrispy：当std::vector<std::pair<X, Y>>被排序时，它仅提供O(log n)的查找。 - jpalecek

是的，因此在排序后插入一次的时间复杂度为O(n)，因此最适合静态数据。 - Alice Purcell

Answer 2

std::pair

std::pair 是一个模板化的二元组结构，仅限于包含两个项目，分别称为 "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）。如果列表有序，并且您想使用二分法，则不会获得预期的性能提升，因为遍历项目列表仍然是逐个项目完成的。

（在我一年前工作的项目中，我们用同样有序的项集替换了有序项的列表，并提高了性能。由于集合具有与映射相同的内部树结构，我想在这里也会出现同样的提升）

- paercebal

Answer 3

(澄清后编辑)

std::map被优化用于快速查找。它有自己的find方法，利用其内部结构提供良好的性能。通常情况下，它只会检查log(N)个键，其中N是映射中的项数。

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

- Walter Mundt

Answer 4

std:pair包含两个对象. std:map存储一组成对的对象。

你无法在pair上使用find()，因为没有需要查找的内容。你所需的对象要么是pair.First，要么是pair.Second。

更新： 假设您想了解map<>和list<pair<> >之间的区别：Map应该实现快速查找key成员。而list只有一个简单的线性列表。在列表中查找项需要运行整个列表。然而，std::find()在两者上都适用。

- James Curran

Answer 5

STL maps是关联数组，通常在内部实现为哈希映射。如果您想迭代STL map，则会返回一个STL pair。

#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（除了将布尔值存储在向量中等奇怪的情况）实现了许多数据结构功能，这些功能在任何程序中都可以使用，而不必重新发明轮子。

- Novikov

---

STL中的map并不是通过哈希表实现的，而是通过红黑树（或类似结构）实现的。 - jpalecek

有一些地方STL文档没有符合C++标准设置的要求，因此阅读STL API可能并不是你实际使用它的情况。 - Dennis Zickefoose

Answer 6

Map可以在O(log n)的范围内提供更好的搜索时间，而列表的搜索时间为O(n)。

- Udhay

Answer 7

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

std::map 是从一个对象集合到另一个对象集合的映射。

试图在 pair 上使用查找方法是没有意义的，因为即使在 pair 类中存在该查找方法，你也知道这两个东西的顺序，所以在两个东西的列表中查找某些东西有什么意义呢？

但是，如果需要，您可以将 std::pair 用作映射值。

- DVK