[Containers] Should flat_* expose implementation vector?
Dear All, Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation? Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface. Cons: it lets the user break the invariants. Const access to the impl is another possibility. Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?) And/or: should flat_* actually be adaptors that take a reference to their underlying implementation? Regards, Phil.
On Fri, Aug 5, 2011 at 5:32 PM, Phil Endecott < spam_from_boost_dev@chezphil.org> wrote:
Dear All,
Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation?
Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface.
Cons: it lets the user break the invariants.
Const access to the impl is another possibility.
Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?) And/or: should flat_* actually be adaptors that take a reference to their underlying implementation?
Maybe consider the flat_* interface factored out into a family of free functions applicable to any...ummm..."extensible" (e.g., has some kind of push_back functionality, etc.?) range? Just a quick thought. - Jeff
Phil Endecott wrote:
Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation?
+1 Or, I would want `uncompared_push_back` (just filling the flat_* container without sorting) and `sort` functions.
Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?) And/or: should flat_* actually be adaptors that take a reference to their underlying implementation?
+1 It would be nice to use stack-based container (e.g. auto_buffer) as the underlying implementation of flat_* containers. Regards, Michel
On Fri, Aug 5, 2011 at 19:05, Michel MORIN <mimomorin@gmail.com> wrote:
Or, I would want `uncompared_push_back` (just filling the flat_* container without sorting) and `sort` functions.
Can we do this with move semantics instead? I picture putting a bunch of data into a flat_set::internal_storage_type, then move-constructing a flat_set from that container, which would do the sorting to fix up the invariants. It would also make sense to have a flat_set::release() function that returns a (moved) temporary of the internal storage.
Scott McMurray wrote:
On Fri, Aug 5, 2011 at 19:05, Michel MORIN <mimomorin@gmail.com> wrote:
Or, I would want `uncompared_push_back` (just filling the flat_* container without sorting) and `sort` functions.
Can we do this with move semantics instead?
Partially yes. But, partially no: when using stack-based allocator (or stack-based container as the underlying implementation of flat_* containers), the overhead of `move` is non-negligible. Regards, Michel
2011/8/6 Michel MORIN <mimomorin@gmail.com>:
Scott McMurray wrote:
Can we do this with move semantics instead?
Partially yes. But, partially no: when using stack-based allocator (or stack-based container as the underlying implementation of flat_* containers), the overhead of `move` is non-negligible.
I meant, "the overhead of move-construct is non-negligible." Regards, Michel
El 06/08/2011 2:32, Phil Endecott escribió:
Dear All,
Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation?
Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface.
Cons: it lets the user break the invariants.
Another possibility is to have a constructor an implementation (which should be guaranteed to be ordered and unique (for flat_(multi)set) taking a implementation as rvalue. Another impl_t extract() function that move returns (or additionally as in some cases (like loops) is more efficient to avoid new object creation, via swapping: void exchange(impl_t &imp)). In debug mode we could check ordering when constructing from an implementation.
Const access to the impl is another possibility.
This is easy and useful for passing the vector to other functions that don't need any ordering.
Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?) And/or: should flat_* actually be adaptors that take a reference to their underlying implementation?
The problem is that flat_xxx take advantage of already implemented move semantics (insertions, etc.) from ::boost::container::vector. stable_vector has the same interface so it would be easy. The problem is to define the Concept (in post C++0x terms) flat_xxx::implementation should be based on. Best, Ion
On Aug 6, 2011, at 8:56 AM, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
The problem is that flat_xxx take advantage of already implemented move semantics (insertions, etc.) from ::boost::container::vector. stable_vector has the same interface so it would be easy. The problem is to define the Concept (in post C++0x terms) flat_xxx::implementation should be based on.
I guess the obvious question is, does a vanilla c++0x vector fit the bill, and if not, what's missing?
El 06/08/2011 20:00, Gordon Woodhull escribió:
On Aug 6, 2011, at 8:56 AM, Ion Gaztañaga<igaztanaga@gmail.com> wrote:
The problem is that flat_xxx take advantage of already implemented move semantics (insertions, etc.) from ::boost::container::vector. stable_vector has the same interface so it would be easy. The problem is to define the Concept (in post C++0x terms) flat_xxx::implementation should be based on.
I guess the obvious question is, does a vanilla c++0x vector fit the bill, and if not, what's missing?
Of course, but vector has a complex interface and I don't know if that would be an acceptable. We also need to define the C++03 subset for vector (with emulated move semantics). Ion
on Fri Aug 05 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:
Dear All,
Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation?
Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface.
Cons: it lets the user break the invariants.
Const access to the impl is another possibility.
Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?)
One way I've dealt with this sort of thing in the past is to allow the user to get an intrusive and dangerous interface initially, and then throw it away later leaving only an invariant-preserving interface. Obviously you can't do that with a single class.
And/or: should flat_* actually be adaptors that take a reference to their underlying implementation?
I'm not sure that's a win if you have move semantics. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Den 06-08-2011 02:32, Phil Endecott skrev:
Dear All,
Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation?
Yes!
Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface.
Cons: it lets the user break the invariants.
Const access to the impl is another possibility.
The interface should be like this, like we e.g. do it PtrContainer: Container& base(); const Container& base() const; This ensures that const flat_xxx objects preserves invariants (unless you do a const_cast which is ok). We can never foresee all uses, and overincapsulation is a serious issue. I have also never heard complaints about the interface in PtrContainer, and it has been useful more than once for users. -Thorsten
participants (8)
-
Dave Abrahams -
Gordon Woodhull -
Ion Gaztañaga -
Jeffrey Lee Hellrung, Jr. -
Michel MORIN -
Phil Endecott -
Scott McMurray -
Thorsten Ottosen