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
Issues
  • 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
  • crash on reserve(1)

    crash on reserve(1)

    If preallocation via reserve() requests only 1 or 2 elements, there's either a crash — or, in debug builds, an assert failure.

    opened by kilobyte 12
  • 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
  • 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
  • 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
  • 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
  • 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
  • Allocator without empty constructor?

    Allocator without empty constructor?

    Colony appears to assume/expect allocators with empty constructors, and will lapse to using empty-constructed allocators even when passing in an allocator constructed with arguments. Am I misunderstanding Colony's relationship with allocators? Otherwise, is there any way this restriction/assumption could be relaxed and the passed allocator could be copied instead of reconstructed by type? Vectors, by comparison, will accept and properly use such an allocator.

    In particular, this seems to revolve around the element packaging (ebco_pair) for empty-base-class optimization. Perhaps due to size constraints?

    Thanks!

    opened by recatek 4
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 102 Jul 19, 2021
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 Jul 23, 2021
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 479 Jul 22, 2021
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 579 Jul 27, 2021
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 105 Jul 19, 2021
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 849 Jul 24, 2021
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 251 Jul 6, 2021
🏅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 528 Jul 14, 2021
Simple Useful Libraries: The C++17 header-only dynamic bitset

dynamic_bitset Simple Useful Libraries: The C++17 header-only dynamic bitset Requirements To use this dynamic bitset, you will need a C++17 compliant

Maxime Pinard 67 Jul 14, 2021
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
Prime Number Projects in C#/C++/Python

Primes | A Software Drag Race Source code to Dave's Garage video benchmarking the same prime number sieve in Python, C#, and C++. Community contributi

null 2 Jul 25, 2021