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.

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.

  • 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

  • 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.

  • 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.

  • 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.

  • 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.)

  • 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.

  • 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!

  • 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.

  • MSVC warning: usage of feature deprecated in C++17

    MSVC warning: usage of feature deprecated in C++17

    Not a blocking issue, just a heads-up about C++17 deprecated warning that might be important if you want plf-colony to work in future C++ versions:

    C:\tmp\build\plf-colony-5.20.0\plf_colony\upstream\plf_colony.h(4021): warning C4996: 'std::allocator<unsigned char>::pointer': warning STL4010: Various members of std::allocator are deprecated in C++17. Use std::allocator_traits instead of accessing these members directly. You can define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING or _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS to acknowledge that you have received this warning.
    C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.21.27702\include\xmemory0(889): note: see declaration of 'std::allocator<unsigned char>::pointer'
    C:\tmp\build\plf-colony-5.20.0\plf_colony\upstream\plf_colony.h(4020): note: while compiling class template member function 'plf::colony<small_struct_non_trivial,std::allocator<element_type>,unsigned short>::raw_memory_block_pointers::~raw_memory_block_pointers(void)'
            with
            [
                element_type=small_struct_non_trivial
            ]
    C:\tmp\build\plf-colony-5.20.0\plf_colony\upstream\plf_colony_test_suite.cpp(1797): note: see reference to function template instantiation 'plf::colony<small_struct_non_trivial,std::allocator<element_type>,unsigned short>::raw_memory_block_pointers::~raw_memory_block_pointers(void)' being compiled
            with
            [
                element_type=small_struct_non_trivial
            ]
    C:\tmp\build\plf-colony-5.20.0\plf_colony\upstream\plf_colony_test_suite.cpp(1143): note: see reference to class template instantiation 'plf::colony<small_struct_non_trivial,std::allocator<element_type>,unsigned short>::raw_memory_block_pointers' being compiled
            with
            [
                element_type=small_struct_non_trivial
            ]
    

    This happen with all the msvc versions starting with Visual Studio 15 (2017) Update 9 (15.9.3). For more details, see: https://queue.cppget.org/plf-colony/5.20.0/

    What solution do you prefer?

    • assume that plf-colony is C++17 only and remove the deprecation warnings (I'll do it in the package setup if you prefer this);
    • try to make it future-proof by using std::allocator_traits as suggested (I can try a patch but suspects it should be better handled by you).

    For course solution 1 is the simplest, I just want to be sure if it's ok with you.

  • compiling on msvc with /permissive- fails

    compiling on msvc with /permissive- fails

    Plf colony version 2018-07-07 (and priviously 2018-06-27) does not compile when using the msvc option /permissive-.

    > cl.exe /EHsc plf_colony.h /TP /std:c++17 /permissive-
    plf_colony.h
    plf_colony.h(2626): error C2760: syntax error: unexpected token 'identifier', expected ')'
    plf_colony.h(3819): note: see reference to class template instantiation 'plf::colony<element_type,element_allocator_type,element_skipfield_type>' being compiled
    
  • Adding functionality discussion

    Adding functionality discussion

    Hiya, the repo doesn't seem to have discussion so hopefully opening an issue isn't too offensive. If so, we can take the discussion elsewhere.

    I've found it useful to be able to add some functionality to colony that allows me to get extra information about where in the colony the data is stored.

    Specifically, I've added 3 things.

    1. a Groups() function to colony that returns a std::vector of group pointers.
        std::vector<colony::group*> groups() const {
            std::vector<colony::group*> _groups;
    
            for (group_pointer_type current_group = begin_iterator.group_pointer;
                 current_group != end_iterator.group_pointer;
                 current_group = current_group->next_group) {
                _groups.push_back(current_group);
            }
    
            _groups.push_back(end_iterator.group_pointer);
    
            return _groups;
        }
    
    1. and 3) Two functions to the colony iterator. group_ptr() and local_offset().

    group_ptr() returns a pointer to the current group that the element pointed to by the iterator is stored in.

    local_offset is essentially an int that is an offset into the local storage in that group.

    inline group_pointer_type group_ptr() const PLF_NOEXCEPT {
        return group_pointer;
    }
    
    inline typename colony::difference_type localOffset() const PLF_NOEXCEPT {
        return element_pointer - group_pointer->elements;
    }
    

    The reason this is useful is because I can use colony as a backing storage for another data structure in this case an unordered_map, where the key is a 3d integer coordinate and the value is a group/offset pair. This way I can spatially look up a 3d coordinate location and get back the colony group and local offset and index into it.

    auto groups = mycolony.groups();
    
    for (auto it = coordToTilemap.cbegin(); it != coordToTilemap.cend(); ++it) {
        auto gp = groups[it->second.group_pointer->group_number];
        doSomethingWithData((*gp)[it->second.offset].data());
    }
    

    I think this is useful because I can still iterate directly over the colony but also have a custom 'view' over the data.

    Keen to see what others think of this.

  • PLF_CPP20_SUPPORT shouldn't be defined on Android NDK r24

    PLF_CPP20_SUPPORT shouldn't be defined on Android NDK r24

    As best I can tell, this detection is broken for the Android NDK, which ships with a copy of libc++ that does not implement the concepts header. Maybe it would be appropriate to use _LIBCPP_VERSION? There doesn't appear to be a way for users to override this behavior without patching.

  • 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!

🏅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

Aug 7, 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

Aug 12, 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

Aug 11, 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

Aug 9, 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

Aug 8, 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

Aug 1, 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

Aug 9, 2022
Template Library of Tree Data Structures in C++17
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

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

May 23, 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

Jul 25, 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%

Jul 25, 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

Jul 24, 2022
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

Jul 22, 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.

Jul 30, 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

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.

May 14, 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

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

Jul 8, 2022