C++ stl 中 std::list<std::pair> 和 std::map 的区别

Difference between std::list<std::pair> and std::map in C++ stl

提问by Boolean

Can you please tell me the difference between std::list<std::pair> and std::map. Can I used find method on list too?

你能告诉我 std::list<std::pair> 和 std::map 之间的区别吗？我也可以在列表中使用 find 方法吗？

Thank you.

谢谢你。

-- Clarification

-- 澄清

Question edited to be more clear.

问题编辑得更清楚。

回答by jpalecek

std::map<X, Y>:

std::map<X, Y>：

• is an ordered structure with respect to keys (that is, when you iterate over it, keys will be always increasing).
• supports unique keys (Xs) only
• offers fast find()method (O(log n)) which finds the Key-Value pair by Key
• offers an indexing operator map[key], which is also fast

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

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

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

• is a simple sequence of paired Xs and Ys. They remain in the order you put it in.
• can hold any number of duplicates
• finding a particular key in a listis O(N)(no special method)
• offers the splicemethod.

• 是一对Xs 和Ys的简单序列。它们保留在您放入的顺序中。
• 可以容纳任意数量的重复项
• 发现在一个特定的键list被O(N)（无特殊方法）
• 提供splice方法。

回答by paercebal

std::pair

std::pair

std::pairis a templated tuple-structure limited to 2 items, called first and second:

std::pair是一个模板化的元组结构，仅限于 2 个项目，称为第一和第二：

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

std::pairis used as a "generic container" by the STL (and other code) to aggregate two values at the same time without having to redefine yet another struct.

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

std::map

std::map

std::mapis an templated associative container, associating keys and values together. The easiest (but not more efficient) example is :

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::pairand std::map

std::pair和 std::map

Note: This was the answer to the original, unedited question.

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

The std::mapfunctions needs to return iterators to the keys and values at the same time to remain efficient... So the obvious solution is to return iterators to pairs:

该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> >and std::map<A,B>

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

Note: Edited after edition of the question.

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

Thus, at first glance, a map of pairs and a list of pairs would seem the same. But this is not the case:

因此，乍一看，对的映射和对的列表似乎相同。但这种情况并非如此：

The map is inherently ordered by the functor provided, whereas the list will keep the pairs of [A,B] right where you put them. This makes insertion O(log n) for the map, whereas raw insertion inside a list is a constant complexity (searching where to insert it is another problem).

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

You can simulate somewhat the behavior of a map using a list of pairs, but note that the map is usually implemented as a tree of items, whereas the list is a chained list of items. Thus, algorithm like dichotomy will work a lot faster in a map than in a list.

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

Thus, finding an item in a map is O(log n), whereas in an unordered list, it is O(n). And if the list is ordered, and you want to use dichotomy, you won't get the expected performance boost, as the traversal the list of items is done item by item anyway.

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

(In a project I worked on one year ago, we replaced a list of ordered items by a set of the same ordered items, and it boosted the performance. The set having the same internal tree structure as the map, I guess the same boost would apply here)

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

回答by Walter Mundt

(Edited after clarification)

（澄清后编辑）

std::mapis optimized for fast searching. It has its own findmethod that uses its internal structure to provide good performance. In general, it will only inspect log(N)keys, where N is the number of items in the map.

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

std::list<std::pair>is a simple linked list, and so only supports element-by-element traversal. You coulduse the separate std::findalgorithm, or std::find_ifwith a custom predicate that only examines the firstmember to better match the semantics of std::map::find, but that would be very slow. In fact, it will have to look at everypair in the list for any failed search, and will look at half on average for any successful one.

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

回答by James Curran

std:pairholds exactly two objects. std:maphold a collection of paired objects.

std:pair正好容纳两个对象。 std:map持有配对对象的集合。

You cannot use find() on pair, because there is nothing to find. The object you want is either pair.Firstor pair.Second

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

UPDATE: Assuming you meant the difference between map<>and list<pair<> >: Map should be implemented for fast lookup on the keymember. listhas just a simple linear list. Looking up an item in a list requires running through the whole list. However, std::find() will work on both.

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

回答by Novikov

STL maps are associative arrays, usually implemented as hashmaps inside. If you want to get iterate over an STL map it'll return an STL pair.

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;
}

I'd suggest googling and reading the complete STL API reference since STL (with the exception of storing booleans in vectors and other oddities like that) implements a lot of data structure functionality you'd want to use in any program without reinventing the wheel.

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

回答by Udhay

Map can provide the better searching time in the range of O(log n), whilw list can have the searching time of O(n).

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

回答by DVK

std::pair is just for grouping together exactly 2 objects (say, "coordinates on a page" is comprized of X and Y).

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

std::map is a mapping from one set of objects to another.

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

There's no point of trying to use a find method on a pair, as what's the point of finding something in a list of two things of which you know the order to, even if that find method existed in a pair class which it does not.

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

However, you CAN use std::pair as a map value if that's what you want.

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