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.

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

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.

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.

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.

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.

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

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.

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!

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.

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!