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.
Home Page: https://plflib.org/colony.htm
License: zlib License
Line 280 in e6e563b
Both sides of the operator || are equivalent. Sorry, this was clang static analyzer saying this, maybe the static analyzer is buggy, so closing this.
Hi! This library is being added to ConanCenter: conan-io/conan-center-index#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!
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
I'm sure this is just my misinterpretation/misunderstanding.
But. Here http://plflib.org/benchmarks_core2_gcc.htm#rawperformance , at "Post-erasure Iteration Performance" section, as I can see at 100'000 elements with 25% percentage erasure probability, plf::colony should perform +/- in pair with std::vector. Right? Just to clarify - elements from std::vector erased too?
I made small benchmark:
https://github.com/tower120/plf_colony_test
int capacity = 100'000;
float erase_probability = 25;
I got 350ms for std::vector and 1500ms for plf::colony, on i7-4771 with gcc 7 and +/- the same with VS 2017 clang/c2 (or whatever compiler they used for open CMake folder).
I could think that this is because of gaps in memory between element positions in plf::colony, after random erasure, but...
P.S. Erased plf::colony surely iterates faster then full, but speed up is not linear (like with std::vector).
P.P.S. For erase_probability = 90 there is 10 fold difference.
P.P.P.S. Maybe you benchmarked in some erase/emplace cycle? Or I, in someway, use it under different conditions?
Using plf::colony with clang++ 7.0.0 under C++11 or later gives the following compilation errors.
$ clang++ --version
clang version 7.0.0
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin
$ clang++ plf_colony_test_suite.cpp -o test
In file included from plf_colony_test_suite.cpp:45:
./plf_colony.h:350:11: error: expected ';' at end of declaration list
~group() PLF_COLONY_NOEXCEPT
^
;
./plf_colony.h:398:70: error: expected ';' at end of declaration list
inline colony_iterator & operator = (const colony_iterator &source) PLF_COLONY_NOEXCEPT
^
;
./plf_colony.h:707:85: error: expected ';' at end of declaration list
inline colony_reverse_iterator& operator = (const colony_reverse_iterator &source) PLF_COLONY_NOEXCEPT
^
;
./plf_colony.h:961:57: error: expected ';' at end of declaration list
explicit ebco_pair2(const skipfield_type min_elements) PLF_COLONY_NOEXCEPT: min_elements_per_group(min_elements) {}
^
;
./plf_colony.h:967:56: error: expected ';' at end of declaration list
explicit ebco_pair(const skipfield_type max_elements) PLF_COLONY_NOEXCEPT: max_elements_per_group(max_elements) {}
^
;
./plf_colony.h:975:10: error: expected ';' at end of declaration list
colony() PLF_COLONY_NOEXCEPT:
^
;
./plf_colony.h:3541:22: error: expected ';' at end of declaration list
sort_dereferencer() PLF_COLONY_NOEXCEPT
^
;
./plf_colony.h:3648:8: error: use of undeclared identifier 'less'
sort(less());
^
plf_colony_test_suite.cpp:137:38: error: no member named 'empty' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("Colony empty", p_colony.empty());
~~~~~~~~ ^
plf_colony_test_suite.cpp:140:13: error: no member named 'insert' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
p_colony.insert(&ten);
~~~~~~~~ ^
plf_colony_test_suite.cpp:142:43: error: no member named 'empty' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("Colony not-empty", !p_colony.empty());
~~~~~~~~ ^
plf_colony_test_suite.cpp:146:43: error: no member named 'begin' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("Begin() working", **p_colony.begin() == 10);
~~~~~~~~ ^
plf_colony_test_suite.cpp:147:39: error: no member named 'begin' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("End() working", p_colony.begin() != p_colony.end());
~~~~~~~~ ^
plf_colony_test_suite.cpp:147:59: error: no member named 'end' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("End() working", p_colony.begin() != p_colony.end());
~~~~~~~~ ^
plf_colony_test_suite.cpp:150:13: error: no member named 'clear' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
p_colony.clear();
~~~~~~~~ ^
plf_colony_test_suite.cpp:152:49: error: no member named 'begin' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("Begin = End after clear", p_colony.begin() == p_colony.end());
~~~~~~~~ ^
plf_colony_test_suite.cpp:152:69: error: no member named 'end' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
failpass("Begin = End after clear", p_colony.begin() == p_colony.end());
~~~~~~~~ ^
plf_colony_test_suite.cpp:158:14: error: no member named 'insert' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
p_colony.insert(&ten);
~~~~~~~~ ^
plf_colony_test_suite.cpp:159:14: error: no member named 'insert' in 'plf::colony<int *, std::allocator<int *>, unsigned short>'
p_colony.insert(&twenty);
~~~~~~~~ ^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
I'll try rebuilding clang to see if this is just the result of a compiler bug. Still gives the same errors.
Oddly enough, this doesn't happen in C++98.
Just out of curiosity:
Is there a specific reason why there is no "visit" function, which takes a lambda/functor with the block pointers as the signature?
I suppose the allocation for the bitfield location would still be required so not much is saved there.
erased_locations is used as a set of blocks that were freed but is external to the colony which requires a cache miss to get a erased block.
Instead you can store a next pointer in the deallocated element and have a stored_element_type to the last deallocated element
union union_element_type {
element_type el,
stored_element_pointer_type next;
}
typedef union_element_type* union_element_pointer_type
iterator erase(const iterator &the_iterator)
{
//...
//instead of pushing onto erased_locations and after destructor
the_iterator.union_element_pointer->next = first_erased_element_pointer;
first_erased_element_pointer = the_iterator.union_element_pointer;
//...
}
iterator insert(element_type &&element)
{
//...
//instead of popping of erased_locations
iterator new_location;
new_location.element_pointer = first_erased_element_pointer;
first_erased_element_pointer = first_erased_element_pointer->next;
PLF_COLONY_CONSTRUCT(...);
//...
}If preallocation via reserve() requests only 1 or 2 elements, there's either a crash — or, in debug builds, an assert failure.
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.
Hi, I have been looking forward to trying out your library! Unfortunately I immediately ran into an issue which at first glance seems like a bug.
Several lines in the the move-insert code look like this:
Line 2340 in abd54bd
I may be misunderstanding things as I just started playing with the library, so apologies if I'm mistaken. I've (hopefully) fixed things in my fork so that I can keep experimenting, so I'll go ahead and submit a pull request.
Thanks!
Hello,
Do you know about Conan?
Conan is modern dependency manager for C++. And will be great if your library will be available via package manager for other developers. For making a package you should make release of the library and then write a simple script.
Here you can find example, how you can create package for the library.
If you have any questions, just ask :-)
Right now exceptions are a fixed part of plf_colony, but many projects have exceptions disabled, especially games.
This obviously means that plf_colony will not compile.
I was wondering if there was any interest in supporting users that have disabled exceptions via macros for/around try, catch and throw?
The length_errors could also be handled via asserts in those cases as well.
Was this a deliberate choice or just never considered?
If its deliberate, modifying the source to fit the use case is obviously a valid solution as well, just makes integrating new versions slightly more work.
I know, this probably seems overkill for a single header library, but have you considered adding a simple cmake file that provides a Plf::cplony target and maybe to adopt a project layout that puts the header files in a subfolder with the name of your library (as much as such a thing exists?) Specifically I'd put the code into <project-root>/include/plf/colony.h or <project-root>/plf/colony.h.
The idea behind it isn't that it would make using plf_colony much simpler than it already is (but also not harder) it is just that this way, one can use all dependencies in a similar fashion, regadless, of how big or small they are or how complicated their project structure is:
I could e.g. just use
target_link_libraries( my_target PULBIC
Boost::filesystem
Plf::colony
Catch2::Catch2
... other dependencies
)
to my cmake script and
#include <boost/filesystem/fstream.hpp>
#include <plf/colony.h>
#include <catch2/catch.hpp>
#include <lib/file.h>
to my c++ code.
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.
Hi,
I get crashes with colony after it's running for a few hours on rhel 9. I get that with different compilers so the compiler shouldn't be the problem. Here's the trace:
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff72af91e in free () from /lib64/libc.so.6
(gdb) bt
#0 0x00007ffff72af91e in free () from /lib64/libc.so.6
#1 0x00000000004044d5 in nclient::~nclient (this=0x516f10) at netcheck.cxx:57
#2 0x00000000004044b9 in __gnu_cxx::new_allocator<nclient>::destroy<nclient> (this=0x7fffffffe1d0,
__p=0x516f10)
at /usr/lib/gcc/x86_64-redhat-linux/11/../../../../include/c++/11/ext/new_allocator.h:168
#3 0x000000000040448d in std::allocator_traits<std::allocator<nclient> >::destroy<nclient> (__a=...,
__p=0x516f10)
at /usr/lib/gcc/x86_64-redhat-linux/11/../../../../include/c++/11/bits/alloc_traits.h:535
#4 0x000000000040415d in plf::colony<nclient, std::allocator<nclient>, (plf::priority)1>::destroy_element (
this=0x7fffffffe1d0, element=0x516f10) at ./plf_colony.h:1159
#5 0x0000000000403192 in plf::colony<nclient, std::allocator<nclient>, (plf::priority)1>::erase (
this=0x7fffffffe1d0, it=...) at ./plf_colony.h:2411
#6 0x000000000040293a in main () at netcheck.cxx:120
The program in question is a network related tool but unfortunately I'm not at liberty to show the full source. However, here are the relevant parts:
struct nclient {
string ip;
unsigned port;
time_t lastcheck;
};
...
plf::colony<struct nclient> nclients;
plf::colony<struct nclient>::iterator it;
struct nclient dummy;
...
for (it = nclients.begin(); it != nclients.end(); ++it) {
if (it->lastcheck < cutoff)
it = nclients.erase(it); // <== CRASHES HERE
}
the content gets added like this later on:
dummy.ip = row[0];
dummy.port = port;
dummy.lastcheck = now;
nclients.insert(dummy);
I ran the same program with a vector before I switched to colony which worked fine. The only difference I noticed was that accessing the struct's members with colony is via pointer (->).
This happens with 7.39 i checked out from github after you fixed the exceptions bug i reported.
Any help would of course be welcome ...
Thank you for this library! I had used something less-than-ideal for this container's purpose before.
I have a use case for getting an (const_)iterator from a const T*. get_iterator_from_pointer works, but I must const_cast the pointer first.
If you will allow a const_cast, it should be trivial to implement an overload for this:
const_iterator get_iterator_from_pointer(const const_pointer element_pointer) const
{
return get_iterator_from_pointer(const_cast<pointer>(element_pointer));
}
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 have a colony with a few erased elements, however not the first one. I pass in an iterator to the first element (retrieved via begin()) and a distance of 1.
This leads to the code block starting at line 3013 being executed which leaves the skipfield_pointer as is (skipfield being 0) and also skips the while-loop (--distance will be 0). This will return the same iterator as being passed in, having a distance of 0 instead of 1.
I believe the "--distance" should actually read "distance--" to be correct.
The same is probably true for negative distances however I did not test this.
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
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.
Could you please add some documentation? At least a list of implemented functions is pretty much a requirement for using the library. An user can blindly try STL assumptions, but quite a few bits differ.
There's the webpage which contains most of what would be needed, but that's not the usual way of providing documentation...
gcc version 8.3.0 (Debian 8.3.0-6)
plf_colony/plf_colony.h:1448:73: error: conversion from ‘int’ to ‘plf::colonyftags::Record::skipfield_type’ {aka ‘short unsigned int’} may change value [-Werror=conversion]
const skipfield_type new_value = *(new_location.skipfield_pointer) - 1;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
The Build2 package of PLF-Colony is published on https://cppget.org which have a CI system which regularly builds the package with new setup. See for example: https://cppget.org/plf-colony/5.11.0
On all builds related to msvc, there is this warning which seems to be serious:
plf_colony_test_suite.cpp(236): warning C4996: 'freopen': This function or variable may be unsafe. Consider using freopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
C:\Program Files (x86)\Windows Kits\10\include\10.0.17763.0\ucrt\stdio.h(243): note: see declaration of 'freopen'
I'm not totally sure if replacing the call by freopen_s would be the best solution here, in particular if that line is supposed to compile on several platforms. Maybe making a local version would work?
Was recently playing around with plf::colony (it's great) and wanted to update some utilities to use it instead of std::vector. While insert() covers the functionality needed, consider adding proxies for it matching the std::vector methods so that other developers can search and replace in their codebases.
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?
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.
Hi Matt,
Colony looks great. I am very excited to be using this. It's been about 15 years since I last developed in C++ and I came across your website (and your Gamasutra articles) while I was researching what is new in C++ since 2002. I am developing a game using the Godot engine and colony is the exact kind of container I'm looking for.
I am having difficulties getting colony to compile with either clang or gcc on a linux box. It appears that the compilers are having issues with an optional memset optimization in the blank() function. The gcc output is slightlly different and I have included both below. As a workaround I commented out the optional memset block (lines 1054-1062) to get it to compile. From what I could tell commenting out the code shouldn't impact the proper working of colony or materially impact its performance (at least I hope this is the case; my C++ is rusty).
I'm fairly sure this isn't a critical error/issue, but I wanted to make you aware of it all the same.
Thanks for your efforts,
Joshua
Error with clang
scons: Reading SConscript files ...
scons: done reading SConscript files.
scons: Building targets ...
clang++ -o src/common.os -c -g -O3 -std=c++11 -Wno-writable-strings -fPIC -I/home/joshua/Desktop/sdf_local/godot_headers -I/home/joshua/Desktop/sdf_local/godot-cpp/include -I/home/joshua/Desktop/sdf_local/godot-cpp/include/core -Isrc src/common.cpp
In file included from src/common.cpp:20:
In file included from src/csbx_force_sim.hpp:9:
src/plf_colony.h:1058:61: error: 'colony' does not refer to a value
...std::memset(reinterpret_cast<void *>(this), 0, offsetof(colony, pointer_allocator_pair));
^
src/plf_colony.h:209:149: note: declared here
...typename element_skipfield_type = unsigned short > class colony : private element_allocator_...
^
1 error generated.
scons: *** [src/common.os] Error 1
scons: building terminated because of errors.
Error with gcc
scons: Reading SConscript files ...
scons: done reading SConscript files.
scons: Building targets ...
g++ -o src/common.os -c -g -O3 -std=c++11 -Wno-writable-strings -fPIC -I/home/joshua/Desktop/sdf_local/godot_headers -I/home/joshua/Desktop/sdf_local/godot-cpp/include -I/home/joshua/Desktop/sdf_local/godot-cpp/include/core -Isrc src/common.cpp
In file included from src/csbx_force_sim.hpp:9:0,
from src/common.cpp:20:
src/plf_colony.h: In member function 'void plf::colony<element_type, element_allocator_type, element_skipfield_type>::blank()':
src/plf_colony.h:1058:67: error: expected primary-expression before ',' token
std::memset(reinterpret_cast<void *>(this), 0, offsetof(colony, pointer_allocator_pair));
It might be an unusual combination, but while build-testing the SG14 repo, I found that I had to disable PLF_COLONY_TYPE_TRAITS_SUPPORT on one of my platforms.
The specific combination is clang (4.0 in this case) with libstdc++4.8 (on CentOS7), where the latter lacks std::is_trivially_copyable.
I believe it's not possible to detect this, due to libstdc++ versioning breakage missteps.
So this is basically a request for an inverse or other way of overriding the PLF_COLONY_TYPE_TRAITS_SUPPORT to force it to not be defined if the build system says so.
You can just call get_iterator_from_pointer( (T*) 0x13370000 ) and the method will not return end() but a valid iterator.
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.
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;
}
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.
Hello!
I've run into an issue that prevents me from updating plf to the newer/latest version.
I use plf colony in a slightly unusual way:
class cBuildingGameObject : public tNonUpdateableGameObject<Volumetric::voxelModelInstance_Static>, public type_colony<cBuildingGameObject>
In this case thru multiple inheritance. I have attached the type_colony and related plf files I have been using. btw, plf is literally awesome.
The problem is a change that prevents me from using it with inheritance.
In the plf_colony.new.h file, lines 279-283
#ifdef PLF_ALIGNMENT_SUPPORT
typedef typename std::aligned_storage<sizeof(element_type), (sizeof(element_type) >= (sizeof(skipfield_type) * 2) || alignof(element_type) >= (sizeof(skipfield_type) * 2)) ? alignof(element_type) : (sizeof(skipfield_type) * 2)>::type aligned_element_type;
#else
typedef element_type aligned_element_type;
#endif
Which is where the problem lies, as element_type is not defined while using inheritance.
eg.)
class C : public type_colony<C>
+------------ type_colony<C> contains plf::colony<C>
[type_colony.zip](https://github.com/mattreecebentley/plf_colony/files/6948747/type_colony.zip)
C is undefined, element type cannot be used before definition.
In the plf_colony.h file this PLF_COLONY_ALIGNMENT_SUPPORT
is undefined before inclusion globally in my usage to work-around this issue.
One of the benefits of using inheritance like I have here, is the association with the type. static methods in type_colony access the the internal colony representing all instances of the type it contains. The type it contains can also be overridden in further levels of inheritance.
The type safety and access is simplified and directly the type being used for all of it's instances.
Thank you for your time!
I get the following failure, both with gcc (tried 9 and 10) and clang (9):
In file included from plf_colony_test_suite.cpp:188:
plf_colony.h: In instantiation of ‘void plf::colony<element_type, element_allocator_type, element_skipfield_type>::fill_skipblock(const element_type&, plf::colony<element_type, element_allocator_type, element_skipfield_type>::aligned_pointer_type, plf::colony<element_type, element_allocator_type, element_skipfield_type>::skipfield_pointer_type, plf::colony<element_type, element_allocator_type, element_skipfield_type>::skipfield_type) [with element_type = int; element_allocator_type = std::allocator<int>; element_skipfield_type = short unsigned int; plf::colony<element_type, element_allocator_type, element_skipfield_type>::aligned_pointer_type = std::aligned_storage<4, 4>::type*; plf::colony<element_type, element_allocator_type, element_skipfield_type>::skipfield_pointer_type = short unsigned int*; plf::colony<element_type, element_allocator_type, element_skipfield_type>::skipfield_type = short unsigned int]’:
plf_colony.h:2169:7: required from ‘void plf::colony<element_type, element_allocator_type, element_skipfield_type>::insert(plf::colony<element_type, element_allocator_type, element_skipfield_type>::size_type, const element_type&) [with element_type = int; element_allocator_type = std::allocator<int>; element_skipfield_type = short unsigned int; plf::colony<element_type, element_allocator_type, element_skipfield_type>::size_type = long unsigned int]’
plf_colony_test_suite.cpp:642:28: required from here
plf_colony.h:2062:51: error: ‘reinterpret_cast’ from type ‘const int*’ to type ‘plf::colony<int>::aligned_pointer_type’ {aka ‘std::aligned_storage<4, 4>::type*’} casts away qualifiers
2062 | std::fill_n(location, number_of_elements, *(reinterpret_cast<aligned_pointer_type>(&aligned_copy)));
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(then more of the same)
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!
MSVC 2017 with /W4 /WX complains about the constant condition on line 1039 of plf_colony.h. It suggests changing the plain if to if constexpr, and I agree.
template <bool r_is_const> class colony_reverse_iterator
{
inline PLF_FORCE_INLINE pointer * operator -> () const PLF_NOEXCEPTI might be misunderstanding, but this is different than the forward iterator?
template <bool is_const> class colony_iterator
{
inline PLF_FORCE_INLINE pointer operator -> () const PLF_NOEXCEPT
{I'm not sure why the reverse iterator signature returns a pointer * instead of a pointer like the forward iterator.
When I tried to update plf_colony conan package, I met a compilation error on apple-clang 14.
conan-io/conan-center-index#15454
This is caused by apple-clang 14 defaulting C++20 with poor C++20 supports.
My suggestion is adding condition to enable PLF_CPP20_SUPPORT:
original
(defined(__clang__) && (__clang_major__ >= 13))suggested
(!defined(__APPLE_CC__) && defined(__clang__) && (__clang_major__ >= 13))Please apply it if possible.
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.
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.
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!
Documentation claims:
"However, if only move-insert and/or emplace are utilized to insert elements into the colony, T is only required to meet the requirements of Erasable."
I can't get this to actually work.
Repro steps:
MSVC compiler will complain about accessing private function (deleted constructors). When removing the two lines that delete the two copy constructors, code compiles.
When using plf_colony 4.14 with the Intel C++ 18.0.1 compiler I get the following warning:
plf_colony.h(1918): message #280: selector expression is constant
switch (prev_skipfield | (after_skipfield << 1))
^
I haven't really looking into it - just wanted to let know so you can check if that is a false alarm or not.
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 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.
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.