On Wed, Oct 23, 2013 at 5:07 PM, TONGARI J wrote:

I wonder if we can choose the underlying container for flat_xxx, for example, use deque instead of vector. Or would it be better to make them as adaptors?

That would be a different question for the container implementor. Experience shows that having the implementation type as a parameter is rarely a good idea. Having a vector as implementation is far enough for me right now but I don't really care as long as the flat_* behaviour and performance are similar. I'm not sure what a deque would enable in this case.

On Thu, Oct 24, 2013 at 11:16 AM, Rob Stewart wrote:

...

Experience shows that having the implementation type as a parameter is rarely a good idea. Having a vector as implementation is far enough for me right now but I don't really care as long as the flat_* behaviour and performance are similar.

Is that general experience, or just yours?

Both my experience and some I gathered online, so think more about my impression. That said, it's more about tradeof than just being a good or bad idea, I guess if there is a performance benefit to it and it don't make the implementation hard to follow, it would be a good idea.

...

I'm not sure what a deque would enable in this case.

The same things deque offers over vector normally: VM-friendly allocations and growth at front and back without copying.

If one reserves enough space up front, there's benefit in vector. If allocating on demand, deque can be better.

I see, but it depends a lot on the allocation pattern, so having the choice would help fine tuning, which is your point if I understand correctly.

On Thu, Oct 24, 2013 at 11:58 AM, Rob Stewart wrote:

Still, that flexibility allows the use of std::array, shared memory containers, etc.

I'm not sure what you mean by std::array? Wouldn't it change the semantic of flat_* and impose a specific implementation?

On 24 October 2013 17:10, Rob Stewart wrote:

I meant that stack allocated memory could be used if std::array's interface satisfies the needs of flat_*. std::array can be one choice among many.

I'm not seeing how a container of exactly N elements would be useful as a backing store for flat_xxx. Could you show an example? -- Nevin ":-)" Liber mailto:nevin@eviloverlord.com (847) 691-1404

On Fri, Oct 25, 2013 at 9:44 PM, Rob Stewart wrote:

On Oct 25, 2013, at 2:00 PM, Nevin Liber wrote:

...

On 24 October 2013 17:10, Rob Stewart wrote:

...

I meant that stack allocated memory could be used if std::array's interface satisfies the needs of flat_*. std::array can be one choice among many.

I'm not seeing how a container of exactly N elements would be useful as a backing store for flat_xxx. Could you show an example?

I was just thinking of a use case in which a map is needed, but memory is constrained or preallocated. I was also just showing how permitting user-specified containers opens possibilities.

A flat_map, backed by std::array, is quite possibly no faster than a normal C++11 map, with a suitable allocator. A C++03 map won't use its allocator for nodes, but IIRC, a C++11 map will.

But then it would make the flat_map semantic changes because it have runtime-fixed-size and it makes it not inter-changeable, wouldn't it? That being said it would be the same as to have a pool allocator I guess. Anyway, I still have no answer as to if there is a proposal work in progress or not.

On 25 October 2013 20:44, Rob Stewart wrote:

A flat_map, backed by std::array, is quite possibly no faster than a normal C++11 map, with a suitable allocator. A C++03 map won't use its allocator for nodes, but IIRC, a C++11 map will.

What do you mean by "use"? std::map has always allocated the memory for its nodes using its allocator.

On 28 October 2013 09:04, Rob Stewart wrote:

On Oct 27, 2013, at 8:32 AM, Jonathan Wakely wrote:

...

On 25 October 2013 20:44, Rob Stewart wrote:

...

A flat_map, backed by std::array, is quite possibly no faster than a normal C++11 map, with a suitable allocator. A C++03 map won't use its allocator for nodes, but IIRC, a C++11 map will.

What do you mean by "use"?

std::map has always allocated the memory for its nodes using its allocator.

03's allocator interface means that the element and node allocations were done via different allocator types, which leads to distinct allocations. I don't recall the details, but that prevents using the same memory for both, as I recall.

You're mistaken. The element has always been embedded in the node, so only the node is allocated.

On 24 October 2013 04:16, Rob Stewart wrote:

On Oct 23, 2013, at 11:57 AM, Klaim - Joël Lamotte wrote:

...

On Wed, Oct 23, 2013 at 5:07 PM, TONGARI J wrote:

...

I wonder if we can choose the underlying container for flat_xxx, for example, use deque instead of vector. Or would it be better to make them as adaptors? If one reserves enough space up front, there's benefit in vector. If allocating on demand, deque can be better.

Well, if you are allocating on demand, xxx (possibly with a custom allocator) may be better than flat_xxx... -- Nevin ":-)" Liber mailto:nevin@eviloverlord.com (847) 691-1404

On Sun, Oct 27, 2013 at 1:35 PM, Jonathan Wakely wrote:

No proposal has reached WG21, I can't say whether anyone is working on one.

Ok.

I'm against the idea that every useful container needs to be in the standard, if you want a different set of trade-offs from the standard containers then use different containers, either from Boost, another library, or write your own.

I think I would have have the advice for most non-standard containers, but I strongly disagree in the case of flat_set, flat_map and stable_vector. The standard containers don't provide enough basic alternatives and, at least in my experience and experiences I've read online and discussed with other C++ devs, we end-up often getting back to std::vector for almost anything. Boost's flat_set and flat_map are preferable as default container than std::set/map in almost all cases I've been working on in the last 5 years (which include time I couldn't use these containers in practice). My understanding of the standard is that it should provide useful and widely used tools, like containers, which are then standard because everybody should use them by default. Adding these containers (stable_vector being discutable but I find it extremely useful too) in the standard library would, in my opinion, be a huge improvement both for performance vs simplicity reasons and for ease of education and choice: it's far simpler to just use something that is fundamentally a vector in all cases, but with the interface corresponding to the wanted manipulations, than to have to know the (wide and long to explain) differences between contiguous and node-based containers. Maybe I'm a bit biased by my specific projects, but they are of wide variety and I end up very often choosing flat_map/set instead of std::map/set simply because cases where it flat_* are what I really want occurs far more often than cases where std::set/map are what I really want. It looks like I'm not the only one praising these kind of containers: http://www.slashslash.info/2013/10/ode-to-a-flat-set/ At the time I'm writting this I'm not in the position to start working on a proposal, even if I'm really tempted (I also think I'm not a specialist so maybe I'm not legitimate for this). But I'm considering doing it in coming months when I'm done with other things.

On Sat, Nov 9, 2013 at 11:26 PM, Jonathan Wakely wrote:

...

Boost's flat_set and flat_map are preferable as default container than std::set/map in almost all cases I've been working on in the last 5 years (which include time I couldn't use these containers in practice).

So you almost never need iterator and reference stability?

I do sometime need reference stability but far less often than one would expect. Fast lookup in (relatively) small maps or set are far more common in my experience.

Because if you don't need them, then yes, a sorted std::vector might be a better choice, or another container such as boost::flat_set, which is great and readily available from Boost - maybe you've heard of it ;-)

Yes and I use them a lot. :)

It looks like I'm not the only one praising these kind of containers:

...

http://www.slashslash.info/2013/10/ode-to-a-flat-set/

I'm not saying they're not useful. I specifically said they're useful, you even quoted me saying that. Stop trying to convince me they're useful.

That was not my point but I might not have been clear. My point that I disagree with your following objection, but uniquely for these specific containers.

I'm objecting to the (IMHO too common) view that everything useful should be put in the standard. There are things missing from the standard (networking, databases, XML/XSLT processing, graphics) that would be better for the committee and implementors to spend time on than different containers with small-ish variations on the interfaces and properties of the existing standard containers. The flat_map and flat_set containers exist and are perfectly usable for those who want them.

I understand your objection in general, but I also believe it's actually problematic that there is no sorted vector kind of containers in the standard library today. I also hoped that more very useful boost libraries would get standardized faster. I'll stop here for the talking anyway, there is no point in convincing anyone here I guess. :)