[PATCH] Make dense_hash_map work with non-default-constructible values

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Under C++11, try to compile google::dense_hash_map<int, 
std::reference_wrapper<int>> x;
2. Observe that compilation fails due to trying to default-construct the 
reference_wrapper.

What is the expected output? What do you see instead?

The code should compile. It's a perfectly reasonable thing to do if you are 
trying to build a secondary index on top of a data structure. Please see the 
attached patch for a proposed fix.

What version of the product are you using? On what operating system?

sparsehash-2.0.2 on Ubuntu 14.04 and CentOS 6.3
Ran "make check" in non-C++11 mode with g++-4.8, and in C++11 mode with g++-4.8 
and g++-4.9.

lesha@ubuntu:~/sparsehash/patch$ cat demo1.cpp 
#include <sparsehash/dense_hash_map>

int main() {
  google::dense_hash_map<int, std::reference_wrapper<int>> x;
  return 0;
}
lesha@ubuntu:~/sparsehash/patch$ g++ -std=c++11 demo1.cpp -o demo1 && ./demo1
lesha@ubuntu:~/sparsehash/patch$ cat demo2.cpp 
#include <sparsehash/dense_hash_map>

int main() {
  int a = 5;
  google::dense_hash_map<int, std::reference_wrapper<int>> x;
  x.set_empty_value(std::make_pair(0, std::ref(a)));
  x.insert(std::make_pair(3, std::ref(a)));
  return 0;
}
lesha@ubuntu:~/sparsehash/patch$ g++ -std=c++11 demo2.cpp -o demo2 && ./demo2
lesha@ubuntu:~/sparsehash/patch$ 

Original issue reported on code.google.com by snarkmas...@gmail.com on 19 Feb 2015 at 3:55

Attachments:

• dense_hash_map_non_default_constructible.patch

[GoogleCodeExporter]

As an alternative, would it be acceptable to add "empty type" and maybe even 
"deleted type" class template parameters? Those types must be pairs that 
potentially differ from `value_type` in their second field. This is fine, since 
we never access the `mapped_type` of deleted or empty elements, so any type 
with the same size and alignment requirements would do. We could even leave the 
`mapped_type` memory uninitialized for those values, potentially improving 
deletion perf.

This approach has a lot of advantages, such as:
 - The user can make the class behave just like std::unordered_map by specifying those template extra parameters
 - Non-default-constructible types can be transparently supported in C++11 (since it has good memory layout introspection).
 - Prior to C++11, it's pretty simple for folks to make this work for non-default-constructible types, e.g. like this:

struct EmptyValueType : std:pair<Key, Data> {
  EmptyValueType() : std::pair<Key, Data>(makeEmptyKey(), makeEmptyValue()) {}
};
google::dense_hash_map<Key, Data, HashFcn, EqualKey, Alloc, EmptyValueType> h;

PS Thanks to John Fremlin for the helpful discussion that led to this 
counter-proposal.

Original comment by snarkmas...@gmail.com on 22 Feb 2015 at 8:38