4 ms·
I don't think std::deque's implementation is specified in standard. It only needs to meet certain running times, and the data structure in the article — the aut
by deathanatos 10y ago
I don't think std::deque's implementation is specified in standard. It only needs to meet certain running times, and the data structure in the article — the author's "devector" — would satisfy the requirements of std::deque; i.e., the "devector" is a valid implementation of std::deque, I think. However, in practice, std::deque is not implemented this way — your link hints at this:
> As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.
The usual implementation, I think, looks something like the image here[1].
[1]: http://stackoverflow.com/a/6292437/101999 http://stackoverflow.com/a/6292437/101999
- nightcracker 10y ago> the "devector" is a valid implementation of std::deque, I think It is not. std::deque has strict requirements that say appends/prepends may not invalidate references/iterators. A devector can not guarantee this.
- foota 10y agoNitpick, the operation seems to be allowed to invalidate iterators, though not references. "An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion 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" [1] There might be some cases where it would be practical to simply not free the previously used memory, such that after N increases in size there are N copies of each element. This would only roughly double the space required. [1] C++ working draft, 11 megabytes; http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...
- nightcracker 10y agoAh, I thought it was both, but was just working from the top of my memory. Good for looking it up :)