1

Q#1）下面的结构不想被复制并给出编译错误 - 为什么以及如何处理它？

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct person
{
    person(string n)
        :name(n)
    {}

    string name;
};

int main()
{
    map<string, person> my_map;

    my_map["one"] = person("Tom");

    return 0;
}

Q#2）我们可以通过省略结构构造函数“person（const string& n）”并一一分配结构值来避免上述问题： 

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct person
{
    string name;
};

int main()
{
    map<string, person> my_map;

    person p;
    p.name = "Tom";
    my_map["one"] = p;

    return 0;
}

所以，假设我这样做，并且在地图中存储了很多人之后，我想检查地图中是否存在特定的人。据我所知，正确的做法是：

if(my_map.find("one") == my_map.end()) { //it doesn't exist in my_map }  
else {//it exists}

但据我了解，这将一一遍历整个地图，不是吗？如果是，那么可以这样做：

using namespace std;

struct person
{
    string name;
    string identifier; // <--
};

int main()
{
    map<string, person> my_map;

    person p;
    p.name = "Tom";
    p.identifier = "something"; // <--
    my_map["one"] = p;

    if(my_map["unknown"].identifier == "something") // <--
        cout << "Found" << endl;
    else 
        cout << "Not found" << endl;

    return 0;
}

通过这样做，我们避免了迭代，并且内存中的垃圾与我们的标识符匹配的可能性是......我猜很小，特别是如果我们使用一些哈希。那么这样做可以（安全）吗？

4

2 回答 2

8

1）由于以下表达式，您的第一个示例中的代码无法编译：

my_map["one"]

my_map["one"]构造一个std::stringfrom "one"，并将其传递给std::map::operator[]。map::operator[]确保将值映射到提供的键（如果键尚未与值关联，则通过将键与默认构造的值相关联）并返回对该值的引用。

这不会编译，因为person没有默认构造函数（“默认构造函数”是不带参数的构造函数）。

有几种方法可以解决此问题。

一种方法是您采用的方式 - 删除构造函数。它之所以有效，是因为如果您不提供任何构造函数，则会隐式定义默认构造函数。

另一种方法是显式定义默认构造函数person：

struct person
{
    person():name(){} //or person()=default; if your compiler supports this
    person(string n)
        :name(n)
    {}
    string name;
};

另一种方法是根本不使用operator[]，而是使用map::insert，如下所示：

auto pair(my_map.insert(std::make_pair(std::string("one"),person("Tom"))));
if (!pair.second) {
    *pair.first = person("Tom");
}

2）在地图中查找元素的正确方法是（如您所说）使用：

if(my_map.find("one") == my_map.end()) {/*it doesn't exist in my_map*/}
else {/*it exists*/}

这不会检查地图中的每个元素 - 实际上它可能只检查O(log(map.size()))元素。

你的担心是完全没有根据的，这是在地图中找到元素的正确方法，但是你继续的方式表明对做什么有严重的误解operator[]。

您问“如果地图中不存在，my_map["unknown"].identifier == "something"返回 true的概率是多少？”。"unknown"

对此的答案是，无论如何都没有机会返回 true，因为如果std::string("unknown")映射中不存在带有键的值，那么operator[]将std::string("unknown")与默认构造关联person，因此identifier将是一个空字符串。

于 2012-04-25T06:23:09.387 回答
2

首先，既然你有一个构造函数，你需要提供一个默认的构造函数。这是因为 C++ 标准库容器使用值语义。所以地图需要能够复制值、分配它们并默认构造它们。由于您提供了构造函数，因此编译器不会合成默认构造函数。这是一个什么都不做的默认构造函数：

person() {} // default constructs string, so no special aciton required.

特别是在 的情况下，当映射中不存在具有键的元素时std::map，返回对默认构造值的引用：operator[]

my_map["one"] = p; // creates *default* person, then *assigns* it the value of p.

其次，关于您关于搜索地图的问题std::map，搜索具有对数复杂性，通常实现为自平衡二叉树。因此，当您搜索时，您不会遍历整个地图。并且由于operator[]在搜索键不存在时通过访问引入了新元素，因此使用表单find()是执行此操作的规范方式。

既然您提到了散列，C++11 提供了std::unordered_map,tr1和. 这些使用散列函数执行搜索是常数时间。是否值得使用取决于地图大小等因素。常数时间可能大于搜索小地图所用的对数时间。boosthash_map

注意：如果你想使用你的结构作为键，或者想把它插入到标准库之一sets，你有进一步的要求：

maps：您需要通过类的小于运算符或自定义比较器函子为键提供严格的弱排序。如果要person用作密钥，则需要类似以下内容：

bool operator<(const person& rhs) const { return name < rhs.name; }

unordered_ 或哈希映射：您必须通过 an或 functor为键提供哈希函数和相等比较。operator==.

于 2012-04-25T05:29:46.623 回答