std::list 和有什么区别和 C++ 中的 std::map STL？

Question

std::list 和 std::map 之间有什么区别？列表也有 find 方法吗？

Answer 1

std::map：

• 是一个关于键的有序结构（也就是说，当你迭代它时，键将始终增加）。
• 支持唯一键 (Xs) 仅
• 提供快速 find() 方法 (O(log n))，该方法通过以下方式查找键值对Key
• 提供了一个索引运算符 map[key]，它的速度也很快

std::list >：

• 是成对的 X 和 Y 的简单序列。它们保持您放入的顺序。
• 可以保存任意数量的重复项
• ，在 list 中查找特定键是 O(N) （没有特殊方法）
• 提供 <代码>拼接方法。

Answer 2

std::pair

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

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

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

因此，乍一看，成对的映射和成对的列表看起来是一样的。但事实并非如此：

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

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

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

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

Answer 3

std:pair 恰好包含两个对象。 std:map 保存配对对象的集合。

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

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

Answer 4

（澄清后编辑）

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

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

Answer 5

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（除了在向量中存储布尔值和其他类似的奇怪之处）实现了许多您希望在任何程序中使用的数据结构功能，而无需重新发明轮子。

Answer 6

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

Answer 7

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

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

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

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