Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20

Overview

➵ robin_hood unordered map & set Release GitHub license

Travis CI Build Status Appveyor Build Status Codacy Badge Total alerts Language grade: C/C++ Coverage Status

robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map / std::unordered_set which is both faster and more memory efficient for real-world use cases.

Installation & Usage

Direct Inclusion

  1. Add robin_hood.h to your C++ project.
  2. Use robin_hood::unordered_map instead of std::unordered_map
  3. Use robin_hood::unordered_set instead of std::unordered_set

Conan, the C/C++ Package Manager

  1. Setup your CMakeLists.txt (see Conan documentation on how to use MSBuild, Meson and others) like this:
    project(myproject CXX)
    
    add_executable(${PROJECT_NAME} main.cpp)
    
    include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake) # Include Conan-generated file
    conan_basic_setup(TARGETS) # Introduce Conan-generated targets
    
    target_link_libraries(${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)
  2. Create conanfile.txt in your source dir (don't forget to update the version)
    [requires]
    robin-hood-hashing/3.10.0
    
    [generators]
    cmake
  3. Install and run Conan, then build your project as always:
    pip install conan
    mkdir build
    cd build
    conan install ../ --build=missing
    cmake ../
    cmake --build .
    The robin-hood-hashing package in Conan is kept up to date by Conan contributors. If the version is out of date, please create an issue or pull request on the conan-center-index repository.

Benchmarks

Please see extensive benchmarks at Hashmaps Benchmarks. In short: robin_hood is always among the fastest maps and uses far less memory than std::unordered_map.

Design Choices

  • Two memory layouts. Data is either stored in a flat array, or with node indirection. Access for unordered_flat_map is extremely fast due to no indirection, but references to elements are not stable. It also causes allocation spikes when the map resizes, and will need plenty of memory for large objects. Node based map has stable references & pointers (NOT iterators! Similar to std::unordered_map) and uses const Key in the pair. It is a bit slower due to indirection. The choice is yours; you can either use robin_hood::unordered_flat_map or robin_hood::unordered_node_map directly. If you use robin_hood::unordered_map It tries to choose the layout that seems appropriate for your data.

  • Custom allocator. Node based representation has a custom bulk allocator that tries to make few memory allocations. All allocated memory is reused, so there won't be any allocation spikes. It's very fast as well.

  • Optimized hash. robin_hood::hash has custom implementations for integer types and for std::string that are very fast and falls back to std::hash for everything else.

  • Depends on good Hashing. For a really bad hash the performance will not only degrade like in std::unordered_map, the map will simply fail with an std::overflow_error. In practice, when using the standard robin_hood::hash, I have never seen this happening.

License

Licensed under the MIT License. See the LICENSE file for details.

by martinus

Issues
  • Insert fails with std::overflow_error again

    Insert fails with std::overflow_error again

    Hello.

    I have encountered std::overflow_error again.

    I am using robin hood version 3.10.0.

    This time I cannot create test case. I hope you can give me guidelines to find source of problem. I am working with robin_hood::unordered_flat_set<int32_t>. My application is working with 200 containers and 10 million elements in total, so I cannot find good way to create test example. It takes about 5 minutes of number crunching before application crashes while trying to insert that specific integer into that specific container.

    My application is basically doing this:

    • Create 200 containers.
    • Do work with all containers (container::insert, container::erase, container::clear). This work takes about 5 minutes.
    • At some moment, application has to process some problematic container.
    • Problematic container contains some elements.
    • I know what are new elements that must be inserted into problematic container.
    • Problematic container is cleared before insertion.
    • New elements are inserted into problematic container one-by-one. Insertion fails with std::overflow_error after some number.

    Exception is not thrown if I recreate standalone test case with same elements.

    Thanks.

    opened by slavenf 26
  • Support for Unique hash map?

    Support for Unique hash map?

    As discussed on https://github.com/CGAL/cgal/issues/4049 I am investigating using robin_hood::unordered_map for a unique hash map. A Unique hash map is a specialization on insertion only and unique hash values allow for a more time and space-efficient implementation. In the case of the implementation in CGAL the memory addresses of Handle objects are used for key-hashes and therefore by their very nature there cannot be duplicates/collisions.

    The CGAL implementation suffers from poor construction speed due to the default hardcoded table size of 512, and this is what I hope to improve by using robin_hood::unordered_map. However the insert speed of the CGAL::Unique_hash_map does seem to outperform by a factor of 0.2, as can be seen in my benchmark project https://github.com/GilesBathgate/hashmap-benchmarks

    What I'd like to establish is whether improvements can be made to either CGAL::Unique_hash_map that would facilitate faster construction, or whether robin_hood::* can be improved with the techniques used in the CGAL implementation.

    I realise that the main purpose of robin hood hashing is to handle the case when there are duplicate keys, so perhaps its not the best candidate. Are there any other faster hash map implementations that can be used for a unique hash map that would be more suitable?

    opened by GilesBathgate 12
  • robin_hood::map overflow

    robin_hood::map overflow

    Dear developer,

    I am using robin hood map (3.11.2) under MinGW. I got overflow error when insert some number as below log.

    ... Add 20686628 Add 20790466 Add 20950897 Add 20938052 Add 20481416 terminate called after throwing an instance of 'std::overflow_error' what(): robin_hood::map overflow

    I have attach reproduce file. Please check it. :)

    Thank you.

    test.zip

    bug 
    opened by ihmin 10
  • Consider porting to C++11 / C++03

    Consider porting to C++11 / C++03

    A large number of development environments still do not have C++14 support, especially in many embedded environments that only support C++03.

    Can you consider porting this powerful and efficient container to these older versions?

    Thanks :-)

    enhancement 
    opened by asbai 7
  • support remove/erase idiom

    support remove/erase idiom

    I noticed when applying the remove/erase idiom that the following method is not implemented:

    iterator erase ( const_iterator first, const_iterator last );

    Reference: https://en.cppreference.com/w/cpp/container/unordered_map/erase Example: cache.erase( std::remove_if( cache.begin(), cache.end(), [&] ( const pair<int,int>& i ) { return i.second == 1 ); } ), cache.end() );

    wontfix 
    opened by jcageman 7
  • Fix CRC32 support on Windows ARM64 and use runtime detection

    Fix CRC32 support on Windows ARM64 and use runtime detection

    __cpuid isn't present on ARM64 builds in Windows, and CRC32 is always present for ARM64 processors that Windows 10 supports (making runtime detection unnecessary).

    Also, remove the hardware support detection at compile time. You've already added runtime detection (the more flexible method), so use that.

    opened by wyattoday 6
  • Fast CRC32 based hash for hash_bytes and hash_int

    Fast CRC32 based hash for hash_bytes and hash_int

    • [x] CRC with runtime dispatch
    • [x] Use _mm_crc32_u64
    • [x] Don't use upper bits of the hash, only use lower bits. Then a single crc command would be enough
    • [ ] Implement optimized hash_bytes that makes use of CRC32 instruction
    performance 
    opened by martinus 6
  • Not using intrinsics

    Not using intrinsics

    What was the reason for reverting https://github.com/martinus/robin-hood-hashing/commit/f45a309af7d08cb98fc08dc7903ac9a7091db6d5 ? Any reliability concerns or just performance?

    I'm asking because, on certain contexts, including x86intrin.h on Mingw-w64 triggers a bug on g++.

    bug 
    opened by oscarfv 6
  • Crashing with overflow_error

    Crashing with overflow_error

    Hello,

    I am currently trying to integrate robin hood hashing into my project. As mentioned on your github, I simply included the robin_hood.h and used robin_hood::unordered_map instead of std::unordered_map.

    However, upon start, my program crashes and reports the following error:

    terminate called after throwing an instance of 'std::overflow_error' what(): robin_hood::map overflow Command terminated by signal 6

    Do you have any idea what could cause this?

    Thanks!

    Cheers, Pierre

    opened by morispi 6
  • Please add C++ 17 node API to node based map

    Please add C++ 17 node API to node based map

    For node-based maps, these functions can enable writing much more efficient code:

    https://en.cppreference.com/w/cpp/container/unordered_map/extract

    Indeed, I am not using your map in a number of places precisely due to me using this node ptr API.

    enhancement 
    opened by ned14 6
  • it = map.erase(it) potentially passes object twice

    it = map.erase(it) potentially passes object twice

    It seems @jcageman has stumbled uppon an issue that probably all robin-hood map with backward shift deletion have (see #18). Here is a simple reproducer

    Insert two elements, where both hash to the last bucket of the map. One entry will be the last one of the map, the other one will wrap around and use the first bucket.

    robin_hood::unordered_node_map<int, int, DummyHash> map;
    map[1024] = 1;
    map[2048] = 2;
    
    it = map.begin(); // it points to 2048, the first element which has wrapped around
    ++it;  // it points to the last element, 1024 which is in its original bucket
    it = map.erase(it); // backward shift deletion removes 1024 and wraps back 2048, so it now (again!) points to 2048 and NOT end
    it = map.erase(it); // finally we are at the end.
    

    Also see https://github.com/Tessil/robin-map/issues/20

    bug 
    opened by martinus 6
  • robin_hoodConfig.cmake missing

    robin_hoodConfig.cmake missing

    I'm trying to make Vulkan Validation layers and the make required robin hood but after using conan to install it and use it, I was expecting there to be a robin_hoodConfig.cmake or robin_hood-config.cmake. Everything works except the robin hood.

    I'm using windows 10, Vulkan 1.3.211.0, cmake 3.10.2

    command to make the validation layers:

    cmake -A x64 -DVULKAN_HEADERS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DGLSLANG_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DSPIRV_HEADERS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DSPIRV_TOOLS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DROBIN_HOOD_HASHING_INSTALL_DIR=C:\robin-hood-hashing-master ..

    output from command:

    -- Selecting Windows SDK version 10.0.22000.0 to target Windows 10.0.19042.


    • NOTE: Not adding target to run update_deps.py automatically. *

    CMake Error at CMakeLists.txt:254 (find_package): Could not find a package configuration file provided by "robin_hood" with any of the following names:

    robin_hoodConfig.cmake
    robin_hood-config.cmake
    

    Add the installation prefix of "robin_hood" to CMAKE_PREFIX_PATH or set "robin_hood_DIR" to a directory containing one of the above files. If "robin_hood" provides a separate development package or SDK, be sure it has been installed.

    -- Configuring incomplete, errors occurred! See also "C:/Vulkan-ValidationLayers-master/build/CMakeFiles/CMakeOutput.log".

    opened by jvonachen 0
  • Idea for robin-hood-hashing V2

    Idea for robin-hood-hashing V2

    • Performance is important but not everything

    • Use an std::vector<std::pair<Key, Value>> (maybe customizable) for the content that is always 100% compact. iteration is perfectly fast.

    • Use an indexing structure into that vector, that cannot overflow, e.g. like so:

      • 3 byte offset from original bucket => 2^24-1 = 16777215 collisions possible, should be plenty
      • 1 byte hash
      • 4 byte index into std::vector
    • => limitations are: no more than 16M collisions (so no overflow check necessary?)

    • 4 byte index, so no more than 4 billion elements are allowed. Should be enough for most use cases.

      • 32bit hash would be enough for indexing. Convert mumx to 32bit would work
      • We could use non-power-of-two-hashmap sizes. Given a well distributed 32bit hash, use idx = ((uint64_t)hash * (uint64_t)mapsize) >> 32
    • 1 byte hash: only every 256th key needs to be checked, that's good enough

    • ordering like robin-hood-hash, we we only need a single < comparison

    • how to deal with capacity() changes / rehash? (resize to capacity + 1, then resize to the new capacity(). This sucks.)

    opened by martinus 1
  • robin_hood.h: Change hash val shifts for `info` and `idx` generation

    robin_hood.h: Change hash val shifts for `info` and `idx` generation

    Instead of generating the info hash bits with a mask + shift, we can just use an unsigned shift from the end as that will bring in zeros.

    With that change the idx hash bits can start from the begining so we no longer need to shift out the info hash bits.

    Saves 2x instructions. Only ALU but this function is in the critical path.

    There does not appear to be any issue with false hits changing the tag bits used.

    False Tag Match Rates:

                      :   New,   Cur
    

    Insert Seq Ints: 2^10 : 2.539, 2.832 2^12 : 3.076, 3.003 2^14 : 2.960, 3.497 2^16 : 4.048, 4.306 2^18 : 4.543, 4.732 2^20 : 5.182, 5.553 2^22 : 5.579, 5.557 2^24 : 6.237, 6.017 2^26 : 6.599, 6.432

    Insert Rand Ints (seed = 0): 2^10 : 2.637, 4.199 2^12 : 2.979, 3.613 2^14 : 3.662, 3.955 2^16 : 4.309, 4.849 2^18 : 4.626, 4.564 2^20 : 4.849, 5.044 2^22 : 6.050, 5.279 2^24 : 5.664, 6.350 2^26 : 6.640, 6.771

    Insert Strings: All Words(0) : 4.974, 5.231 10k Words(1) : 3.550, 4.000 URLS(2) : 5.548, 5.683 URLS(2) w/ "http://" : 5.466, 5.831 URLS(2) w/ "https://" : 5.569, 5.761

    opened by goldsteinn 0
  • Memory blow up for certain payloads when using robin hood unordered node map

    Memory blow up for certain payloads when using robin hood unordered node map

    Hi

    I encountered a memory spike when using robin hood unordered node map with certain payloads. A link to the compiler explorer snippet is as follows Compiler-Explorer-link (I occasionally get a compiler returned -1 error from compiler explorer . I suspect its because of the number of lines of code. If this happens on your side , you can follow the second link where I removed the robin hood comments at the start of the file to get it working ) Here's a second link in case the first doesn't work Compiler-Explorer-Second-Link

    Essentially when I run the following piece of code

    int main()
    {
        struct Value
        {
            int arr[20];
        };
        using Container = robin_hood::unordered_map<int , Value>;
        robin_hood::unordered_map<int , Container> containers;
        unsigned numMapElements = 1'000;
        for(unsigned k =0 ; k < 8 ; ++k)
        {
            printMemory("Memory at the start of iteration " + std::to_string(k));
            for(unsigned i =0 ; i < numMapElements ; ++i)
            {
                Container tmp;
                containers[i] = tmp;
                for(unsigned j =0 ; j < 50 ; ++j)
                {
                    containers[i].emplace(j , Value());
                }
            }
            printMemory("Memory at the end of iteration " + std::to_string(k));
        }
        return 0 ;
    }
    

    I notice that the memory usage is around 11 MB for the first iteration and 170 MB in the next iteration. This issue disappears when I change the Container type to robin_hood::unordered_flat_map or std::unordered_map. This behavior is quite unexpected and I suspect there is some memory issue in the robin_hood::unordered_node_map.

    Additionally this only happens happens when using the copy assignment operator on container. If I change the lines in the inner most loop to the following , the issue disappears

    
    Container tmp;
    containers[i] = std::move(tmp);
    
    

    I have used the following functions to print memory usage

    namespace{
        void parseMemoryValue(const char* buf , const char* prefix , unsigned int& val)
        {
            const std::size_t prefixLen = strlen(prefix);
            if(strncmp(buf , prefix , prefixLen) == 0 )
            {
                val = static_cast<unsigned>(atoi(buf + prefixLen));
            }
        }
        int getMemory(unsigned int& currentRealMem, 
                      unsigned int& peakRealMemory ,
                      unsigned int& currentVirtualMemory, 
                      unsigned int& peakVirtualMemory)
        {
            static constexpr int bufferSize = 1024;
            char buf[bufferSize];
            std::ifstream stream;
            stream.open("/proc/self/status");
            if(!stream.is_open())
                return -1;
            while(!stream.getline(buf,bufferSize).eof())
            {
                const char* pos = strstr(buf , "Vm");
                if(pos == nullptr)
                    continue;
                pos+=2;
                parseMemoryValue(pos , "RSS:" , currentRealMem);
                parseMemoryValue(pos , "HWM:" , peakRealMemory);
                parseMemoryValue(pos , "Size:" , currentVirtualMemory);
                parseMemoryValue(pos , "Peak:" , peakVirtualMemory);
            }
            stream.close();
            return 0 ;
    
        }
        void printMemory(const std::string& title)
        {
            unsigned currentReal = 0 ;
            unsigned realPeak = 0 ;
            unsigned currentVirtual = 0 ;
            unsigned virtualPeak = 0 ;
            if(getMemory(currentReal , realPeak , currentVirtual , virtualPeak))
            {
                return ;
            }
            std::cout<<"Printing "<<title << std::endl;
            std::cout<<std::endl;
            std::cout<<"Current Real " <<currentReal / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Peak Real "<<realPeak / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Current Virual "<<currentVirtual / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Peak Virtual "<<virtualPeak / 1.0e3 << " MB"<<std::endl;
            std::cout<<std::endl;
        }
    }
    
    

    Please let me know if you have any idea why this happens.

    Thanks

    opened by abdullah578 0
  • making unordered_map automatically choose between unordered_node_map and unordered_flat_map is error-prone

    making unordered_map automatically choose between unordered_node_map and unordered_flat_map is error-prone

    Hi!

    First, thanks for the amazing work!

    I understand the motivation, but I think that having unordered_map try to automatically pick between the node and flat implementations is error prone:

    https://github.com/martinus/robin-hood-hashing/blob/9145f963d80d6a02f0f96a47758050a89184a3ed/src/include/robin_hood.h#L2519

    template <typename Key, typename T, typename Hash = hash<Key>,
              typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
    using unordered_map =
        detail::Table<sizeof(robin_hood::pair<Key, T>) <= sizeof(size_t) * 6 &&
                          std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
                          std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
                      MaxLoadFactor100, Key, T, Hash, KeyEqual>;
    

    The problem is that both implementations have different performance characteristics, and more importantly different iterator/reference invalidation semantics.

    For example AFAICT code like this:

    m["a"] = m["b"];
    

    is safe when inserting "a" into m causes a resizing with the node-based implementation, but not with the flat one, resulting in UB.

    And more generally, code which works fine with the node-based one might break subtly with the flat one.

    It can be quite confusing since subtle changes to the key or value types - which can occur for example when compiling with a different compiler/libraries - can cause a change in the underlying implementation used.

    opened by cf-natali 0
Releases(3.11.5)
  • 3.11.5(Jan 14, 2022)

    Direct download: robin_hood.h

    • #141: Use malloc + memset instead of calloc, which can be a bit faster, especially when the map gets large. Thanks @zhanglistar!
    • #138: The return type of functions that use hints should be consistent with std. Thanks @acd1034!
    Source code(tar.gz)
    Source code(zip)
  • 3.11.4(Dec 10, 2021)

  • 3.11.3(Jul 12, 2021)

  • 3.11.2(May 16, 2021)

  • 3.11.1(Mar 25, 2021)

    Direct download: robin_hood.h

    • Fix compiling with MSVC 2015 #118, thanks @jeremyg-lunarg!
    • Support insert with initializer list, found by @xuanqing94
    • Updated copyright to 2021
    • overflow fix: rehash with different hash instead (#121). This uses a pretty nice method to get rid of potential overflow problems, by rehashing with a slightly modified hash. Thanks for @slavenf for making the problem reproducible!
    Source code(tar.gz)
    Source code(zip)
  • 3.10.0(Mar 14, 2021)

    Direct download: robin_hood.h

    • new API compact(): if possible reallocates the map to a smaller one.
    • Improve CMake integration in #105, thanks @Ryan-rsm-McKenzie!
    • Switch to murmurhash3 in hash_int (it's not slower, but much higher quality hash)
    • try_emplace and insert_or_assign now use a single lookup instead of two, in #116. Thanks @GilesBathgate for the proof of concept!
    Source code(tar.gz)
    Source code(zip)
  • 3.9.1(Nov 13, 2020)

  • 3.9.0(Oct 25, 2020)

    Direct download: robin_hood.h

    • README updated with conan
    • Travis now builds on OSX, ARM, S390 too.
    • better intrinsics handling, can now be manually disabled with #define ROBIN_HOOD_DISABLE_INTRINSICS
    • Support MSVC's wchar_t
    • [[noreturn]] doThrow
    • use std::free and std::malloc
    • fixed explicit ctor warning
    Source code(tar.gz)
    Source code(zip)
  • 3.8.0(Jul 18, 2020)

    Direct download: robin_hood.h

    • Add member functions from C++17 #79
    • Fix is_transparent typedef detection #78
    • Add Conan package manager usage example #81
    • Support hash for smart pointers, string views, and basic_string
    • Updated hash (again...) to not use CRC. It's still not optimal :-(

    Thanks @k0zmo, @Talkless for your contributions!

    Source code(tar.gz)
    Source code(zip)
  • 3.7.0(Jun 25, 2020)

    Direct download: robin_hood.h

    • Improved iteration speed
    • Updated with new hash algorithm
    • C++17 fix for VS2019
    • Heterogeneous lookup support (#72)
    • Minor bug & compiler warning fixes

    Thanks @wolfpld, @gergondet, @wyattoday for your contributions!

    Source code(tar.gz)
    Source code(zip)
  • 3.6.0(Mar 14, 2020)

  • 3.5.2(Feb 29, 2020)

  • 3.5.1(Feb 18, 2020)

  • 3.5.0(Jan 25, 2020)

  • 3.4.4(Jan 18, 2020)

  • 3.4.3(Nov 10, 2019)

    Direct download: robin_hood.h

    • Fixed long standing iteration & deletion bug #42 - Now there are no known bugs left!
    • Fixed -Werror=free-nonheap-object problem with g++-7
    • Cmake interface library target now working #52
    • update LINT's
    • updated doctest to 2.3.5
    Source code(tar.gz)
    Source code(zip)
  • 3.4.1(Oct 23, 2019)

  • 3.4.0(Aug 1, 2019)

    Direct download: robin_hood.h

    • Added lots of noexcept
    • Code now works with -fno-exceptions, instead of throw I simply call abort();.
    • More stringent clang-tidy checks
    • nodiscard for C++17
    • improved iterator consistency
    • Added some tests for better code coverage
    Source code(tar.gz)
    Source code(zip)
  • 3.3.2(Jun 26, 2019)

  • 3.3.1(Jun 26, 2019)

  • 3.3.0(Jun 23, 2019)

  • 3.2.15(Jun 6, 2019)

    Direct download: robin_hood.h

    This bugfix release contains a critical fix: assigning to moved map was broken. Please upgrade!

    • assign to moved map fixed
    • swap member fixed
    • Thanks @wyattoday for cleanup and ARM64 fixes!
    Source code(tar.gz)
    Source code(zip)
  • 3.2.14(May 31, 2019)

  • 3.2.13(May 31, 2019)

  • 3.2.7(May 3, 2019)

    Important robin_hood.h stability fixes and improvements:

    • fix include for old clang on darwin build
    • no more static object required: got rid of the static dummybyte, reusing mMask when it's still empty.
    • Per the standard, out-of-bounds pointer were undefined behavior. Now no out-of-bounds pointers are used any more.
    • fixed a count() and .at() bug for empty maps
    • fixed move of empty map
    • Much more stringent compile warnings, with fixes: loads of cast warnings, __int128, fallthrough
    • visual studio compile fix

    Lots of infrastructure improvements:

    • Complete rewrite of all unit tests
    • switched from catch2 to doctest: much faster builds
    • cmake all the things!
    Source code(tar.gz)
    Source code(zip)
  • 3.2.3(Apr 23, 2019)

    This is a bugfix release concering the overflow handling

    • Now 127 objects an be hashed to the same bucket before overflowing.
    • Make sure the map stays in consistent state when overflow exception is thrown
    Source code(tar.gz)
    Source code(zip)
  • 3.2.0(Feb 7, 2019)

  • 3.1.0(Feb 7, 2019)

  • 3.0.1(Feb 6, 2019)

  • 3.0.0(Jan 31, 2019)

    3.0.0 because of incompatible API Changes. Renamed flat_map into unordered_flat_map and node_map into unordered_node_map to prevent confusion with other flat_map implementations that use a sorted array.

    value_type for node now uses const Key.

    Source code(tar.gz)
    Source code(zip)
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Thibaut Goetghebuer-Planchon 551 Jun 17, 2022
A repository I'm using to learn hashing with GLib.

GLib Tests Description A repository I'm using to store my progress while learning GNOME's GLib library. Specifically hashing via ghash. Test Files GLi

Christian Deacon 5 May 31, 2022
A fast and efficient non-iterating hashmap library

libhash: a fast and efficient non-iterating hashmap library Libhash is a fast and efficient non-iterating hashmap library Usage Usage is easy and simp

Oğuzhan Eroğlu 5 May 29, 2022
C++ library to create dynamic structures in plain memory of shared-memory segments

Ищи описание на хабре @mrlolthe1st. #define _CRT_SECURE_NO_WARNINGS #include "shared_structures.h" #include <iostream> #include <fstream> #include <ca

Александр Новожилов 4 Mar 30, 2022
A family of header-only, very fast and memory-friendly hashmap and btree containers.

The Parallel Hashmap Overview This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map

Gregory Popovitch 1.5k Jun 27, 2022
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design

Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.

DSC-Banasthali 53 Jun 12, 2022
A simple and efficient c++ KDTree implementation.

A simple and efficient c++ KD-Tree implementation. This code was written when I was learning c++11.

JoeyforJoy 4 May 11, 2022
This is a curve topology verification tool based on Fast Linking Numbers for Topology Verification of Loopy Structures.

Fast Linking Numbers This tool, called verifycurves, takes input models that consist of closed-loop curves, and outputs a topology certificate as a .t

Ante Qu 22 Jan 26, 2022
Cross-platform process memory inspector

Catsight Cross-platform process memory viewer inspired by x64dbg. Features Cross-platform (currently runs on Linux and Windows). Attach to any process

Melissa 142 Jun 15, 2022
C++ DataFrame for statistical, Financial, and ML analysis -- in modern C++ using native types, continuous memory storage, and no pointers are involved

C++ DataFrame for statistical, Financial, and ML analysis -- in modern C++ using native types, continuous memory storage, and no pointers are involved

Hossein Moein 1.5k Jun 21, 2022
A GREAT program to fuck your memory or swap

Let everyone enjoy the fun of fucking -- Chi_Tang FuckMemory This is a GREAT program to fuck your memory or Swap Installation Dependencies make g++ Li

FuckComputer 9 Mar 3, 2022
HashTableBenchmark - A simple cross-platform speed & memory-efficiency benchmark for the most common hash-table implementations in the C++ world

Hash-Tables Benchmarks This repository contains a bunch of extendable benchmarks mostly for following containers: std:unordered_map from STL. google::

Unum 7 Jun 15, 2022
A fast hash map/hash table (whatever you want to call it) for the C programming language.

C HashMap A fast hash map/hash table (whatever you want to call it) for the C programming language. It can associate a key with a pointer or integer v

Mashpoe 63 May 28, 2022
Simple C++ code to benchmark fast division algorithms

fast_division Simple C++ code to benchmark fast division algorithms relying on constant divisors. The code is a companion to the paper Integer Divisio

Daniel Lemire 35 Apr 19, 2022
This project Orchid-Fst implements a fast text string dictionary search data structure: Finite state transducer (short for FST) in c++ language.This FST C++ open source project has much significant advantages.

Orchid-Fst 1. Project Overview This project Orchid-Fst implements a fast text string dictionary search data structure: Finite state transducer , which

Bin Ding 8 Jan 5, 2022
Another neofetch-like utility but this time it's fast.

SystemFetch Another neofetch-like utility but this time it's fast. Example Speed Here is a table of the time it took to execute all of these programs,

YSU 10 Jul 22, 2021
merge two sorted lists fast

Py Merge Merge sorted list faster than using list.sort or heapq.merge. import merge # create some sorted lists a = list(range(-100, 1700)) b = list(r

Earthly 10 Nov 21, 2021
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 6.9k Jun 27, 2022