An unordered C++ data container providing fast iteration/insertion/erasure while maintaining pointer/iterator validity to non-erased elements regardless of insertions/erasures. Provides higher-performance than std:: library containers for high-modification scenarios with unordered data.

Overview
Comments
  • misaligned objects on 32 bit windows

    misaligned objects on 32 bit windows

    I am getting alignment issues with over-aligned types with 32 bit build on windows. I am using visual studio 2019 (16.7.2) with c++17 standard.

    Code to reproduce:

    #define _ENABLE_EXTENDED_ALIGNED_STORAGE
    //#define _DISABLE_EXTENDED_ALIGNED_STORAGE
    
    #include "plf_colony.h"
    
    struct alignas(16) A
    {
    	char dummy[96];
    };
    
    static_assert(sizeof(A) == 96, "sizeof");
    static_assert(alignof(A) == 16, "alignof");
    
    int main()
    {
    	plf::colony<A> c;
    
    	for (int i = 0; i < 100; i++)
    		c.emplace();
    
    	for (A &a : c)
    	{
    		if ((std::size_t(&a) % 16) != 0)
    			throw "misaligned";
    	}
    }
    

    It may be necessary to run it multiple times until it crashes.

    Thanks.

    opened by malytomas 33
  • clear() implementation

    clear() implementation

    I've been tempted to use colony instead std::vector because we use structs containing a boolean flag for tagging erased elements. My problem with colony so far is that memory is deallocated when calling clear(), which is not the case of std::vector. I was wondering if keeping the allocating memory when clear() is called is something you are considering, and forcing the deallocation upon shrink_to_fit

    opened by arnaudbrejeon 18
  • Moved out colony still copying moved out elements.

    Moved out colony still copying moved out elements.

    Hello !

    I have seen a problem when a colony is moved out and after this colony is copied : it copy the moved out elements.

    You can see the problem with this code :

    struct StructTest { StructTest() { } StructTest(const StructTest& Rhs) { std::cout << "Copied" << std::endl; } StructTest(StructTest&& Rhs) { std::cout << "Moved" << std::endl; }

    StructTest& operator=(const StructTest& Rhs) { std::cout << "copy assigned" << std::endl; }
    StructTest& operator=(StructTest&& Rhs) { std::cout << "move assigned" << std::endl; }
    ~StructTest() { std::cout << "destructed" << std::endl; }
    

    };

    int main() { plf::colony Colony1; Colony1.insert(StructTest());

    std::cout << "Now performing move construction" << std::endl;
    auto Colony2(std::move(Colony1));
    
    std::cout << "Now performing copy construction with moved out colony" << std::endl;
    auto Colony3(Colony1);
    
    std::cout << "End" << std::endl;
    
    int pause;
    std::cin >> pause;
    return 0;
    

    }

    The struct StructTest is copied during the last copy construction.

    opened by GuillaumeTz 14
  • Range-v3 fails to create a view out of colony of noncopyable objects

    Range-v3 fails to create a view out of colony of noncopyable objects

    I have this simple code:

    #include <plf_colony.h>
    #include <range/v3/view.hpp>
    
    struct Noncopyable
    {
      Noncopyable()                   = default;
      Noncopyable(const Noncopyable&) = delete;
      Noncopyable(Noncopyable&&)      = default;
    
      Noncopyable& operator=(const Noncopyable&)  = delete;
      Noncopyable& operator=(Noncopyable&&)       = default;
    };
    
    int main()
    {
      plf::colony<Noncopyable> foos;
    
      foos | ranges::views::all;
    }
    

    I compile it with GCC 9.2.1 g++ example.cpp -std=c++17 and I get the error:

    In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/c++allocator.h:33,
                     from /usr/include/c++/9/bits/allocator.h:46,
                     from /usr/include/c++/9/string:41,
                     from /usr/include/c++/9/stdexcept:39,
                     from /usr/include/c++/9/array:39,
                     from /usr/include/c++/9/tuple:39,
                     from /usr/include/c++/9/functional:54,
                     from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                     from /usr/include/c++/9/algorithm:71,
                     from /usr/local/include/plf_colony.h:209,
                     from example.cpp:1:
    /usr/include/c++/9/ext/new_allocator.h: In instantiation of ‘void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Noncopyable; _Args = {const Noncopyable&}; _Tp = Noncopyable]’:
    /usr/include/c++/9/bits/alloc_traits.h:482:2:   required from ‘static void std::allocator_traits<std::allocator<_Tp> >::construct(std::allocator_traits<std::allocator<_Tp> >::allocator_type&, _Up*, _Args&& ...) [with _Up = Noncopyable; _Args = {const Noncopyable&}; _Tp = Noncopyable; std::allocator_traits<std::allocator<_Tp> >::allocator_type = std::allocator<Noncopyable>]’
    /usr/local/include/plf_colony.h:1375:7:   required from ‘plf::colony<element_type, element_allocator_type, element_skipfield_type>::iterator plf::colony<element_type, element_allocator_type, element_skipfield_type>::insert(const element_type&) [with element_type = Noncopyable; element_allocator_type = std::allocator<Noncopyable>; element_skipfield_type = short unsigned int; plf::colony<element_type, element_allocator_type, element_skipfield_type>::iterator = plf::colony<Noncopyable>::colony_iterator<false>]’
    /usr/local/include/plf_colony.h:2143:4:   required from ‘void plf::colony<element_type, element_allocator_type, element_skipfield_type>::insert(typename plf::colony<element_type, element_allocator_type, element_skipfield_type>::plf_enable_if_c<(! std::numeric_limits<iterator_type>::is_integer), iterator_type>::type, iterator_type) [with iterator_type = plf::colony<Noncopyable>::colony_iterator<false>; element_type = Noncopyable; element_allocator_type = std::allocator<Noncopyable>; element_skipfield_type = short unsigned int; typename plf::colony<element_type, element_allocator_type, element_skipfield_type>::plf_enable_if_c<(! std::numeric_limits<iterator_type>::is_integer), iterator_type>::type = plf::colony<Noncopyable>::colony_iterator<false>]’
    /usr/local/include/plf_colony.h:1034:3:   required from ‘plf::colony<element_type, element_allocator_type, element_skipfield_type>::colony(const plf::colony<element_type, element_allocator_type, element_skipfield_type>&) [with element_type = Noncopyable; element_allocator_type = std::allocator<Noncopyable>; element_skipfield_type = short unsigned int]’
    /usr/include/range-v3/range/v3/view/all.hpp:44:43:   required from ‘static constexpr auto ranges::views::all_fn::from_range_(T&&, std::true_type, ranges::detail::ignore_t, ranges::detail::ignore_t) [with T = plf::colony<Noncopyable>&; std::true_type = std::integral_constant<bool, true>]’
    /usr/include/range-v3/range/v3/view/all.hpp:69:43:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
    /usr/include/range-v3/range/v3/functional/concepts.hpp:27:5:   required by substitution of ‘template<class C_> static constexpr decltype (((& C_::Requires_<all_fn, colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&>), true)) ranges::cpp_detail_::invocable_concept::Eval<ranges::views::all_fn, plf::colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&>::impl<C_>(int) [with C_ = ranges::cpp_detail_::invocable_concept]’
    /usr/include/range-v3/range/v3/functional/concepts.hpp:27:5:   required from ‘constexpr ranges::cpp_detail_::invocable_concept::Eval<Fun, Args>::operator bool() const [with Fun = ranges::views::all_fn; Args = {plf::colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&}]’
    /usr/include/range-v3/concepts/concepts.hpp:787:24:   required by substitution of ‘template<bool B> using bool_ = std::integral_constant<bool, __v> [with bool B = concepts::detail::and_<ranges::cpp_detail_::viewable_range_concept::Eval<plf::colony<Noncopyable>&>, ranges::cpp_detail_::invocable_concept::Eval<ranges::views::all_fn, plf::colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&> >{}.concepts::detail::and_<ranges::cpp_detail_::viewable_range_concept::Eval<plf::colony<Noncopyable>&>, ranges::cpp_detail_::invocable_concept::Eval<ranges::views::all_fn, plf::colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&> >::operator bool()]’
    /usr/include/range-v3/concepts/concepts.hpp:791:34:   required from ‘constexpr concepts::detail::and_<T, U>::operator bool() const [with T = concepts::detail::and_<ranges::cpp_detail_::viewable_range_concept::Eval<plf::colony<Noncopyable>&>, ranges::cpp_detail_::invocable_concept::Eval<ranges::views::all_fn, plf::colony<Noncopyable, std::allocator<Noncopyable>, short unsigned int>&> >; U = std::integral_constant<bool, true>]’
    /usr/include/range-v3/range/v3/view/view.hpp:88:13:   required by substitution of ‘template<class Rng, class ViewFn, class CPP_true_, typename std::enable_if<((viewable_range<Rng> && invocable<ViewFn, Rng>) && CPP_true_{}), int>::type <anonymous> > constexpr auto ranges::views::view_closure_base_ns::operator|(Rng&&, ranges::views::view_closure<ViewFn>) [with Rng = plf::colony<Noncopyable>&; ViewFn = ranges::views::all_fn; CPP_true_ = std::integral_constant<bool, true>; typename std::enable_if<((viewable_range<Rng> && invocable<ViewFn, Rng>) && CPP_true_{}), int>::type <anonymous> = 0]’
    example.cpp:18:25:   required from here
    /usr/include/c++/9/ext/new_allocator.h:145:20: error: use of deleted function ‘Noncopyable::Noncopyable(const Noncopyable&)’
      145 |  noexcept(noexcept(::new((void *)__p)
          |                    ^~~~~~~~~~~~~~~~~~
      146 |        _Up(std::forward<_Args>(__args)...)))
          |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    example.cpp:7:3: note: declared here
        7 |   Noncopyable(const Noncopyable&) = delete;
          |   ^~~~~~~~~~~
    

    The same code compiles just fine with std::vector (and other standard containers) in the place of plf::colony. Any insight would be appreciated.

    opened by 60rntogo 10
  • Update conan link in homepage

    Update conan link in homepage

    The conan package mentioned in the homepage is very old and not part of the official public repository of conan (conancenter).

    Actually, a conan recipe of plf_colony is available in conancenter: https://conan.io/center/plf_colony

    You should advice to use this one since it has far more chance to be kept uptodate.

    Moreover, it would be nice to publish official releases on github as well, so that package maintainers can be quickly notified, and therefore it gives you more chance to see your library properly maintained in package managers.

    opened by SpaceIm 8
  • Erase is faster than Clear

    Erase is faster than Clear

    Seemingly contrary to STL containers, colony.clear() is slower than colony.erase(colony.begin(),colony.end()).

    Maybe I'm alone in being surprised that .clear() deallocates the memory, which seems to go against the purpose of the colony container.

    opened by Meerkov 7
  • get_iterator_from_pointer expects a non-const pointer

    get_iterator_from_pointer expects a non-const pointer

    As it is even documented get_iterator_from_pointer expects a non-const pointer forcing a const_cast in some cases.

    plf::colony<int> colony;
    const int* ptr = &*colony.insert(0);
    colony.get_iterator_from_pointer(const_cast<int*>(ptr));
                                     ^^^^^^^^^^^^^^^^
    

    However looking at the implementation (as expected) the pointed (object) data is not accessed therefore a const pointer should be sufficient.

    (Please, also consider another function overload for erase with a single pointer as argument which internally calls get_iterator_from_pointer just for convenience.)

    opened by VaderY 7
  • reserve() calls constructor of T (C++17)

    reserve() calls constructor of T (C++17)

    As per above, plf::colony::reserve ( ) calls constructor of T (I am using C++17).

    Why, I read about that T needs to be Copy-Constructable, but if it is to do a reserve, I'm a worried. The T's are never moved (re-allocated), in C++03 maybe?

    I've been wrapping plf::colony and in my T there are some std::atomic s, using proper move construction and propagation, these atomics have been no problem in the implementation of my class emplace/push/pop type of functionality, except bizarrely reserve().

    I've written most of what constitutes a lock-free stack (on top of plf::colony). I would like to build on top, a circular list, so concurrent insertions and removals are possible as all changes will be local, hence the need for the address of the first T to be allocated node.

    I would like to find the address of the first T that will be allocated, so I thought to reserve() and scour the raw data, to obtain the address of the first 'T' (logically it should be there somewhere, help welcome?), by-passing construction. If want my type to have erasable as requirement only, so doing a quick default emplace/erase, immediately would make my type have a default-constructable requirement, i.e. that's not acceptable.

    opened by degski 7
  • Modernize NULL -> nullptr?

    Modernize NULL -> nullptr?

    Is plf::colony used on in environments that don't have nullptr? Can all "NULL" references be replaced with "nullptr"? Or at least do like fmtlib and use version/feature testing to select nullptr on compilers that support it?

    I'm working on a prototype and turned all warnings and clang-tidy and cppcheck to full blast, and I keep getting quite a few of these:

    3 external/plf_colony/plf_colony.h|1302 col 23 warning| error: zero as null pointer constant [-Werror,-Wzero-as-null-pointer-constant]
    4 || if (next_group == NULL)
    5 || ^~~~
    6 || nullptr

    Thank you!

    opened by 0x8000-0000 7
  • Question about shrink_to_fit implementation

    Question about shrink_to_fit implementation

    Hi there,

    First, thanks for the library.

    I'm trying to use the plf::colony with move only elements and I stumbled upon compilation error when invoking shrink_to_fit and more precisely the consolidate function. As far as I understood the implementation it uses the copy constructor of container to shrink it and then move it back to *this. I understand that the reusing of the copy constructor simplifies the implementation here but want to ask would it be a problem the 'alive' entries to be moved instead of being copied?

    Regards, Pavel.

    opened by freak82 7
  • Request for tag/release

    Request for tag/release

    Hi! This library is being added to ConanCenter: https://github.com/conan-io/conan-center-index/pull/5985/

    It would be easier for us if you tag/release a version instead of using the string in the commit. Is it possible, would you consider to tag the existing latest commit as 6.25 version?

    Thanks!

    opened by jgsogo 6
🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of bil

Giorgio Vinciguerra 644 Nov 26, 2022
C++ associative containers

This directory contains several hash-map implementations, similar in API to SGI's hash_map class, but with different performance characteristics. spa

null 1.4k Nov 28, 2022
A c++ toolbox of locality-sensitive hashing (LSH), provides several popular LSH algorithms, also support python and matlab.

LSHBOX-0.9 A C++ Toolbox of Locality-Sensitive Hashing for Large Scale Image Retrieval, Also Support Python and MATLAB. Change Log 2015.07.04 A new LS

null 269 Nov 13, 2022
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 571 Nov 11, 2022
Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20

➵ robin_hood unordered map & set robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map

Martin Ankerl 1.3k Nov 28, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

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

Thibaut Goetghebuer-Planchon 853 Nov 26, 2022
A fast, memory efficient hash map for C++

I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit

Gregory Popovitch 1.1k Nov 22, 2022
Template Library of Tree Data Structures in C++17

Template Library of Tree Data Structures in C++17 Implementations AVL Tree Binary Search Tree BTree KD-Tree Splay Tree Trie Notes This project is for

George Fotopoulos 149 Feb 8, 2021
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

Martin Moene 125 Nov 26, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf_list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70% f

Matt Bentley 117 Nov 8, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf::list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70%

Matt Bentley 117 Nov 8, 2022
A C++ data container replicating std::stack functionality but with better performance than standard library containers in a stack context.

plf::stack A data container replicating std::stack functionality but with better performance than standard library containers in a stack context. C++9

Matt Bentley 47 Sep 11, 2022
Rajesh Kumar Sah 1 Nov 20, 2021
Fast C++ container combining the best features of std::vector and std::deque

veque The double-ended vector A very fast C++17 container combining the best features of std::vector and std::deque "In Most Cases, Prefer Using deque

null 102 Nov 26, 2022
Fast UI Draw is a library that provides a higher performance Canvas interface.

Fast UI Draw is a library that provides a higher performance Canvas interface. It is designed so that it always draws using a GPU.

Intel Corporation 594 Nov 24, 2022
Similar to C++ streams, but the stream elements are structured JSON data rather than characters.

JIOS : JSON Input Output Streams Similar to C++ streams, but the stream elements are structured JSON data rather than characters. Contents Features [P

Castedo Ellerman 3 Aug 16, 2019
A C++ data container replicating std::queue functionality but with better performance.

A data container replicating std::queue functionality but with better performance than standard library containers in a queue context. C++98/03/11/14/etc-compatible.

Matt Bentley 21 Aug 16, 2022
SIMULATeQCD is a multi-GPU Lattice QCD framework that makes it simple and easy for physicists to implement lattice QCD formulas while still providing the best possible performance.

SIMULATeQCD a SImple MUlti-GPU LATtice code for QCD calculations SIMULATeQCD is a multi-GPU Lattice QCD framework that makes it simple and easy for ph

null 10 Apr 23, 2022
Quick fix to iphone usb tethering with ios14 or higher for Linux kernel lower than 5.10.4

Quick fix to Linux Iphone USB tethering with IOS 14 or higher (Tested with ubuntu 18.04, kernel 5.4.0-65, if you fail in the build, please download yo

null 24 Sep 18, 2022