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

Question

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

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

#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?

Solution 1

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

my_map["one"]

my_map["one"] constructs a std::string from "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.

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

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:

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:

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:

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

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

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

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

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 identifier will be an empty string.

Solution 2

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:

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:

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.

Since you mentioned hashing, C++11 provides std::unordered_map, and tr1 and boost have 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.

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:

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 person as a key, you woul dneed something like:

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

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

Comments

[juanchopanza]

The search for an element with a given key does not traverse the whole map, see answer below.

[bdonlan]

No, the default copy and assignment operators will work fine here. Just a default constructor ought to be enough.

[moriesta]

@juanchopanza and what is default constructor in this case? I mean how exactly should the default constructor look like?

[weidi]

using operator[] can insert new entry into the map, which might not be expected i think, if the intent is just to check for existence. Maybe some more explanation on that

[juanchopanza]

@Acute I added it to the answer. Of course, depending on your data members you might actually want to do something.

[juanchopanza]

@Acute to be clear, strict weak ordering, equality comparison, hashing are only required if you want to use your class as a key, or if you want to insert it into a set.

[moriesta]

Huge thanks for detailed explanation! Now I understand how do struct constructors and operator[] work!