[container] Proposal for ring queues

Andrey Semashev

21 May 2020 21 May '20

10:17 p.m.

Hi, Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container: https://github.com/boostorg/container/pull/121 The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit. In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03. I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this. If there is interest, what would be the preferred course of action? 1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill. 2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably. Thanks.

Show replies by date

pbristow＠hetp.u-net.com

22 May 22 May

9:17 a.m.

...

-----Original Message----- From: Boost On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List Cc: Andrey Semashev Subject: [boost] [container] Proposal for ring queues

Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.

I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

If there is interest, what would be the preferred course of action?

1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.

2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.

FWIW ... I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be! So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche. Paul PS Some links in the docs of all three libraries should refer to a summary of the various pros and cons and use cases. So users can chose the est/right tool for their project.

degski

23 May 23 May

6:02 p.m.

On Fri, 22 May 2020 at 04:17, Paul A Bristow via Boost < boost@lists.boost.org> wrote:

...

...
-----Original Message----- From: Boost On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List Cc: Andrey Semashev Subject: [boost] [container] Proposal for ring queues

Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.

I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

If there is interest, what would be the preferred course of action?

1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.

2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.

FWIW ...

I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be!

So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche.

What about using *std::circular_list,* an end-to-begin-connected *std::list ?* degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey

Andrey Semashev

6:13 p.m.

On 2020-05-23 21:02, degski via Boost wrote:

...

What about using *std::circular_list,* an end-to-begin-connected *std::list ?*

It doesn't suit the initial intention to minimize the number of memory allocations. And it is less cache-friendly.

degski

6:20 p.m.

On Sat, 23 May 2020 at 13:13, Andrey Semashev via Boost < boost@lists.boost.org> wrote:

...

On 2020-05-23 21:02, degski via Boost wrote:

...
What about using *std::circular_list,* an end-to-begin-connected *std::list ?*

This *plf::list https://www.plflib.org/list.htm* is doing exactly that (allocating in increasingly larger blocks, re-using as possible). It is written on top of *plf::colony*, I seem to remember it was proposed as a Boost addittion but was rejected. degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey

degski

6:53 p.m.

On Sat, 23 May 2020 at 13:20, degski wrote:

...

On Sat, 23 May 2020 at 13:13, Andrey Semashev via Boost < boost@lists.boost.org> wrote:

...
On 2020-05-23 21:02, degski via Boost wrote:

...
What about using *std::circular_list,* an end-to-begin-connected *std::list ?*

This *plf::list https://www.plflib.org/list.htm* is doing exactly that (allocating in increasingly larger blocks, re-using as possible). It is written on top of *plf::colony*, I seem to remember it was proposed as a Boost addition but was rejected.

In case my message still was unclear, very possibly. I'm saying is to create a replacement for std::list, this std::list-v2 is in effect a circular_list, the generalization can be done at no cost and overall the design will/can be better even when viewed as a std::list. degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey

degski

6:14 p.m.

On Sat, 23 May 2020 at 13:02, degski wrote:

...

On Fri, 22 May 2020 at 04:17, Paul A Bristow via Boost < boost@lists.boost.org> wrote:

...
...
-----Original Message----- From: Boost On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List Cc: Andrey Semashev Subject: [boost] [container] Proposal for ring queues

Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.

I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

If there is interest, what would be the preferred course of action?

1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.

2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.

FWIW ...

I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be!

So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche.

What about using *std::circular_list,* an end-to-begin-connected *std::list ?*

Apologies, I meant to write *boost::container::circular_list *an end-to-begin-connected* boost::container::list ?* degski PS: ;) -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey

Mathias Gaunard

22 May 22 May

10:01 a.m.

On Thu, 21 May 2020 at 23:17, Andrey Semashev via Boost wrote:

...

I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

I don't understand the use cases for your container. If I want a queue with bounded capacity, I use a circular buffer. If I want a queue with unbounded capacity, I use std::deque. What's the advantage of your approach compared to std::deque? Assuming a decent state of the art implementation.

Andrey Semashev

10:24 a.m.

On 2020-05-22 13:01, Mathias Gaunard wrote:

...

On Thu, 21 May 2020 at 23:17, Andrey Semashev via Boost wrote:

...
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

I don't understand the use cases for your container. If I want a queue with bounded capacity, I use a circular buffer.

circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it. std::queue and ring queues instead preserve all pushed elements until you dequeue them.

...

If I want a queue with unbounded capacity, I use std::deque.

What's the advantage of your approach compared to std::deque? Assuming a decent state of the art implementation.

As I said, the main advantage is avoiding dynamic memory allocations, which you get with std::queue and std::deque. This can be important if you need a stable latency of push/pop operations or don't want dynamic memory allocations for other reasons.

Mathias Gaunard

11:32 a.m.

On Fri, 22 May 2020, 11:24 Andrey Semashev via Boost, wrote:

...

circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it.

That's just the behaviour when you run out of capacity. Nothing prevents you from checking you're out of capacity and have different behaviour instead. As I said, the main advantage is avoiding dynamic memory allocations You cannot avoid memory allocations if your queue is unbounded. If pre-allocation of some size is a concern you can just use an adequate allocator. For full memory management flexibility one can also build a circular buffer view on a manually managed contiguous piece of memory.

Andrey Semashev

2:08 p.m.

On 2020-05-22 14:32, Mathias Gaunard wrote:

...

On Fri, 22 May 2020, 11:24 Andrey Semashev via Boost, mailto:boost@lists.boost.org> wrote:

circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it.

That's just the behaviour when you run out of capacity. Nothing prevents you from checking you're out of capacity and have different behaviour instead.

Yes, that is a possible workaround, but definitely not the intended use of a circular buffer.

...

As I said, the main advantage is avoiding dynamic memory allocations

You cannot avoid memory allocations if your queue is unbounded.

If pre-allocation of some size is a concern you can just use an adequate allocator.

One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time. However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.

Mathias Gaunard

2:31 p.m.

On Fri, 22 May 2020 at 15:08, Andrey Semashev via Boost wrote:

...

However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.

Nothing prevents you from using a pool allocator with a deque.

Peter Dimov

2:44 p.m.

Mathias Gaunard wrote:

...

Nothing prevents you from using a pool allocator with a deque.

And nothing prevents me from using the proposed ring_queue instead. Do you have a better point than "you can achieve the same effect in a more complicated and stupider way"?

Mathias Gaunard

3:18 p.m.

On Fri, 22 May 2020 at 15:44, Peter Dimov via Boost wrote:

...

Mathias Gaunard wrote:

...
Nothing prevents you from using a pool allocator with a deque.

And nothing prevents me from using the proposed ring_queue instead. Do you have a better point than "you can achieve the same effect in a more complicated and stupider way"?

I don't think combining two well-established generic tools in a way they are meant to be is either of "complicated" or "stupid". Of course you can always roll out something special for every use case. But that comes with a lot of overhead of maintaining it compatible with other components, flexible, efficient and bug-free. Less code is better than more. Ultimately the fact that uses are not too niche or that there is significant value on top of existing solutions are criteria for illegibility for Boost. Not that those criteria are very heavily enforced, as we have a lot of libraries that only target domain specialists, so it's up to how strongly people feel about things.

Andrey Semashev

3:12 p.m.

On 2020-05-22 17:31, Mathias Gaunard wrote:

...

On Fri, 22 May 2020 at 15:08, Andrey Semashev via Boost wrote:

...
However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.

Nothing prevents you from using a pool allocator with a deque.

I agree with Peter in that it is a much more complicated solution. It is likely much less efficient, too. For example, such an allocator has to be prepared that it will be used to allocate buffers of different types and sizes, so it will be difficult to predict, which allocations need to be pooled and which are not. Then the complications from allocator propagation, rebinding, conversion and comparison. It is easier to implement a new container than a non-trivial allocator, really.

Ion Gaztañaga

23 May 23 May

5:08 p.m.

On 22/05/2020 16:08, Andrey Semashev via Boost wrote:

...

One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time.

However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.

Independently from a future Boost.RingQueue or integrated into Boost.CircularBufer (which I think it's be correct module), having a boost::container::deque that conserves capacity (already allocated buffers) so that continuous dynamic allocation does not happen is a nice to have feature. Best, Ion

Bjorn Reese

22 May 22 May

3:08 p.m.

On 2020-05-22 16:08, Andrey Semashev via Boost wrote:

...

One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time.

This corresponds almost to https://github.com/breese/trial.circular/blob/develop/include/trial/circular... This is a circular buffer that operates on an std::vector. Capacity is only increased when the user calls reserve(). It is trivial to write a wrapper on top of this that automatically increases capacity when the buffer is full.

Robert Ramey

23 May 23 May

8:19 p.m.

On 5/21/20 3:17 PM, Andrey Semashev via Boost wrote:

...

Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.

I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.

If there is interest, what would be the preferred course of action?

1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.

2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.

Thanks.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

FWIW - I made a ring_view library as part of my talk on how to document your own library. Interesting features: a) It has almost no features - simplest possible implement b) library user provides his own fixed size storage c) so there's not allocation d) supports any pair of forward iterators. So it isn't dependent on the container type the user might prefer. std::array works just fine. e) it's very simple - just one header file - though it depends on a couple others. f) Documentation is already written! You can download the talk, slides and library here: http://www.rrsd.com/software_development/boost/CppCon%202017/CppCon%202017.z... Robert Ramey

Gavin Lambert

25 May 25 May

3:37 a.m.

On 22/05/2020 10:17, Andrey Semashev wrote:

...

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic). The queue doesn't implement a ring buffer, but can be used as if it did. The spsc_queue actually uses a ring buffer internally. They implement "push fails" if the buffer is full when fixed-capacity, but (provided you use the multi-consumer version, or prevent concurrent access some other way) there's no reason why you couldn't pop and retry if you want overwrite-like behaviour. Usually I personally find that if I care about memory allocation then I care about locking as well. [1]: https://www.boost.org/doc/libs/1_73_0/doc/html/lockfree.html

degski

10:04 a.m.

On Sun, 24 May 2020 at 22:38, Gavin Lambert via Boost wrote:

...

On 22/05/2020 10:17, Andrey Semashev wrote:

...
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic).

I reacted earlier in this thread and was erroneously babbling on about unbounded circular lists. You will say I'm a lousy reader, I on the other hand could not imagine you would not use https://www.threadingbuildingblocks.org/docs/help/reference/containers_overv... for one moment (i.e. that that problem was covered). Is Boost.Lockfree being developed? degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey

Andrey Semashev

10:43 a.m.

On 2020-05-25 06:37, Gavin Lambert via Boost wrote:

...

On 22/05/2020 10:17, Andrey Semashev wrote:

...
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.

Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic).

The obvious difference is that it is lock-free, which is not always needed.

Peter Dimov

15 Jun 15 Jun

3:51 p.m.

Andrey Semashev wrote:

...

Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

Interestingly, the committee is now discussing a proposal to make std::queue constexpr, and it came up that no standard container can ever be used with a constexpr std::queue, because no standard container can have a constexpr pop_front. However, it seems to me that both a "ring deque" and a vector-deque as in DoubleEnded can provide a constexpr pop_front (in C++20.) This might or might not be a sufficient reason to pursue these.

Andrey Semashev

4:08 p.m.

On 2020-06-15 18:51, Peter Dimov via Boost wrote:

...

Andrey Semashev wrote:

...
Hi,

Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:

https://github.com/boostorg/container/pull/121

Interestingly, the committee is now discussing a proposal to make std::queue constexpr, and it came up that no standard container can ever be used with a constexpr std::queue, because no standard container can have a constexpr pop_front.

However, it seems to me that both a "ring deque" and a vector-deque as in DoubleEnded can provide a constexpr pop_front (in C++20.)

This might or might not be a sufficient reason to pursue these.

I see, thanks for the info. I'll see if I can propose ring queues as a separate library then.

Peter Dimov

4:11 p.m.

Andrey Semashev wrote:

...

I see, thanks for the info. I'll see if I can propose ring queues as a separate library then.

I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".

Andrey Semashev

4:18 p.m.

On 2020-06-15 19:11, Peter Dimov via Boost wrote:

...

Andrey Semashev wrote:

...
I see, thanks for the info. I'll see if I can propose ring queues as a separate library then.

I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".

Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...

Peter Dimov

4:31 p.m.

Andrey Semashev wrote:

...

...
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".

Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...

Erasing/inserting at begin()+k for small k will be considerably more efficient than vector.

degski

17 Jun 17 Jun

10:01 a.m.

On Mon, 15 Jun 2020 at 11:32, Peter Dimov via Boost wrote:

...

Andrey Semashev wrote:

...
...
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".

Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...

Erasing/inserting at begin()+k for small k will be considerably more efficient than vector.

Another approach worth exploring in my opinion is *to change 'the allocator' from being a std-node-allocator to being a node=allocator that 'dispenses' from a std::vector.* Such an 'allocator' exists, i.e. 'plf::colony'. Now our LL (the ring) has vector-allocation-patterns behind it [see docs plf::colcony], with an added benefit: the nodes are like with std::allocator never moved. The latter is currently (due to implementation details, which will change) not strictly true, notably reserve() moves objects (reserve() is not usable with non-movable objects), but plf::colony is otherwise well usable for non-movable-non-copyable types (contrary to what is said in the docs). I have written a PoC https://github.com/degski/this_local/blob/b6305194e14de6c6678cea6a847d1aee00... . degski

Gavin Lambert

10:56 p.m.

On 17/06/2020 22:01, degski wrote:

...

Another approach worth exploring in my opinion is *to change 'the allocator' from being a std-node-allocator to being a node=allocator that 'dispenses' from a std::vector.* Such an 'allocator' exists, i.e. 'plf::colony'. Now our LL (the ring) has vector-allocation-patterns behind it [see docs plf::colcony], with an added benefit: the nodes are like with std::allocator never moved. The latter is currently (due to implementation details, which will change) not strictly true, notably reserve() moves objects (reserve() is not usable with non-movable objects), but plf::colony is otherwise well usable for non-movable-non-copyable types (contrary to what is said in the docs). I have written a PoC https://github.com/degski/this_local/blob/b6305194e14de6c6678cea6a847d1aee00...

Using an interface that requires throwing an exception to indicate "buffer full" (due to failure to allocate a new node from a fixed-capacity buffer, and allocators lacking any other means to indicate allocation failure) doesn't seem entirely desirable.

degski

11:07 p.m.

On Wed, 17 Jun 2020 at 17:57, Gavin Lambert via Boost wrote:

...

... and allocators lacking any other means to indicate allocation failure) doesn't seem entirely desirable.

You have to write code that can fail, like sfinae.

1623

Age (days ago)

1650

Last active (days ago)

List overview

Download

28 comments

9 participants

participants (9)

Andrey Semashev
Bjorn Reese
degski
Gavin Lambert
Ion Gaztañaga
Mathias Gaunard
pbristow＠hetp.u-net.com
Peter Dimov
Robert Ramey