C++ associative containers

What steps will reproduce the problem?

Fill table with entries--table full error at approx 2^31 entries.


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

sparsehash-1.8.1

Mac OS X 10.6


Please provide any additional information below.

All was well with the table occupying approx 96GB RAM when I hit the table full 
limit of approx 2^31 entries.  I'm curious whether there's any plan to lift 
this nominal 32-bit limit.  (Yes, it did occur to me that I could get around 
the limit by using multiple tables.)

Regardless, kudos to the developers, it's a real champ--I paired it with 
Murmurhash.

Original issue reported on code.google.com by [email protected] on 20 Sep 2010 at 11:05

Hey there, I have a question if it's possible to serializer/deserialize sparse_hash_map which consist of

sparse_hash_map<unsigned long long, std::vector<Structure>>

I tried to write my own serializer, but it seems it's not possible to serialize STL containers, did I miss something or simply I can't write any serializer for this map?

What steps will reproduce the problem?
1. Open solution in Visual C++ 2010
2. Try to compile

What is the expected output? What do you see instead?
I've expected some warnings, but not an error. 
1>  hashtable_test.cc
1>...\vc\include\utility(260): error C2166: l-value specifies const object

What version of the product are you using? On what operating system?
Visual Studio 2010 Ultimate / Windows Seven x64

Please provide any additional information below.

Original issue reported on code.google.com by wolfulus on 28 Sep 2010 at 6:58

Hello,

Running ./configure fails with "configure: error: cannot run C++ compiled programs." A bigger picture - I'm trying to compile ea-utils, which fails with the same error.

The detailed output of ./configure is:

checking whether make sets $(MAKE)... yes
checking whether the C++ compiler works... yes
checking for C++ compiler default output file name... a.out
checking for suffix of executables...
checking whether we are cross compiling... configure: error: in `/Users/mdozmorov/Documents/nobackup/ea-utils/clipper/sparsehash':
configure: error: cannot run C++ compiled programs.

And the full config.log is attached.

Thanks for your help, Mikhail config.log

AFAIK, include dir "google" is still available in 2.0.1 because of backward 
compatibility and new codes should use the new include dir "sparsehash".

However, this dir "google" is not correct as backward compatibility, because 
the old version 1.12 had include dir 'google/sparsehash', not just 'google'. 
So, yes, it is broken.

In my case, PCSX2 failed to build, because it didn't find include dir. Here is 
an open thread in PCSX2 forum (just in case you want to see other report): 
http://forums.pcsx2.net/Thread-ZZogl-ERROR-Need-GL-EXT-framebuffer-object-for-mu
ltiple-render-targets

I'm currently using Sparsehash version 2.0.1 on Arch Linux 64-bit(all system 
up-to-date)

Original issue reported on code.google.com by [email protected] on 14 Feb 2012 at 1:28

What steps will reproduce the problem?

#include "google/dense_hash_set"
#include "tr1/unordered_set"

int main()
{
//  typedef std::tr1::unordered_set<int> TSet;
  typedef google::dense_hash_set<int> TSet;
  TSet set;
  set.set_empty_key(-1);
  set.set_deleted_key(-2);
  const int size = 1000000;
  set.rehash(size);
  for (int i = 0; i < size; ++i) set.insert(i);
  for (int i = 0; i < size; ++i) { set.erase(i); set.insert(i); }
  return 0;
}

What is the expected output? What do you see instead?
time ./a.out ~ 3 sec (dense_set)
time ./a.out ~ 0.01 sec (unordered_set)

What version of the product are you using? On what operating system?
Google Hash 1.11 amd64
Linux DE3UNP-503726 2.6.32-26-generic #48-Ubuntu SMP Wed Nov 24 10:14:11 UTC 
2010 x86_64 GNU/Linux
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)
Intel Core 2 Duo 3 GHz
g++ -O3

Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 28 Jun 2011 at 5:39

God evening

I am trying to install sparsehash, /.configure runs OK, and so does make, but when I try make install there is a fatal error:

install: /usr/local/share/doc/sparsehash-2.0.2/AUTHORS: Permission denied make[2]: *** [install-dist_docDATA] Error 71 make[1]: *** [install-am] Error 2 make: *** [install] Error 2

Can someone help please?

The updated build in 0.9 produces an empty sparseconfig.h file, which
prevents use of any of the collections.

To reproduce:
1. Extract the 0.9 source.
2. Run configure in the source directory.
3. Run make in the source directory.
4. Examine src/google/sparsehash/sparseconfig.h.  It will be empty.

I suspect there is some problem with the awk command in the Makefile that
replaces the grep/fgrep commands in previous versions.  I have not
attempted to debug the awk command myself.

Replacing the awk command with the grep/fgrep pipe from the 0.8 package
(with a couple of path fixups) fixes the problem, and sparseconfig.h is
created correctly.

This bug happens both when building in place and when building in a
separate build directory.

Original issue reported on code.google.com by [email protected] on 10 Oct 2007 at 6:10

The default memory allocator used (libc_allocator_with_realloc) necessarily has some overhead, as the size of the block is not passed to free(). The memory usage claims are updated to take into account an overhead of up to 16 bytes per malloc'ed block.

Hello, I tried using sparse_hash_map to replace std::map in a big application, 
and I got many warnings during compilation. I isolated the problem to the "-W 
-Wall" compilation parameters and compiling google-sparsehash v1.7 with those 
parameters also issues the same warnings. 

They are huge, template related warnings so it's not meaningful to copy-paste 
them here, just try compiling with those flags. 

Unfortunately sparse_hash_map doesn't work for me as drop-in replacement to 
std::map, sometimes I get garbage when reading from specific places... I can't 
tell if it's related to these warnings but I'll look into the issue more and 
report back if it is so.

Original issue reported on code.google.com by [email protected] on 20 Jun 2010 at 1:57

What steps will reproduce the problem?
1. Compile on Mac OS X Maverick with XCode Command Line Tools March 2014


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

I was expected correct compilation

I have attached the log.

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

Latest SVN (116).
Mac OS X 10.9.2
Compiler: XCode Command Line Tools March 2014


Please provide any additional information below.

Original issue reported on code.google.com by [email protected] on 24 Mar 2014 at 5:52

Attachments:

• error.log

I am going to install sparsehash-2.0.4 into Mac OS 10.15.7. Setting of C++ is not so easy in my PC. $./configure CXX=“gcc" #worked, but I cannot make with the following commands. $ CXX="gcc" make $ CXX="g++" make $ CC="gcc" make and so on.

The error is like below.

(std::__1::basic_ostream<char, std::__1::char_traits >&, char const*, unsigned long) in template_util_unittest.o std::__1::ostreambuf_iterator<char, std::__1::char_traits > std::__1::__pad_and_output<char, std::__1::char_traits >(std::__1::ostreambuf_iterator<char, std::__1::char_traits >, char const*, char const*, char const*, std::__1::ios_base&, char) in template_util_unittest.o Dwarf Exception Unwind Info (__eh_frame) in template_util_unittest.o ld: symbol(s) not found for architecture x86_64 clang: error: linker command failed with exit code 1 (use -v to see invocation) make[1]: *** [template_util_unittest] Error 1 make: *** [all] Error 2

I assume this will be the problem of Mac, rather than the package, but any advices or suggestions will greatly help me. Thank you in advance.

Hello, I was trying to use sparsetable and come to this issue with indexed assignment:

google::sparsetable tab; tab.resize(10); tab[4] = 1; tab[0] = tab[4]; printf("%d %d\n", tab.test(0), (int) tab[0]);

the tab[0] reamins unasinged, sure I can do tab[0] = (int) tab[4]; and then everything is as I would expect.

What is the correct assignment behavior of tab[0] = tab[4] as in example? Isn't it a bug?

Thank you Pavel

Hello!

I compiled sparsehash 2.0.4 and tried running my pretty old tests which I think worked few years ago.

But now I can observe crashes in 100% of runs of my test code: https://gist.github.com/pavel-odintsov/d72513432faf208828a387792053b623

I just insert around 10m of keys and it crashes during process:

./traffic_structures_tests 
google:dense_hashmap without preallocation: 0.5 mega ops per second
Segmentation fault

Stacktrace:

google:dense_hashmap without preallocation: 0.2 mega ops per second

Program received signal SIGSEGV, Segmentation fault.
0x0000000000424aa0 in google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::dense_hashtable(google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > > const&, unsigned long) ()
(gdb) 

Full backtrace:

bt
#0  0x0000000000424aa0 in google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::dense_hashtable(google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > > const&, unsigned long)
    ()
#1  0x0000000000425435 in google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::resize_delta(unsigned long) ()
#2  0x0000000000420e19 in std::pair<unsigned int const, subnet_counter_t>& google::dense_hashtable<std::pair<unsigned int const, subnet_counter_t>, unsigned int, std::hash<unsigned int>, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SelectKey, google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::SetKey, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::find_or_insert<google::dense_hash_map<unsigned int, subnet_counter_t, std::hash<unsigned int>, eqint, google::libc_allocator_with_realloc<std::pair<unsigned int const, subnet_counter_t> > >::DefaultValue>(unsigned int const&) [clone .constprop.1] ()
#3  0x0000000000420f3a in packet_collector_thread_google_dense_hash_map_preallocated() ()
#4  0x00000000004208d5 in run_tests(std::function<void ()>) ()
#5  0x000000000041fe13 in main ()

Let me know if you need more details from me.

C++20 removed many deprecated std::allocator members, causing sparsehash to fail when it is built with -std=c++20. This implements most of the uses of the removed members in terms of std::allocator_traits.

There are no corresponding reference and const_reference members in std::allocator_traits, in which case used the actual value_type&/const value_type& instead.

Replace C NULL by C++11 nullptr

This allows building with -Werror,-Wzero-as-null-pointer-constant

Code tested and validated in our codebase (https://github.com/algolia)

This includes find, count, equal_range

The rationale is that HashFcn and EqualKey passed during type construction may be tuned to support more types compared by the fixed type key_type.

• HashFcn would typically implement additional size_t operator()(const T& key) const member(s)
• EqualKey would typically implement additional bool operator()(const T& other, const key_type& value) const member(s)

Code tested and validated in our codebase (https://github.com/algolia)