Hacker News Reader

Comment by dehrmann | Hacker News Reader

> Unlike std::deque, which uses a fragmented block-based structure

I always assumed deque implementations were ring buffers that double in size once full so that prepend/append operations are amortized O(1).

View on HN

No, that's what Rust's VecDeque is, the C++ std::deque is something which you wouldn't invent today, but alas C++ is wedded to how things were done in the 1990s sometimes before.

std::deque does have practical uses, but they're rare and many implementations aren't well suited even to those uses. Unlike VecDeque most people should just ignore it.

> the C++ std::deque is something which you wouldn't invent today,

Why is that?

My major issue with std::deque is that the standard implementation doesn't provide a) a way to define the block size, b) a way to access the single blocks for optimizations. The deque in boost.container provides the former. I don't know if any widely available implementation provides the latter (segmented iterators were first proposed around the original C++ standardization, but it seems that were never picked up).

IDK, I thought the whole point of a deque was to string vectors into a linked list, so you get benefits of both, the most important ones being 1) cheap random access, and 2) insertion doesn't move stuff around in memory. I.e. that the deque's "vectors connected by pointers" is not an implementation detail, but the very nature of the beast.

Maybe I just took the boxes-and-arrows diagrams from C++ books too seriously.

Yes, I agree, insertion not moving things is a very useful feature of deques. It allows you to keep items with deleted copy and move constructors in a container that has good cache locality.

deque does not move elements once added, so it can’t be implemented like that.

Is that an actual guarantee or just the current implementation? I'd expected that at the very least some functions that can operate on std::deque must require moves. erase_if immediately comes to mind.

https://en.cppreference.com/w/cpp/container/deque:

> When inserting at either end of the deque, references are not invalidated by insert and emplace.

> push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.

That's a guarantee of some specific operations on deque not a general requirement on the entirety of deque. I looked at your link and erase_if does not have that requirement. So I'd imagine that can and does invalidate references aka move elements.

Right, indeed, amluto's comment is incorrectly broad. But it's still a thing that a ring buffer cannot guarantee, but std::deque impls must.

std::deque typically uses chunked arrays. It is more complex but tends to be faster than a ring buffer based implementation.

That's what I learned in my university data structures course. I don't know anything about C++'s std::deque though.

Reply on news.ycombinator.com