When I loop through a C++ map, why does it give me an instantiation error?

Question

I am trying to loop through a map but nothing I try seems to work... I declare and define the map as follows:

// loop through the strings and group based on length
map<size_t, NGroup> groups;
for (size_t i = 0; i < strs.size(); i++) {
    size_t len = strs[i].size();
    if (groups.count(len) != 0) {
        groups.at(len).appendString(strs[i]);
    } else {
        NGroup g(strs[i]);
        groups[len] = g;
    }
}

with the following relevant classes:

class AnagramGroup {
public:
    map<char, size_t> freqs;
    map<char, size_t> ground;
    vector<string> anagrams;

    AnagramGroup(map<char, size_t> m, string anagram) {
        freqs = m;
        ground = m;
        anagrams.push_back(anagram);
    }
    AnagramGroup(AnagramGroup &other);
};

class NGroup {
public:
    vector<string> strings;
    vector<AnagramGroup> groups;

    NGroup(string str) {
        vector<string> strs = {str};
        strings = strs;
    }
    NGroup(vector<string> strs) {
        strings = strs;
    }
    NGroup(NGroup &other);

    void appendString(string str) {
        strings.push_back(str);
    }
};

And I have tried to loop through the map using the ways listed here:

map<size_t, NGroup>::iterator it;
for (it = groups.begin(); it != groups.end(); it++) {
...
}

for (const auto &p : groups) {
...
}

But I always get the same error:

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:13:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/cmath:1927:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/specfun.h:45:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algobase.h:64:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_pair.h:303:17: error: the parameter for this explicitly-defaulted copy constructor is const, but a member or base requires it to be non-const
      constexpr pair(const pair&) = default;
                ^
Line 61: Char 38: note: in instantiation of template class 'std::pair<const unsigned long, NGroup>' requested here
        for (it = groups.begin(); it != groups.end(); it++) {
                                     ^

What am I missing?

Answer 1

std::map needs to support this semantic:

NGroup ng& = groups["some key that doesn't exist in this map"];

When the key is not in the map, it default constructs an instance of your value type of the map and assigns it at that key. Without a default constructor, it doesn't know what to pass to you object's constructor.

Thus, NGroup needs a default constructor. This fixed it for me:

class NGroup {
public:
    vector<string> strings;
    vector<AnagramGroup> groups;

    NGroup() {  // add this

    }

Also, neither NGroup nor AnagramGroup need a copy constructor since the default constructor will do the right thing. So you can just remove both. The copy constructor is only needed when a member variable can't be trivially copied or rely or the member variable's own copy constructors.

Now let's clean up the rest of your code by passing most parameters as const reference so you aren't making so me inadvertent copies of those strings and collections.

class AnagramGroup {
public:
    map<char, size_t> freqs;
    map<char, size_t> ground;
    vector<string> anagrams;

    AnagramGroup(const map<char, size_t>& m, const string& anagram) :
        freqs(m), ground(m), anagrams({anagram}) {
    }

};

class NGroup {
public:
    vector<string> strings;
    vector<AnagramGroup> groups;

    NGroup() {

    }

    NGroup(const string& str) : strings({ str }) {
    }

    NGroup(const vector<string>& strs) : strings(strs) {
    }

    void appendString(const string& str) {
        strings.push_back(str);
    }
};

Answer 2

The problem is that your "copy constructors" aren't really a copy constructors since they accept their parameters by reference to non-const. Change your copy constructors to accept a reference-to-const or remove them if all they do is a field-by-field copy, since the compiler will auto-generate copy constructors that do that.

The elements of a std::map are std::pairs, and std::pair is copyable. When instantiating the copy constructor of std::pair<const size_t, NGroup>, the compiler is going to come up with something like this:

pair(const pair& other)
    : first(other.first),
      second(other.second)
{}

But since other is a reference-to-const, that means that other.second is a const NGroup. NGroup has no constructor that accepts a const NGroup as a parameter, and so the std::pair instantiation is invalid.