Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to have an unordered_map where the value type is the class it's in?

Tags:

c++

This code:

class Foo {
    std::unordered_map<std::string, Foo> x;
};

gives me an error:

/usr/include/c++/4.7/bits/stl_pair.h:94:11:
  error: 'std::pair<_T1, _T2>::second' has incomplete type
foo.cpp:4:7: error: forward declaration of 'class Foo'

However, this code compiles just fine:

class Foo {
    std::vector<Foo> x;
};

Is this a library/compiler bug?

like image 895
Martin C. Martin Avatar asked Oct 26 '12 14:10

Martin C. Martin


People also ask

Are elements sorted in unordered_map?

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets.

How are elements stored in unordered_map?

unordered_map is an associated container that stores elements formed by the combination of a key value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.

Can unordered map have pair as key?

Unordered Map does not contain a hash function for a pair like it has for int, string, etc, So if we want to hash a pair then we have to explicitly provide it with a hash function that can hash a pair. unordered_map can takes upto 5 arguments: Key : Type of key values.


1 Answers

The C++ standard specifies for the various smart pointers that the template parameter is allowed to be an incomplete type.

The 2017 and later versions of the standard allow a container's value_type to be an incomplete type when instantiating the class template only for the container templates std::forward_list, std::list, and std::vector, and only if the allocator type satisfies the "allocator completeness requirements". The default allocator template std::allocator always satisfies the allocator completeness requirements. Instantiating any member of the container class template still requires the value_type to be complete.

For any other standard container type, this information is not given. In cases where it is unspecified, an implementation is allowed to accept an incomplete type for one container class template and not another, and still be conformant.

To make your code portable, avoid making containers of any type before the type is completed, except in the cases specifically permitted by the standard.

Formally, the general constraint is found in the following rule ([res.on.functions]) which applies to your code:

In certain cases (replacement functions, handler functions, operations on types used to instantiate standard library template components), the C++ standard library depends on components supplied by a C++ program. If these components do not meet their requirements, the Standard places no requirements on the implementation.

In particular, the effects are undefined in the following cases:

...

  • if an incomplete type is used as a template argument when instantiating a template component, unless specifically allowed for that component.

The three statements specifically allowing an incomplete template argument for forward_list, list, and vector are found in sections [forwardlist.overview], [list.overview], and [vector.overview].

like image 70
Ben Voigt Avatar answered Oct 25 '22 19:10

Ben Voigt