boostorg / boostorg/container

New container: small_deque

Open
#324 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
127
Forks
126
Avg merge
18h 53m
Merged PRs (30d)
1

Description

I propose the addition of `boost::container::small_deque` - a deque container that optimizes for small element counts by storing the first time appeared block in stack memory, similar to the existing `boost::container::small_vector` but maintaining deque semantics with efficient push/pop operations at both ends.

The standard `std::deque` typically performs heap allocations even for small numbers of elements, which can be suboptimal for deque instances which contain few elements.
Existing solutions like `boost::container::small_vector` provide stack optimization but lack efficient O(1) push/pop operations at both ends.

```
std::deque d1 = {1, 2, 3}; // heap
boost::container::small_deque d2 = {1, 2, 3}; // Only stack
boost::container::small_deque d3 = {1, 2, 3, 4, 5}; // stack + heap (at least 20 bytes totaly used)
boost::container::small_vector v1 = {1, 2, 3}; // Only stack
boost::container::small_vector v2 = {1, 2, 3, 4, 5}; // Only heap (at least 36 bytes totally used)

void process(const boost::container::small_deque& items) {
for (int item : items) { // hot path cycle
process_item(item);
}
}
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.