Deque implementation review about eastl HOT 5 CLOSED

This post got the wrong qualifier. It's actually two suggested enhancements and one bug (or major inefficiency at least, since move won't guarantee a move but may very well copy when dealing with legacy code or something that doesn't satisfy Movable).

Please re-read my post, or, if it's too long, just re-read your code I cited above and keep in mind that deque::emplace_back should never ever change the memory locations of elements already in the container.

from eastl.

For emplace_back, its not clear to me what change you are suggesting? I'd agree this code is subtle and I'm not exactly sure what guarantee the standards give for moving elements that originate from within the container. I'd have to read up on that.

from eastl.

I'm not exactly sure what guarantee standards give for moving elements that originate from within the container. I'd have to read up on that.

<cite, from the second link to stackoverflow given above>
§23.2.1.3 guarantees that while iterators into the dequeue are invalidated, pointers and references to the elements are still valid: An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.
</cite>

So there would be the paragraph to verify.

This means that deque::emplace_back must never reallocate the objects, it may have to do so for the bookkeeping data, but that's about how far it goes (other than std::vector::emplace_back which will eventually relocate the objects).

For emplace_back, its not clear to me what change you are suggesting?

Get rid of that subtle and inefficient dance and just go

if need be {
   grow container
}
call placement new with the reference which must still be valid, no matter what

In fact, I guess you can just delete the overload and let the variadic version do the right thing :-).

from eastl.

This reallocation issue has become even more relevant since C++17's emplace_back finally returns a reference to the inserted object.

template< class... Args >
reference emplace_back( Args&&... args );

It is unfortunate that vagaries such as this (and I'm not referring to your library here, I had an issue with MSVC's std::unordered_map changing references) have led to me habitually using a std::list to store data when I need to be sure the reference will remain unchanged, and using (e.g.) std::unordered_map as an index into std::list.

My only suggestion would be that it be strongly documented that your class does not comply with (as phrased at http://en.cppreference.com/w/cpp/container/deque/emplace_back) - "No references are invalidated." (If this is indeed the case).

from eastl.

It seems interest hasn't picked up on this ticket. Please re-open with additional information and/or provide a PR for specific changes you would like to see.

from eastl.