Recursive container

[Nekotekina]

Hi! It seems the following code example doesn't work due to the std::deque<std::pair<...>> type used.

class foo {
  tsl::ordered_map<foo, foo> map;
  bool operator==(const foo&) const;
};

namespace std {
  template <> struct hash<foo> {
.....
  };
}

However, std::unordered_map works in this situation. I use Visual Studio 2015 Update 3.

[Tessil]

Hi,

Do you have a full example?

The following code seems to work.

#include <iostream>
#include <ordered_map.h>

struct foo {
    tsl::ordered_map<int, foo> map;
};

int main() {
    foo f;

    f.map.insert({1, foo()});
    f.map.insert({2, foo()});

    std::cout << f.map.size() << std::endl;
}

[Nekotekina]

Hmm, updated the post. Maybe the fact I used the same type as a key matters.

[Tessil]

I still can't reproduce the problem, even with foo as key.

test.h

#pragma once

struct foo;

namespace std {
    template<>
    struct hash<foo> {
        size_t operator()(const foo& f) const;
    };
}

test.cpp

#include <iostream>
#include <ordered_map.h>
#include "test.h"

struct foo {
    foo(int id): m_id(id) {
    }

    bool operator==(const foo& f) const {
        return m_id == f.m_id;
    }

    int m_id;
    tsl::ordered_map<foo, foo> m_map;
};

size_t std::hash<foo>::operator()(const foo& f) const {
    return std::hash<int>()(f.m_id);
}

int main() {
    foo f(1);

    f.m_map.insert({foo(2), foo(22)});
    f.m_map.insert({foo(3), foo(33)});

    std::cout << f.m_map.size() << std::endl;
}

[Nekotekina]

Wait, I tried the first example, the error is the same in any case: error C2079: 'std::pair<Key,T>::second' uses undefined struct 'foo'

[Tessil]

I tested it with GCC and Clang. I will try on Visual Studio when I have time and come back to you.

[Tessil]

Recursive containers like that are, from what I understand from this discussion, undefined behavior. But on cppreference , we can read for std::vector (but not std::deque):

This container (but not its members) can be instantiated with an incomplete element type if the allocator satisfies the allocator completeness requirements. `

I don't know the standard well enough to be sure that struct foo { std::vector<foo> vect }; is a defined behavior, but struct foo { std::deque<foo> vect }; seems to be undefined.

struct foo {
    // Compile on GCC and Clang, not on Visual Studio. Undefined behavior?
    //std::deque<foo> deq;

    // Compile on GCC, Clang and Visual Studio. Defined behavior?
    std::vector<foo> vect;
};

You can try this:

struct foo {
    tsl::ordered_map<int, foo, std::hash<int>, std::equal_to<int>, 
                     std::allocator<std::pair<int, foo>>, 
                     std::vector<std::pair<int, foo>>> map;
};

It will store the elements in a std::vector instead of a std::deque which may slow down the rehash operation a bit, but should works well otherwise.

Edit:

There is a nice article about containers of incomplete types on Dr. Dobb's if it interests you.

[Tessil]

Out of curiosity I checked a little bit more.

Incomplete types for containers are an undefined behaviour before C++17. The N4510 proposition in C++17 added the support for incomplete types in std::vector, std::forward_list and std::list.

So theoretically an incomplete type for std::unordered_map is an undefined behaviour, even if the main compilers support it.

The Boost Container provides support for incomplete types. You could use boost::deque as ValueTypeContainer parameter to tsl::ordered_map if you really need it, but std::vector should work fine on most compilers.

[Nekotekina]

Thanks for the answer! Indeed, I didn't know that std::deque doesn't allow incomplete types. I'll try the workaround.