[containers] Are there flat_map/set and stable_vector proposals at work?
All is in the title: I would like to know if flat_map, flat_set and stable_vector have been proposed for inclusion in the C++ standard library, or if there are works going on to write such a proposal. I find that I use a bit more flat associative containers than tree-based standard associative containers in all my recent projects, and I think that having option in the standard to choose one or the other would be very useful for a lot of devs.
2013/10/23 Klaim - Joël Lamotte <mjklaim@gmail.com>
All is in the title: I would like to know if flat_map, flat_set and stable_vector have been proposed for inclusion in the C++ standard library, or if there are works going on to write such a proposal.
I find that I use a bit more flat associative containers than tree-based standard associative containers in all my recent projects, and I think that having option in the standard to choose one or the other would be very useful for a lot of devs.
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?
On Wed, Oct 23, 2013 at 5:07 PM, TONGARI J <tongari95@gmail.com> 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 Oct 23, 2013, at 11:57 AM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:
On Wed, Oct 23, 2013 at 5:07 PM, TONGARI J <tongari95@gmail.com> 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.
It can, and possibly should, be in the hands of the user. After all, one selects flat_map over map, for example, for performance reasons.
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?
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. ___ Rob (Sent from my portable computation engine)
On Thu, Oct 24, 2013 at 11:16 AM, Rob Stewart <robertstewart@comcast.net>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 Oct 24, 2013, at 5:31 AM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:
On Thu, Oct 24, 2013 at 11:16 AM, Rob Stewart <robertstewart@comcast.net>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.
Specializations, with different containers, would be different types, so interoperability adds complexity. Without concepts, BCCL should be used to ensure the container satisfies the interface requirements. That increases complexity, of course, and doesn't verify semantics. Still, that flexibility allows the use of std::array, shared memory containers, etc.
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.
Right. ___ Rob (Sent from my portable computation engine)
On Thu, Oct 24, 2013 at 11:58 AM, Rob Stewart <robertstewart@comcast.net>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 Oct 24, 2013, at 6:07 AM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:
On Thu, Oct 24, 2013 at 11:58 AM, Rob Stewart <robertstewart@comcast.net>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?
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. ___ Rob (Sent from my portable computation engine)
On 24 October 2013 17:10, Rob Stewart <robertstewart@comcast.net> 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 Oct 25, 2013, at 2:00 PM, Nevin Liber <nevin@eviloverlord.com> wrote:
On 24 October 2013 17:10, Rob Stewart <robertstewart@comcast.net> 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. ___ Rob (Sent from my portable computation engine)
On Fri, Oct 25, 2013 at 9:44 PM, Rob Stewart <robertstewart@comcast.net>wrote:
On Oct 25, 2013, at 2:00 PM, Nevin Liber <nevin@eviloverlord.com> wrote:
On 24 October 2013 17:10, Rob Stewart <robertstewart@comcast.net> 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 Oct 25, 2013, at 3:49 PM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:
On Fri, Oct 25, 2013 at 9:44 PM, Rob Stewart <robertstewart@comcast.net>wrote:
On Oct 25, 2013, at 2:00 PM, Nevin Liber <nevin@eviloverlord.com> wrote:
On 24 October 2013 17:10, Rob Stewart <robertstewart@comcast.net> 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.
The semantics would be the same: std::bad_alloc when memory is exhausted. The difference is that one gets a prescribed amount of memory a priori and the other can try to use all available application memory. ___ Rob (Sent from my portable computation engine)
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 Oct 27, 2013, at 8:32 AM, Jonathan Wakely <jwakely.boost@kayari.org> 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. ___ Rob (Sent from my portable computation engine)
On 28 October 2013 09:04, Rob Stewart wrote:
On Oct 27, 2013, at 8:32 AM, Jonathan Wakely <jwakely.boost@kayari.org> 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 Oct 28, 2013, at 6:23 AM, Jonathan Wakely <jwakely.boost@kayari.org> wrote:
On 28 October 2013 09:04, Rob Stewart wrote:
On Oct 27, 2013, at 8:32 AM, Jonathan Wakely <jwakely.boost@kayari.org> 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.
I'm sure that's right, now that you say it. I can't think of the issue that's stuck in the back of my head. It's probably not relevant anyway. :) ___ Rob (Sent from my portable computation engine)
On 24 October 2013 04:16, Rob Stewart <robertstewart@comcast.net> wrote:
On Oct 23, 2013, at 11:57 AM, Klaim - Joël Lamotte <mjklaim@gmail.com> wrote:
On Wed, Oct 23, 2013 at 5:07 PM, TONGARI J <tongari95@gmail.com> 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 23 October 2013 15:39, Klaim - Joël Lamotte wrote:
All is in the title: I would like to know if flat_map, flat_set and stable_vector have been proposed for inclusion in the C++ standard library, or if there are works going on to write such a proposal.
No proposal has reached WG21, I can't say whether anyone is working on one. 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.
On Sun, Oct 27, 2013 at 1:35 PM, Jonathan Wakely <jwakely.boost@kayari.org>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 9 November 2013 15:37, Klaim - Joël Lamotte wrote:
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.
Good, it's the right most for most situations :-)
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? 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 ;-)
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.
According to Stepanov (and IIRC Stroustrup) everyone should use vector by default :-)
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. 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.
On Sat, Nov 9, 2013 at 11:26 PM, Jonathan Wakely <jwakely.boost@kayari.org>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:
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. :)
participants (5)
-
Jonathan Wakely -
Klaim - Joël Lamotte -
Nevin Liber -
Rob Stewart -
TONGARI J