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
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
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
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

PpHd 527 Oct 2, 2022
Is a linear data structure with O(log n) searches and O(cbrt n) insertions and index lookups.

A binary cube is a linear data structure that contains a sorted two dimensional dynamic array of nodes which each point to a sorted array

null 22 Jul 13, 2022
Gcpp - Experimental deferred and unordered destruction library for C++

You can find a talk that describes this library here: Video: "Leak-Freedom in C++... By Default" (CppCon 2016) PDF slides gcpp: Deferred and unordered

Herb Sutter 855 Sep 28, 2022
C++ hash map and hash set which preserve the order of insertion

C++ hash map and hash set which preserves the order of insertion The ordered-map library provides a hash map and a hash set which preserve the order o

Thibaut Goetghebuer-Planchon 368 Sep 23, 2022
🏅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 630 Sep 21, 2022
Provides very lightweight outcome and result (non-Boost edition)

master branch develop branch CTest dashboard: https://my.cdash.org/index.php?project=Boost.Outcome All tests passing source tarballs: https://github.c

Niall Douglas 557 Sep 22, 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.6k Sep 30, 2022
Higher level programming in C

Cello Cello is a library that brings higher level programming to C. By acting as a modern, powerful runtime system Cello makes many things easy that w

Daniel Holden 6k Sep 25, 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 6 Aug 19, 2022
Very Fast Non-Cryptographic Hash Function

KOMIHASH - Very Fast Hash Function Introduction The komihash() function available in the komihash.h file implements a very fast 64-bit hash function,

Aleksey Vaneev 75 Sep 28, 2022
C++ Type Traits for Smart Pointer

SmartPointerTypeTrait C++ Type Traits for Smart Pointer is_a_pointer is_smart_pointer template < typename T > struct is_smart_ptr : is_smart_ptr_impl<

null 12 Sep 14, 2022
Cross-platform STL-styled and STL-compatible library with implementing containers, ranges, iterators, type traits and other tools; actors system; type-safe config interface.

Yato A small repository where I'm gatherting useful snippets and abstractions for C++ development. Yato includes 3 main modules: multidimensional cont

Alexey 9 Jul 22, 2022
Allocator Aware Containers Made Easy

Custom Allocator Aware containers made easy with "wit" Have you ever looked at the allocator specification and thought about how hard it would be to

Darth Rubik 4 Sep 25, 2021
This algorithm is amazing and take a high performance to search something under array.

Sequential Binary Algorithm O(n) Algoritmo Este é um algoritmo de complexidade O(log n), que possui uma alta performance em percorrer um vetor de inte

Guilherme Serafim Kollet 1 Oct 26, 2021
High performance build system for Windows, OSX and Linux. Supporting caching, network distribution and more.

FASTBuild FASTBuild is a build system for Windows, OSX and Linux, supporting distributed compilation and object caching. It is used by many game devel

FASTBuild 971 Oct 2, 2022
Benchmarking a trivial replacement for std::vector

std::vector replacement benchmark Dependencies You'll need gnuplot and bash to run ./bench.sh. In addition to that, you'll need to have gcc and clang

Dale Weiler 9 Aug 27, 2022