[Bug libstdc++/53339] New: unordered_map::iterator requires Value to be complete type

["eltoder at gmail dot com" <gcc-bugzilla@gcc.gnu.org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53339

             Bug #: 53339
           Summary: unordered_map::iterator requires Value to be complete
                    type
    Classification: Unclassified
           Product: gcc
           Version: 4.6.3
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: eltoder@gmail.com


Created attachment 27393
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27393
Simple test case

Sometimes it's useful to refer to map's iterator from map's value, e.g.:

#include <string>
#include <tr1/unordered_map>

struct LinkedHashMap
{
    struct Entry;
    typedef std::tr1::unordered_map<std::string, Entry> Storage;
    typedef Storage::iterator EntryPtr; // <-- fails here
    struct Entry
    {
        EntryPtr prev, next;
    };

    Storage  storage_;
    EntryPtr head_;
};

(here we combine hash map with linked list implemented via iterators).
It doesn't seem unreasonable to expect this to compile, however it doesn't:

In file included from /usr/include/c++/4.6/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/4.6/bits/char_traits.h:41,
                 from /usr/include/c++/4.6/string:42,
                 from linkedhash.cc:1:
/usr/include/c++/4.6/bits/stl_pair.h: In instantiation of 'std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>':
/usr/include/c++/4.6/bits/stl_function.h:486:12:   instantiated from
'std::_Select1st<std::pair<const std::basic_string<char>, LinkedHashMap::Entry>
>'
/usr/include/c++/4.6/tr1/hashtable_policy.h:708:20:   instantiated from
'std::tr1::__detail::_Hash_code_base<std::basic_string<char>, std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>, std::_Select1st<std::pair<const
std::basic_string<char>, LinkedHashMap::Entry> >,
std::equal_to<std::basic_string<char> >, std::tr1::hash<std::basic_string<char>
>, std::tr1::__detail::_Mod_range_hashing,
std::tr1::__detail::_Default_ranged_hash, false>'
/usr/include/c++/4.6/tr1/hashtable.h:108:11:   instantiated from
'std::tr1::_Hashtable<std::basic_string<char>, std::pair<const
std::basic_string<char>, LinkedHashMap::Entry>, std::allocator<std::pair<const
std::basic_string<char>, LinkedHashMap::Entry> >,
std::_Select1st<std::pair<const std::basic_string<char>, LinkedHashMap::Entry>
>, std::equal_to<std::basic_string<char> >,
std::tr1::hash<std::basic_string<char> >,
std::tr1::__detail::_Mod_range_hashing,
std::tr1::__detail::_Default_ranged_hash,
std::tr1::__detail::_Prime_rehash_policy, false, false, true>'
/usr/include/c++/4.6/tr1/unordered_map.h:43:11:   instantiated from
'std::tr1::__unordered_map<std::basic_string<char>, LinkedHashMap::Entry,
std::tr1::hash<std::basic_string<char> >, std::equal_to<std::basic_string<char>
>, std::allocator<std::pair<const std::basic_string<char>,
LinkedHashMap::Entry> >, false>'
/usr/include/c++/4.6/tr1/unordered_map.h:180:11:   instantiated from
'std::tr1::unordered_map<std::basic_string<char>, LinkedHashMap::Entry>'
linkedhash.cc:8:20:   instantiated from here
/usr/include/c++/4.6/bits/stl_pair.h:93:11: error: 'std::pair<_T1,
_T2>::second' has incomplete type
linkedhash.cc:6:12: error: forward declaration of 'struct LinkedHashMap::Entry'

The problem is that _Select1st<pair<Key,Value> > forces instantiation of pair
when trying to declare its return type:

template<typename _Pair>
struct _Select1st : public unary_function<_Pair,
                                          typename _Pair::first_type> // <--

but pair cannot be instantiated until both types are complete. This is can be
worked around by using unordered_set or using _Hashtable directly, but
* This code compiles if unordered_map is replaced by map. Would be nice to keep
them consistent.
* There doesn't seem to be any fundamental reason why this doesn't work -- it
comes from a minor implementation choice and seems very easy to fix.