CODEWITHSUNDEEP
c++templatesc++11
Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19837

How to use unordered_map in base class with curiously recurring template pattern?

I'm using curiously recurring template pattern:

#include <unordered_map>

using namespace std;

template<class S>
struct State {
    unordered_map<int, S> children; // <-- problem!
};

struct TicTacToeState : public State<TicTacToeState> {
    // implementation
};

int main() {
    return 0;
}

Basically, I want to have an unordered_map of children states in a (base) State.

Compile with g++ file.cpp -std=c++11:

In file included from /usr/include/c++/4.8/utility:70:0,
                 from /usr/include/boost/config/no_tr1/utility.hpp:21,
                 from /usr/include/boost/config/select_stdlib_config.hpp:37,
                 from /usr/include/boost/config.hpp:40,
                 from /usr/include/boost/functional/hash/hash_fwd.hpp:17,
                 from /usr/include/boost/functional/hash/hash.hpp:13,
                 from /usr/include/boost/functional/hash.hpp:6,
                 from tests/../examples/tic_tac_toe.cpp:1,
                 from tests/test_tic_tac_toe.cpp:3:
/usr/include/c++/4.8/bits/stl_pair.h: In instantiation of ‘struct std::pair<const long unsigned int, TicTacToeState>’:
/usr/include/c++/4.8/type_traits:615:28:   required from ‘struct std::__is_destructible_impl<std::pair<const long unsigned int, TicTacToeState> >’
/usr/include/c++/4.8/type_traits:637:12:   required from ‘struct std::__is_destructible_safe<std::pair<const long unsigned int, TicTacToeState>, false, false>’
/usr/include/c++/4.8/type_traits:652:12:   required from ‘struct std::is_destructible<std::pair<const long unsigned int, TicTacToeState> >’
/usr/include/c++/4.8/type_traits:116:12:   required from ‘struct std::__and_<std::is_destructible<std::pair<const long unsigned int, TicTacToeState> >, std::__is_direct_constructible_impl<std::pair<const long unsigned int, TicTacToeState>, const std::pair<const long unsigned int, TicTacToeState>&> >’
/usr/include/c++/4.8/type_traits:817:12:   required from ‘struct std::__is_direct_constructible_new_safe<std::pair<const long unsigned int, TicTacToeState>, const std::pair<const long unsigned int, TicTacToeState>&>’
/usr/include/c++/4.8/type_traits:895:12:   [ skipping 5 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
/usr/include/c++/4.8/type_traits:974:12:   required from ‘struct std::is_copy_constructible<std::pair<const long unsigned int, TicTacToeState> >’
/usr/include/c++/4.8/bits/alloc_traits.h:540:12:   required from ‘struct std::__is_copy_insertable<std::allocator<std::pair<const long unsigned int, TicTacToeState> > >’
/usr/include/c++/4.8/bits/alloc_traits.h:560:63:   required by substitution of ‘template<class _Alloc> using __check_copy_constructible = std::__allow_copy_cons<std::__is_copy_insertable<_Alloc>::value> [with _Alloc = std::allocator<std::pair<const long unsigned int, TicTacToeState> >]’
/usr/include/c++/4.8/bits/unordered_map.h:97:11:   required from ‘class std::unordered_map<long unsigned int, TicTacToeState, std::hash<long unsigned int>, std::equal_to<long unsigned int>, std::allocator<std::pair<const long unsigned int, TicTacToeState> > >’
tests/../examples/../gtsa.hpp:110:30:   required from ‘struct State<TicTacToeState, TicTacToeMove>’
tests/../examples/tic_tac_toe.cpp:69:32:   required from here
/usr/include/c++/4.8/bits/stl_pair.h:102:11: error: ‘std::pair<_T1, _T2>::second’ has incomplete type
       _T2 second;                /// @c second is a copy of the second object
           ^
In file included from tests/test_tic_tac_toe.cpp:3:0:
tests/../examples/tic_tac_toe.cpp:69:8: error: forward declaration of ‘struct TicTacToeState’
 struct TicTacToeState : public State<TicTacToeState, TicTacToeMove> {
        ^
In file included from /usr/include/c++/4.8/utility:70:0,
                 from /usr/include/boost/config/no_tr1/utility.hpp:21,
                 from /usr/include/boost/config/select_stdlib_config.hpp:37,
                 from /usr/include/boost/config.hpp:40,
                 from /usr/include/boost/functional/hash/hash_fwd.hpp:17,
                 from /usr/include/boost/functional/hash/hash.hpp:13,
                 from /usr/include/boost/functional/hash.hpp:6,
                 from tests/../examples/tic_tac_toe.cpp:1,
                 from tests/test_tic_tac_toe.cpp:3:
/usr/include/c++/4.8/bits/stl_pair.h: In instantiation of ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = long unsigned int&; _U2 = TicTacToeState&; <template-parameter-2-3> = void; _T1 = const long unsigned int; _T2 = TicTacToeState]’:
tests/../examples/../gtsa.hpp:640:57:   required from ‘S* MonteCarloTreeSearch<S, M>::add_child(S*, M&) [with S = TicTacToeState; M = TicTacToeMove]’
tests/../examples/../gtsa.hpp:472:41:   required from ‘S* MonteCarloTreeSearch<S, M>::tree_policy(S*, S*) [with S = TicTacToeState; M = TicTacToeMove]’
tests/../examples/../gtsa.hpp:453:44:   required from ‘void MonteCarloTreeSearch<S, M>::monte_carlo_tree_search(S*) [with S = TicTacToeState; M = TicTacToeMove]’
tests/../examples/../gtsa.hpp:433:41:   required from ‘M MonteCarloTreeSearch<S, M>::get_move(S*) [with S = TicTacToeState; M = TicTacToeMove]’
tests/test_tic_tac_toe.cpp:123:1:   required from here
/usr/include/c++/4.8/bits/stl_pair.h:145:64: error: using invalid field ‘std::pair<_T1, _T2>::second’
  : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { }
                                                                ^

My understanding is:

I'm asking to create a struct TicTacToeState, it looks what's the base class, aha, it's template, fine, it tries to instantiate State with S = TicTacToeState but fails, because unordered_map<int, S> needs already defined type for map values, but TicTacToeState wasn't defined.

Placing TicTacToeState in front won't help, because then it will have no State declaration at hand.

If somebody would like to have a broader look at the original code, State is defined here. I use CRTP for the first time, maybe I don't need it and it's only complicating the code? I don't know, I haven't found anything simpler.

How to make it work?

Upvotes: 1

Views: 846

Answers (1)

JVApen
JVApen

Reputation: 11317

Classes/structs can't have members which are incomplete types, so they cannot refer to itself, since they need a definition of itself to form this class.

Since looping over std::unordered_map should give you a reference to std::pair<const Key, Value> it requires a complete type.

So, in order to do something like this, you'll have to use a wrapper class which makes use of allocations, allowing you to first complete the type and use it elsewhere. In most cases I would use std::unordered_map<int, std::unique_ptr<S>>, though if you really require the element to be created, you can wrap it.

struct SWrapper final
{
    SWrapper();
    operator S&() { return *_S; }
    operator const S&() const { return *_S; }
private:
    std::unique_ptr<S> _S;
};

// In .cpp
SWrapper::SWrapper() : _S(std::make_unique<S>()) {}

Upvotes: 2

Related Questions