10 July 2012

GNU C++ hash_set vs STL std::set: my notebook

A set is a C++ container that stores unique elements. The C++ Standard Template library  (STL) defines a C++ template set<T> that is typically implemented as a binary search tree.

#include<set>

But the GNU C++ library also provides a (non-standard) hash-based set:

#include<ext/hash_set>

In the following code I've created some random #rs numbers and I print the time needed to insert/remove them from a (GNU/hash_set or STL ) set:

STL version

$ g++  -Wall -O3 testset.cpp
$ ./a.out 
Time: 109.27seconds.

GNU hash_set version

$  g++ -DWITH_HASHSET=1 -Wall -O3 testset.cpp
In file included from /usr/include/c++/4.6/ext/hash_set:61:0,
                 from jeter.cpp:7:
/usr/include/c++/4.6/backward/backward_warning.h:33:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed (...)
$ ./a.out 
Time: 49.69seconds.

That's it,


Pierre




at

1 comment:

  1. RobTuesday, 10 July, 2012

    g++ also now includes the (standard) unordered_set, from the header , that provides a tr1 (and c++11) compatible interface to a random-access unordered set. This should have the same (or very similar) performance characteristics to the hash set with the added benefit of being standard.

    ReplyDelete