2

Consider the following (C++) code

class A {...};

namespace std
{
    template<>
    struct hash<A>
    {
        size_t operator() (const A& a) const
        {
            // returns unique hash based on components of A
        };
    };
}

class B
{
    std::unordered_map<A, B> *children; //ignore the fact that its a pointer for now
};

When I compile, the compiler tells me that std::pair<_T1, _T2>::second has incomplete type (among other errors), which I assume is my fault for declaring it in B, however I don't know how I should do it correctly.

bathtub
  • 426
  • 3
  • 15
  • can you provide the code you are trying to compile? including the definition of B? – user1708860 Sep 19 '13 at 23:27
  • Please provide executable example. – zch Sep 19 '13 at 23:27
  • @sehe Actually I realized that my example is too generic. If I create an executable example using this, it compiles, so I need to pinpoint more specifically. I will do my best to narrow it down – bathtub Sep 20 '13 at 00:15

1 Answers1

4

I think the standard library doesn't in general (have to) support incomplete types.

As I remember, Boost Container library explicitely supports this, though:

Containers of Incomplete Types

What about standard containers? Containers of incomplete types have been under discussion for a long time, as explained in Matt Austern's great article (The Standard Librarian: Containers of Incomplete Types):

“Unlike most of my columns, this one is about something you can't do with the C++ Standard library: put incomplete types in one of the standard containers. This column explains why you might want to do this, why the standardization committee banned it even though they knew it was useful, and what you might be able to do to get around the restriction.”

All containers offered by Boost.Container can be used to define recursive containers.

See it Live on Coliru

#include <boost/container/vector.hpp>
#include <boost/container/list.hpp>
#include <boost/container/map.hpp>
#include <boost/container/stable_vector.hpp>
#include <boost/container/string.hpp>

using namespace boost::container;

struct data
{
   int               i_; 
   vector<data>      v_; //A vector holding still undefined class 'data'
   list<data>        l_; //A list holding still undefined 'data'
   map<data, data>   m_; //A map holding still undefined 'data'

   friend bool operator <(const data &l, const data &r)
   { return l.i_ < r.i_; }
};

struct tree_node
{
   string name;
   string value;

   //children nodes of this node
   list<tree_node>        children_;
};

int main()
{
   //a container holding a recursive data type
   stable_vector<data> sv;
   sv.resize(100);

   //Let's build a tree based in
   //a recursive data type
   tree_node root;
   root.name  = "root";
   root.value = "root_value";
   root.children_.resize(7);
   return 0;
}
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Interesting [this strangely related question](http://stackoverflow.com/questions/18905090/how-to-declare-two-classes-such-that-a-has-members-of-b-and-b-marks-members-of-a) surfaced today as well. It even stirred up conversation over the very notion of supporting incomplete types in-general [via this unrelated question answer](http://stackoverflow.com/questions/18672135/why-c-containers-dont-allow-incomplete-types/18672346#18672346) (oh, and +1) – WhozCraig Sep 20 '13 at 00:21
  • Well the interesting thing is that my example given will compile, however not the actual code from which the error occurred – bathtub Sep 20 '13 at 00:28
  • Probably because your code shown does _shallow instantiation_ of `unordered_map<...>`, not the members: once you start _using_ members, they will get instantiated and _then_ you will see the errors springing up. This is known as POI (Point Of Instantiation) – sehe Sep 20 '13 at 00:31
  • See e.g. **[What is POI and what does it mean?](http://stackoverflow.com/a/3866268/85371)** and a nice mind-twisting example of that with ADL: **[here](http://stackoverflow.com/a/12921672/85371)** – sehe Sep 20 '13 at 00:34
  • @WhozCraig oh hey, I missed your comment. That's funny indeed. I'm glad I referenced the same seminal article by M.Austern :/ – sehe Sep 20 '13 at 00:39
  • So my code is f***ed via this implementation... Thanks for the info. And in the simpler example, I gave B an int. Are you saying if it were a complicated user defined type, like in the actual code, it doesn't work? – bathtub Sep 20 '13 at 00:45