C++ 将结构存储在地图中；检查地图中是否存在结构

Store struct in a map; Checking if a struct exist inside a map

提问by Acute

Q#1) Struct below doesn't want to be copied and gives compilation errors - why and how to deal with it?

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) We can avoid the problem above by omitting the struct constructor "person(const string& n)" and assigning struct values one by one:

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

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

So, let's say I do it this way, and after storing many persons in the map I want to check if a particular person exists inside a map. As I know the correct way of doing it is:

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

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

But this as I understand will iterate through the whole map one by one, won't it? If yes, then is it okay to do it like:

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

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

By doing this we avoid iterating, and possibility that garbage in the memory will match our identifier is... small I guess, especially if we use some hash. So is it okay (secure) doing like that?

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

回答by Mankarse

1) The code in your first example fails to compile because of the following expression:

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

my_map["one"]

my_map["one"]constructs a std::stringfrom "one", and passes it to std::map::operator[]. map::operator[]ensures that a value is mapped to the supplied key (by associating the key with a default-constructed value if it is not already associated with a value) and returns a reference to that value.

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

This does not compile, because persondoes not have a default constructor (A "default constructor" is a constructor which takes no arguments).

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

There are several ways to fix this problem.

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

One way is the way that you took - removing the constructor. It works because if you do not supply any constructors, a default constructor will be implicitly defined.

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

Another way is to explicitly define a default constructor for person:

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

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

Another way is to not use operator[]at all, and to instead use map::insert, as follows:

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

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

---

---

2) The correct way to find an element in the map is (as you said) to use:

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

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

This does notinspect every element in the map - in fact it may only inspect O(log(map.size()))elements.

这并没有在地图上检查每一个元素-事实上，它可能只检查O(log(map.size()))元素。

Your fears are totally unfounded, this is thecorrect way to find an element in the map, however the way in which you continue suggests a severe misunderstanding about what operator[]does.

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

You ask "what is the probability that my_map["unknown"].identifier == "something"will return true if "unknown"does not exist in the map?".

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

The answer to this is that there is no chance whatsoever of this returning true, because if no value with the key std::string("unknown")exists in the map, then operator[]will associate std::string("unknown")with a default constructed person, and so identifierwill be an empty string.

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

回答by juanchopanza

First of all, since you have a constructor, you need to provide a default constructor. This is because C++ standard library containers use value semantics. So the map needs to be able to copy values, assign them, and default construct them. Since you provide a constructor, the compiler does not synthesize the default constructor. This is a default constructor that does nothing:

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

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

Particularly in the case of std::map, operator[]returns a reference to a default constructed value when an element with the key does not already exist in the map:

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

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

Second, concerning your question about searching the map, std::map, search has logarithmic complexity and is typically implemented as a self-balancing binary tree. So when you search you do not traverse the whole map. And since accessing via operator[]introduces new elements when the searched key doesn't exist, the form using find()is the canonical way to do it.

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

Since you mentioned hashing, C++11 provides std::unordered_map, and tr1and boosthave hash_map. These use hash functions perform the search is constant time. Whether it is worth using it or not depends on factors such as the size of your map. The constant time could be larger than the logarithmic time taken to search a small map.

既然你提到了散列，C++11 提供了std::unordered_map，tr1并且boost有hash_map。这些使用散列函数执行搜索是常数时间。是否值得使用它取决于诸如地图大小之类的因素。常数时间可能大于搜索小地图所用的对数时间。

Note: If you want to use your struct as key, or want to insert it into one of the standard library sets, you have further requirements:

注意：如果您想使用您的结构作为键，或者想将其插入标准库之一sets，您还有进一步的要求：

maps: You need to provide strict weak ordering, for the key, either via a less-than operator for your class, or a custom comparator functor. If you were to use personas a key, you woul dneed something like:

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

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

unordered_ or hash maps: You must provide both a hashfunction and an equality comparison for the key, either via an operator==or a functor. .

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