3 ms·

I thought a resizable ring buffer was a valid implementation, but maybe I'm thinking of Rust's VecDeque and there's something about the semantics of std::deque

I thought a resizable ring buffer was a valid implementation, but maybe I'm thinking of Rust's VecDeque and there's something about the semantics of std::deque that doesn't allow that.

kadoban 5y ago
I don't think insert at front/back is allowed an amortized bound, it has to be flat constant. But then I don't see how libc++'s is conforming if this article is true, so I'm not entirely sure what's going on there.
mgaunard 5y ago
How could you make any operation O(1) with resizing?
- monocasa 5y ago
  Amortized O(1)
  - mgaunard 5y ago
    Amortized O(1) does not satisfy the specified requirements.
    - monocasa 5y ago
      Oh, ok, it used to be amortized constant O(1), but changed at some point apparently. https://web.archive.org/web/20150310134852/https://en.cppreference.com/w/cpp/container/deque https://web.archive.org/web/20150310134852/https://en.cppref...
      - mgaunard 5y ago
        That's an error that this website did. It's not an authoritative source. It's always been non-amortized since 1998.
- rav 5y ago
  It is possible to deamortize the O(n) resizing step, meaning you spend O(1) extra time over the O(n) operations leading to the resize, so that when the resize needs to happen, you don't need to spend O(n) time. This assumes that allocation/deallocation takes O(1) time regardless of the buffer size. Deamortized resizing can work as follows: When inserting into a vector that is half full, allocate a new buffer twice the size and copy two elements into the buffer. For the subsequent insertions, copy two elements every time you insert one element. This guarantees that you are done copying all elements into the new buffer once the old buffer is full, and you only performed a constant number of instructions with each operation. It's possible to deamortize many quite advanced data structures in theory - see e.g. the lecture notes on "Maintaining Order in a List" on this course webpage: https://cs.au.dk/~gerth/aa11/ https://cs.au.dk/~gerth/aa11/ ... but as with everything in theoretical computer science you are not guaranteed that the implementation works better in practice than the "naive" approach. Deamortization techniques do have a lot of practical relevance in hard realtime applications, but I don't know how much of "real" hard realtime stuff uses academic techniques and how much of it is mostly engineering.
monocasa 5y ago
Ohhhh, I think I found the issue with a ring buffer implementation. Would edit my post if I was in the edit window. resize() doesn't invalidate existing references in std::deque.

I thought a resizable ring buffer was a valid implementation, but maybe I'm thinking of Rust's VecDeque and there's something about the semantics of std::deque that doesn't allow that.

kadoban 5y ago

I don't think insert at front/back is allowed an amortized bound, it has to be flat constant. But then I don't see how libc++'s is conforming if this article is true, so I'm not entirely sure what's going on there.

mgaunard 5y ago

How could you make any operation O(1) with resizing?

monocasa 5y ago
Amortized O(1)
- mgaunard 5y ago
  Amortized O(1) does not satisfy the specified requirements.
  - monocasa 5y ago
    Oh, ok, it used to be amortized constant O(1), but changed at some point apparently. https://web.archive.org/web/20150310134852/https://en.cppreference.com/w/cpp/container/deque https://web.archive.org/web/20150310134852/https://en.cppref...
    - mgaunard 5y ago
      That's an error that this website did. It's not an authoritative source. It's always been non-amortized since 1998.
rav 5y ago
It is possible to deamortize the O(n) resizing step, meaning you spend O(1) extra time over the O(n) operations leading to the resize, so that when the resize needs to happen, you don't need to spend O(n) time. This assumes that allocation/deallocation takes O(1) time regardless of the buffer size. Deamortized resizing can work as follows: When inserting into a vector that is half full, allocate a new buffer twice the size and copy two elements into the buffer. For the subsequent insertions, copy two elements every time you insert one element. This guarantees that you are done copying all elements into the new buffer once the old buffer is full, and you only performed a constant number of instructions with each operation. It's possible to deamortize many quite advanced data structures in theory - see e.g. the lecture notes on "Maintaining Order in a List" on this course webpage: https://cs.au.dk/~gerth/aa11/ https://cs.au.dk/~gerth/aa11/ ... but as with everything in theoretical computer science you are not guaranteed that the implementation works better in practice than the "naive" approach. Deamortization techniques do have a lot of practical relevance in hard realtime applications, but I don't know how much of "real" hard realtime stuff uses academic techniques and how much of it is mostly engineering.

monocasa 5y ago

Ohhhh, I think I found the issue with a ring buffer implementation. Would edit my post if I was in the edit window. resize() doesn't invalidate existing references in std::deque.