gpt4 book ai didi

c++ - std::map 超出需要的比较

转载 作者:行者123 更新时间:2023-11-28 07:43:26 25 4
gpt4 key购买 nike

我正在尝试 std::map(在 MinGW 和 MSVC2008 中),我使用了以下代码:

#include <map>
#include <string.h>
#include <iostream>
using namespace std;

class MapManager
{public:
void insert(char* n){
cout << "Inserting " << n << endl;
m_map[n] = 0;}
void get(char* n){
cout << "Finding (" << n << ")" << endl;
int x = m_map[n];}
struct cmp_str{
bool operator()(char const *a, char const *b){
cout << "operator(" << a << " " << b << ")\n";
return strcmp(a, b) < 0;}
};
std::map<char*,int,cmp_str> m_map;
};
int main(){
MapManager m;
m.insert("Abc"); m.insert("Xyz"); m.insert("123"); m.insert("987");
m.get("Abc"); m.get("Xyz");
}

结果如下:

Inserting Abc
Inserting Xyz
operator(Abc Xyz)
operator(Xyz Abc)
operator(Abc Xyz)
operator(Xyz Abc)
Inserting 123
operator(Abc 123)
operator(123 Abc)
operator(123 Abc)
operator(Abc 123)
Inserting 987
operator(Abc 987)
operator(123 987)
operator(987 123)
operator(987 Abc)
operator(987 Abc)
operator(Abc 987)
operator(123 987)
operator(987 123)
Finding (Abc)
operator(Abc Abc)
operator(123 Abc)
operator(Abc 123)
operator(987 Abc)
operator(Abc 987)
operator(Abc Abc)
Finding (Xyz)
operator(Abc Xyz)
operator(Xyz Abc)
operator(Xyz Xyz)
operator(Xyz Xyz)

Inserting Xyz 需要 4 次比较调用,这很奇怪!

operator(Abc Xyz)
operator(Xyz Abc)
operator(Abc Xyz)
operator(Xyz Abc)

map 用来插入/查找条目的算法是什么?

最佳答案

它依赖于实现,唯一的要求是 insertfind/[] 必须是 O(log n)。< sup>* 通常是在 red-black tree 上插入/搜索,这可能不是完全平衡的。

(请注意,由于 std::map 是一个模板,所有的实现细节都将在您可以细读的头文件中...)


* 对于这个用例,至少。

关于c++ - std::map 超出需要的比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15370132/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com