C++ Logo


Advanced search

Re: Container.iterator_to for getting an iterator form the reference to value

From: Jason McKesson <jmckesson_at_[hidden]>
Date: Thu, 13 Aug 2020 17:00:57 -0400
On Thu, Aug 13, 2020 at 11:56 AM Barry Revzin via Std-Proposals
<std-proposals_at_[hidden]> wrote:
> On Thu, Aug 13, 2020 at 9:58 AM Arthur O'Dwyer via Std-Proposals <std-proposals_at_[hidden]> wrote:
>> To implement `iterator_to` for anything except `vector`, you have to rely on a cast like this:
>> struct Node {
>> T t;
>> Node *next;
>> };
>> Node *node_from_t(T *t) {
>> return reinterpret_cast<Node *>(t);
>> }
>> int main() {
>> Node n;
>> assert(node_from_t(&n.t) == &n);
>> }
>> I'm not sure if this is well-defined. As long as `t` is the first member of `Node`, I think it might actually be well-defined; but I wouldn't bet money on it.
>> Problem is, library implementors tend to be extremely loath to rely on anything smelling of UB in their implementations.
>> my $.02,
>> –Arthur
> This is well-defined. A pointer to the first non-static data member of a struct is pointer-convertible with a pointer to the struct.

True. But is the `T` the first NSDM in the struct? For a linked-list
style node, the pointer(s) might come before `T`. And as LL pointed
out, is the iterator type standard layout? Might that not depend on
`T` itself being standard layout?

And as Arthur pointed out, `deque` just can't do it (in O(1)). And
`deque` is not the only kind of container where this conversion isn't
really possible. A segmented stack (kind of like `vector` but
non-contiguous. You have a linked list of contiguous blocks of
ever-increasing numbers of `T`s, which gives you optimal push/pop
performance) can't go from a reference to a `T` to an iterator into
the stack.

If this is a thing that needs to happen, I'd say that it has to be
allowed on a case-by-case basis, just like many other container
functions like `push_back` and such.

Received on 2020-08-13 16:04:32