C++11, STL-like API, bidirectional iterator, one memory allocation in the circular buffer.
push - O(n/2)
pop - O(1)
min - O(1)
median - O(1)
max - O(1)
The container is well suited in cases where you need to constantly receive min, max, median elements with the constantly insertion of new data (points).
MSVC142x64, Kaby Lake, 3.88 GHz
- Container initialization
sorted_flat_deque<int32_t> deque;
╔═══╤═══╤═══╤═══╗
deque.set_max_size(4); ║ │ │ │ ║ // internal circular buffer
╚═══╧═══╧═══╧═══╝- Pushing items
╔═══╤═══╤═══╤═══╗
deque.push_back(7); ║ 7 │ │ │ ║
╚═══╧═══╧═══╧═══╝
╔═══╤═══╤═══╤═══╗
deque.push_back(2); ║ 7f│ 2b│ │ ║ // b - back position, f - front position
╚═══╧═══╧═══╧═══╝
╔═══╤═══╤═══╤═══╗
deque.push_back(6); ║ 7f│ 2 │ 6b│ ║
╚═══╧═══╧═══╧═══╝
╔═══╤═══╤═══╤═══╗
deque.push_back(1); ║ 7f│ 2 │ 6 │ 1b║
╚═══╧═══╧═══╧═══╝
╔═══╤═══╤═══╤═══╗
deque.push_back(3); ║ 3b│ 2f│ 6 │ 1 ║ // element '7' was automatically removed from front
╚═══╧═══╧═══╧═══╝- Accessing to
min,maxormedianelements
for (auto it = deque.cbegin(); it != deque.cend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl; // 1 2 3 6
deque.min(); // 1
deque.median(); // 2
deque.max(); // 6
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent