Ion Gazta?aga
I recently committed to develop the initial implementation (not properly tested!) to use a different container than boost::container::vector as the underlying sequence. The idea is to pass a container instead of an allocator:
flat_set
?? and
flat_set
Hi Ion, This now works for me. I've done some quick benchmarks; I have a test harness that applies a sequence of operations - insert, erase by value, assign, empty(), equality comparison, enumeration - extracted from a run of my application to various implementations of small sets. The value type in each case is uint64_t and for the static and small vectors the size is 8. Benchmark run times are: 2.2 no-op - test harness only 65.2 std::set 38.3 std::set with move assignment (*) 20.2 boost::container::flat_set using std::vector 15.8 boost::container::flat_set (defaults) 17.6 boost::container::flat_set using boost::container::small_vector 15.6 boost::container::flat_set using boost::container::static_vector 16.7 my linear flat_set using boost::container::small_vector 15.3 my linear flat_set using boost::container::static_vector (*) std::set with move assignment doesn't have the same semantics as the other tests so it isn't directly comparable, as some assignments in my application need the assigned-from value afterwards and others don't. This is on an ARM64 system (Cavium ThunderX) using: $ g++ --version g++ (Debian 6.3.0-18) 6.3.0 20170516 So it appears that my linear flat set has just a tiny benefit over binary search for this set size. The theory is that when N is small, the O(log N) vs. O(N) difference is less important than the simpler algorithms and better branch prediction of linear methods. Benchmark code is here: http://chezphil.org/tmp/set_bm.tgz Regards, Phil.