unordered_set <Foo>作爲Foo的數據成員？

Question

正如標題所說，我試圖使用包含Foo類對象的unordered_set作爲Foo類的數據成員。這在C++中可能嗎？

我有這樣的代碼：

#include <unordered_set> 
using namespace std; 

struct FooHash; 

class Foo { 
public: 
    int id; 
    unordered_set<Foo, FooHash> foos; // error here 
    bool operator==(const Foo& foo) { 
     return id == foo.id; 
    } 
}; 

struct FooHash { 
    size_t operator()(const Foo& foo) const { 
     return foo.id; 
    } 
}; 

int main() { 
    Foo f; 
    unordered_set<Foo, FooHash> foos; 
    return 0; 
} 

，但它引發以下錯誤：

In file included from /usr/include/c++/6.3.1/bits/hashtable.h:35:0, 
       from /usr/include/c++/6.3.1/unordered_set:47, 
       from main.cpp:1: 
/usr/include/c++/6.3.1/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::__is_noexcept_hash<Foo, FooHash>’: 
/usr/include/c++/6.3.1/type_traits:143:12: required from ‘struct std::__and_<std::__is_fast_hash<FooHash>, std::__detail::__is_noexcept_hash<Foo, FooHash> >’ 
/usr/include/c++/6.3.1/type_traits:154:38: required from ‘struct std::__not_<std::__and_<std::__is_fast_hash<FooHash>, std::__detail::__is_noexcept_hash<Foo, FooHash> > >’ 
/usr/include/c++/6.3.1/bits/unordered_set.h:95:63: required from ‘class std::unordered_set<Foo, FooHash>’ 
main.cpp:9:33: required from here 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:85:34: error: no match for call to ‘(const FooHash) (const Foo&)’ 
    noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 
      ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ 
In file included from /usr/include/c++/6.3.1/bits/move.h:57:0, 
       from /usr/include/c++/6.3.1/bits/stl_pair.h:59, 
       from /usr/include/c++/6.3.1/utility:70, 
       from /usr/include/c++/6.3.1/unordered_set:38, 
       from main.cpp:1: 
/usr/include/c++/6.3.1/type_traits: In instantiation of ‘struct std::__not_<std::__and_<std::__is_fast_hash<FooHash>, std::__detail::__is_noexcept_hash<Foo, FooHash> > >’: 
/usr/include/c++/6.3.1/bits/unordered_set.h:95:63: required from ‘class std::unordered_set<Foo, FooHash>’ 
main.cpp:9:33: required from here 
/usr/include/c++/6.3.1/type_traits:154:38: error: ‘value’ is not a member of ‘std::__and_<std::__is_fast_hash<FooHash>, std::__detail::__is_noexcept_hash<Foo, FooHash> >’ 
    : public integral_constant<bool, !_Pp::value> 

正向聲明兩個類，並宣佈該方法給出了這兩個錯誤後：

In file included from /usr/include/c++/6.3.1/unordered_set:44:0, 
       from main.cpp:1: 
/usr/include/c++/6.3.1/ext/aligned_buffer.h: In instantiation of ‘struct __gnu_cxx::__aligned_buffer<Foo>’: 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:246:43: required from ‘struct std::__detail::_Hash_node_value_base<Foo>’ 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:277:12: required from ‘struct std::__detail::_Hash_node<Foo, true>’ 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:1894:60: required from ‘struct std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<Foo, true> > >’ 
/usr/include/c++/6.3.1/bits/hashtable.h:170:11: required from ‘class std::_Hashtable<Foo, Foo, std::allocator<Foo>, std::__detail::_Identity, std::equal_to<Foo>, FooHash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’ 
/usr/include/c++/6.3.1/bits/unordered_set.h:96:18: required from ‘class std::unordered_set<Foo, FooHash>’ 
main.cpp:12:37: required from here 
/usr/include/c++/6.3.1/ext/aligned_buffer.h:85:34: error: invalid application of ‘sizeof’ to incomplete type ‘Foo’ 
    : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value> 
           ^
/usr/include/c++/6.3.1/ext/aligned_buffer.h:85:34: error: invalid application of ‘sizeof’ to incomplete type ‘Foo’ 
/usr/include/c++/6.3.1/ext/aligned_buffer.h: In instantiation of ‘void* __gnu_cxx::__aligned_buffer<_Tp>::_M_addr() [with _Tp = Foo]’: 
/usr/include/c++/6.3.1/ext/aligned_buffer.h:110:41: required from ‘_Tp* __gnu_cxx::__aligned_buffer<_Tp>::_M_ptr() [with _Tp = Foo]’ 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:250:34: required from ‘_Value* std::__detail::_Hash_node_value_base<_Value>::_M_valptr() [with _Value = Foo]’ 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:1971:36: required from ‘void std::__detail::_Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(std::__detail::_Hashtable_alloc<_NodeAlloc>::__node_type*) [with _NodeAlloc = std::allocator<std::__detail::_Hash_node<Foo, true> >; std::__detail::_Hashtable_alloc<_NodeAlloc>::__node_type = std::__detail::_Hash_node<Foo, true>]’ 
/usr/include/c++/6.3.1/bits/hashtable_policy.h:1984:22: required from ‘void std::__detail::_Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(std::__detail::_Hashtable_alloc<_NodeAlloc>::__node_type*) [with _NodeAlloc = std::allocator<std::__detail::_Hash_node<Foo, true> >; std::__detail::_Hashtable_alloc<_NodeAlloc>::__node_type = std::__detail::_Hash_node<Foo, true>]’ 
/usr/include/c++/6.3.1/bits/hashtable.h:1901:7: required from ‘void std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::clear() [with _Key = Foo; _Value = Foo; _Alloc = std::allocator<Foo>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<Foo>; _H1 = FooHash; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]’ 
/usr/include/c++/6.3.1/bits/hashtable.h:1227:12: required from ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::~_Hashtable() [with _Key = Foo; _Value = Foo; _Alloc = std::allocator<Foo>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<Foo>; _H1 = FooHash; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]’ 
/usr/include/c++/6.3.1/bits/unordered_set.h:126:7: required from here 
/usr/include/c++/6.3.1/ext/aligned_buffer.h:99:36: error: using invalid field ‘__gnu_cxx::__aligned_buffer<_Tp>::_M_storage’ 
     return static_cast<void*>(&_M_storage); 

看來標準中不允許使用不完整類型的容器。我想嘗試使用指針，但不能爲指針操作數重載operator==。任何解決方法？

Answer 1

在將它們用作unordered_set的模板參數之前，您需要完全定義您的類。雖然Foo不能完全定義期間它是自己的定義，但它的指針類型是。您可以很容易地將Foo替換爲unique_ptr<Foo>以解決此問題。

#include <memory> 
#include <unordered_set> 

// Forward declaration 
class Foo; 

// Declare classes 
struct FooHash { 
    size_t operator()(const std::unique_ptr<Foo>& foo) const; 
}; 

class Foo { 
public: 
    int id; 
    std::unordered_set<std::unique_ptr<Foo>, FooHash> foos; 
}; 

// Method implementations 
size_t FooHash::operator()(const std::unique_ptr<Foo>& foo) const { 
    return foo->id; 
} 

Answer 2

正如弗朗索瓦·安德里厄已經在his answer指出的，一個不完全類型不能與標準:: unordered_set使用。他用std::unique_ptr給出了一個可能的解決方案。

一個使用std::unique_ptr可能是你的類現在需要明確的動態內存分配插入到Foo::foos的缺點。在我看來，這是一個應該隱藏的實現細節。

另一個（也可能更大）的問題可能是你的鬆散值語義，因爲std :: unique_ptr只能被移動，不能被複制。你將不得不實現自定義拷貝構造函數和賦值操作符來獲取價值語義。

使用boost::recursive_wrapper，還有另一種可能的解決方案，隱藏指針。雖然boost::recursive_wrapper是爲boost::variant發明的，但它可用於不允許使用不完整類型的其他情況。

隨着recursive_wrapper，Foo類變爲：

class Foo { 
public: 
    using Wrapper = boost::recursive_wrapper<Foo>; 

    Foo() = default; 
    explicit Foo(int id) : id(id) {} 

    struct Hash { 
     size_t operator()(const Wrapper& foo) const { return foo.get().id; } 
    }; 

    struct KeyEqual { 
     bool operator()(const Wrapper& foo1, const Wrapper& foo2) const { 
      return foo1.get().id == foo2.get().id; 
     } 
    }; 

    using Set = std::unordered_set< Wrapper, Hash, KeyEqual >; 
    Set foos; 
    int id = 0; 
}; 

我用3號模板參數KeyEqualstd::unordered_set的從Foo::operator==獨立定義密鑰的平等方面取得的另一個變化。現在Foo::operator==可以通過比較所有 Foo的成員，而不僅僅是ID來實現。這留給讀者作爲練習。

要插入並找到Foo::foos中的項目，您可以定期創建Foo實例，而無需使用動態內存分配。在幕後，boost::recursive_wrapper會動態分配內存。

當您通過Foo::Set的迭代器訪問Foo時，您將注意到將使用包裝器的唯一位置，因爲您必須致電boost::reference_wrapper::get()。這並不比使用需要使用雙重間接的std::unique_ptr差（即，(*it)->id）。

用法示例：

int main() { 
    Foo f1; 

    // No explicit dynamic memory allocation here! 
    f1.foos.insert(Foo(1)); 
    f1.foos.insert(Foo(1)); 
    f1.foos.insert(Foo(2)); 

    // Value semantics are kept. 
    Foo f2 = f1; 

    f2.foos.erase(Foo(1)); 

    std::cout << "f1.size: " << f1.foos.size() << std::endl; 
    std::cout << "f2.size: " << f2.foos.size() << std::endl; 

    // Find a Foo, still clean syntax. 
    auto it = f1.foos.find(Foo(2)); 
    if(it != f1.foos.end()) 
    { 
     // Only when accessing Foo through the iterator we notice 
     // the recursive_wrapper because we must call its get() method. 
     std::cout << "found a Foo with id: " << it->get().id << std::endl; 
    }  
    return 0; 
} 

完整的示例：http://coliru.stacked-crooked.com/a/00d2a48106f2cc99