On 05/09/2017 9:07, Thorsten Ottosen via Boost wrote:

Den 04-09-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:

...

On 04/09/2017 17:12, Phil Endecott via Boost wrote:

...

...

Any thoughts?

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:

Awesome. Also for flat_map, I presume?

Sure! Ion

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

should work. Or better said, they'll work properly soon. Willing to try?

detail/flat_tree.hpp line 459 tries to use a macro BOOST_INTRUSIVE_HAS_TYPE which doesn't seem to be defined anywhere. Regards, Phil.

...

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.

Hi Ion, Ion Gazta?aga wrote:

Many thanks. I need to see why flat_set segfaults.

Errr..... Are you looking at the line where I wrote "15.8 boost::container::flat_set (defaults)" and reading it as "segfaults" ? I just mean flat_set, with its other template parameters as their default values. Nothing segfaults. Regards, Phil.

Hi degski, degski wrote:

On 4 September 2017 at 18:12, Phil Endecott via Boost

...

wrote:

But that gets complicated if you need iterators with the normal behaviour.

Wrap a std::vector or a std::array (if fixed size) and forward the begin() and end() iterators of the container. This then will also give you range based for loops (for free) on your type.

Of course that works for a sorted vector. But in the part of my message that you didn't quote, I mentioned storing the values in an unsorted vector and doing linear search. In this case, you can usefully iterate over the entire container as long as you don't care about the order, but you can't iterate over, for example, the range between two elements that you get from find(). Regards, Phil.