Stack Overflow
Stack Overflow

Questions tagged [sparsehash]

An extremely memory-efficient hash_map implementation from google. 2 bits/entry overhead! The SparseHash library contains several hash-map implementations, including implementations that optimize for space or speed.

An extremely memory-efficient hash_map implementation from google. 2 bits/entry overhead! The SparseHash library contains several hash-map implementations, including implementations that optimize for space or speed.

These hashtable implementations are similar in API to SGI's hash_map class and the tr1 unordered_map class, but with different performance characteristics. It's easy to replace hash_map or unordered_map by sparse_hash_map or dense_hash_map in C++ code.

They also contain code to serialize and unserialize from disk.

http://code.google.com/p/sparsehash/

11 questions
22
votes
2 answers

What is the main implementation idea behind sparse hash table?

Why does Google sparsehash open-source library has two implementations: a dense hashtable and a sparse one?
Denis Gorodetskiy
  • 2,884
  • 3
  • 21
  • 23
9
votes
2 answers

Redefinition of tuple when using gtest and google sparsehash

All test cases that somehow include and fail to build for me. Usually the later is included indirectly but I can reproduce the problem like this: #include #include…
b.buchhold
  • 3,837
  • 2
  • 24
  • 33
7
votes
3 answers

Google Sparsehash uses realloc() on type which is not trivially copyable

Consider this simple program: #include #include int main() { google::dense_hash_map map; map["foo"] = 0; } Compiling with GCC 8.2 and -Wclass-memaccess (or -Wall) produces a…
John Zwinck
  • 239,568
  • 38
  • 324
  • 436
2
votes
1 answer

C++: using an iterator of dense_hash_set after erase(*it)

I have this C++ code file which is FOSS under the Expat licence. When running cppcheck on the code I get this error: [google_hash.cpp:137] -> [google_hash.cpp:141]: (error) Iterator 'it' used after element has been erased. The code in question is: …
Shlomi Fish
  • 4,380
  • 3
  • 23
  • 27
1
vote
0 answers

C++ Integer Trie implementation using a hash_map to reduce memory consumption

I have to implement a Trie of codes of a given fixed-length. Each code is a sequence of integers and considering that some patterns are usual, I decided to implement a Trie in order to store all the codes. I also need to iterate throught the codes…
Quentin Preguntino
  • 3
  • 4
1
vote
0 answers

Google sparse_hash_map insertion doen't work when reading chars from the input file

So, I'm noob in C++ and I'm trying to use sparse_hash_map but I can't figure out why insertion into the map does not work when reading the lines from the file, but it works when I hardcode strings. #include #include #include…
Boy
  • 1,182
  • 2
  • 11
  • 28
1
vote
0 answers

Google sparse hash slow for map of int to vector

I have a map of uint64_t to vector. The map takes an unusually long time (~70s) to build compared to unordered_map(~4s) for a string input of 4MB in size. Similarly, 120s vs 2400s for a string input of size ~150MB. Unordered_map is generally faster…
user1995120
  • 167
  • 1
  • 9
1
vote
1 answer

How does google's sparse hash table handle collisions?

How does google's sparse hash table handle collisions? i.e. when 2 elements map to the same bucket, how does it decide where to put the new (colliding) element? I'm reading What is the main implementation idea behind sparse hash table? but that…
dhruvbird
  • 6,061
  • 6
  • 34
  • 39
0
votes
1 answer

Errors on compilation

I tried to complile this project: https://github.com/ccshiro/corecraft I am use Ubuntu 16.04, i have installed: gcc 4.9, 5.0, 6.0; g++ 4.9, 5.0; clang; cmake3; and libsparsehash-dev . I got this error: [ 96%] Linking CXX executable…
Amaroc
  • 179
  • 1
  • 2
  • 9
0
votes
1 answer

Memory leak in Google sparse_hash_map

This week I've been trying to spot an unusual memory behavior: when I run my code with one single thread I have a specific memory footprint, but if I run it with multiple threads then the memory footprint increases a lot with no apparent reason. I…
xmas79
  • 5,060
  • 2
  • 14
  • 35
0
votes
1 answer

Is there any way to serialize the type of sparse_hash_map to file?

I tried to code to serialize the type of sparse_hash_map to file, but somehow it just didn't work, compelling it tells me this error message: /usr/local/include/sparsehash/sparsetable:1763:13: error: no matching function for call to object of type…
beanmoon
  • 59
  • 2
  • 8