Unordered_map with custom class as key

Question

I am working on a compiler right now and I am trying to represent the scope class by inheriting from unordered_map, because it is essentially a hash table of symbols to declarations. I added a custom hash function to the symbol, but I am getting an error complaining there is no default constructor for initializing a std::pair. Here is the relevant code:

Symbol.hpp

#pragma once

#include <string>
#include <unordered_set>


class Symbol
{
    friend class Symbol_table;

    Symbol(std::string const* str) : m_str(str) { }
    /// Constructs the symbol from `str`.

public:
    Symbol() : m_str() { }

    std::string const& str() const { return *m_str; }
    /// Returns the spelling of the token.

    friend bool operator==(Symbol a, Symbol b) 
    {
        return a.m_str == b.m_str;
    }

    friend bool operator!=(Symbol a, Symbol b) 
    {
        return a.m_str != b.m_str;
    }

private:
    std::string const* m_str;  
};


class Symbol_table : std::unordered_set<std::string>
{
public:
    Symbol get(std::string const& str);
    /// Returns the unique symbol for `str`.

    Symbol get(char const* str);
    /// Returns the unique symbol for `str`.
};

inline Symbol
Symbol_table::get(std::string const& str)
{
    return &*emplace(str).first;
}

inline Symbol
Symbol_table::get(char const* str)
{
    return &*emplace(str).first;
}


namespace std
{
    template<>
    struct hash<::Symbol>
    {
        std::size_t operator()(::Symbol sym) const noexcept
        {
            std::hash<std::string const*> h;
            return h(&sym.str());
        }
    };
};

Scope.hpp

#pragma once

#include "decl.hpp"
#include "name.hpp"

#include <string>
#include <vector>
#include <unordered_map>

struct Scope : std::unordered_map<Symbol, Decl*>
{
    Decl* lookup(Symbol sym)
    {
        auto iter = find(sym);
        if (iter == end())
        {
            return nullptr;
        }
        return iter->second;
    }

    void declare(Decl* d)
    {
        assert(!already_declared(d));
        emplace(d->get_name()->get_str(), d);
    }

    bool already_declared(Decl* d)
    {
        return d->get_name() != nullptr;
    }
};

struct Scope_stack : std::vector<Scope>
{
    Decl* lookup(Symbol sym)
    {
        for (auto iter = rbegin(); iter != rend(); ++iter)
        {
            if (Decl * d = iter->lookup(sym))
            {
                return d;
            }
        }
        return nullptr;
    }
};

And here is the compilation error:

/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1805:31: error: no matching constructor for initialization of
      'std::__1::pair<const Symbol, Decl *>'
            ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
                              ^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

There is a lot more below this error that I put in this pastebin.

Please edit your question to contain [mcve], in general it is not recommended to inherit from STL containers — Slava, Dec 13 '18 at 15:57
Why are your inheriting from `std::unordered_map` and `std::vector`? That doesn't look right. Those should probably be members of the class, not parents. — NathanOliver, Dec 13 '18 at 15:58
I switched it to not inherit and made it a member, still same error. — Nick Gallimore, Dec 13 '18 at 16:00
The problem is with symbol.hpp not having a default pair constructor — Nick Gallimore, Dec 13 '18 at 16:01
In general it is [not a good idea to inherit from standard containers](https://stackoverflow.com/questions/6806173/subclass-inherit-standard-containers). — TypeIA, Dec 13 '18 at 16:01
Absolutely it is. If someone tells you they're having problems getting their nail to hold in some brick, would you show them how to superglue it, or advise them to use a masonry screw instead? — TypeIA, Dec 13 '18 at 16:05
@TypeIA If someone asks why a nail is not successfully holding in some brick, "use a masonry screw instead" is a tangential suggestion rather than an answer to their question. And, indeed, inheriting from std containers _has nothing to do with this question_! — Lightness Races in Orbit, Dec 13 '18 at 16:09
@TypeIA Also note that this is _private_ inheritance, which really upsets the typical "don't inherit" argument, as explored on that page you linked to — Lightness Races in Orbit, Dec 13 '18 at 16:10
Take it up with the compiler professor who wrote that line of code. I mean he only did his PHD under Bjarne and is on the C++ std committee. — Nick Gallimore, Dec 13 '18 at 16:10
"Take it up with the compiler professor" Post his contact details and I'll message him. — n. m. could be an AI, Dec 13 '18 at 16:20

score 6 · Accepted Answer · answered Dec 13 '18 at 16:02

emplace(d->get_name()->get_str(), d);

Here you try to construct a std::unordered_map<Symbol, Decl*>::value_type (i.e. a std::pair<Symbol, Decl*>) from a const std::string& and a Decl*.

The problem is that Symbol has no constructor taking a std::string, only a std::string const*.

This is the line in the error messages that gives the hint:

/Library/Developer/CommandLineTools/usr/include/c++/v1/utility:422:5: note: candidate constructor not viable: no known conversion from
      'std::__1::basic_string<char>' to 'const const Symbol' for 1st argument
    pair(_T1 const& __t1, _T2 const& __t2)

error message pointing to `/Users/nfgallimore/Code/Compilers/malan/src/scope.hpp:25:13:` is more handy for me. Then message you have pasted flows it. — Marek R, Dec 13 '18 at 16:05

Unordered_map with custom class as key

1 Answers1