Skip to content

C++11, STL-like API, bidirectional iterator, min, max, median, one memory allocation in the circular buffer.

License

Notifications You must be signed in to change notification settings

yurablok/sorted_flat_deque

Repository files navigation

sorted_flat_deque

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)

Applicability:

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).

Benchmark result:

MSVC142x64, Kaby Lake, 3.88 GHz
benchmark result

Principle of usage:

  1. Container initialization
sorted_flat_deque<int32_t> deque;
                       ╔═══╤═══╤═══╤═══╗
deque.set_max_size(4); ║   │   │   │   ║  // internal circular buffer
                       ╚═══╧═══╧═══╧═══╝
  1. Pushing items
                    ╔═══╤═══╤═══╤═══╗
deque.push_back(7); ║ 7 │   │   │   ║
                    ╚═══╧═══╧═══╧═══╝
                    ╔═══╤═══╤═══╤═══╗
deque.push_back(2); ║ 7f│ 2b│   │   ║ // b - back position, f - front position
                    ╚═══╧═══╧═══╧═══╝
                    ╔═══╤═══╤═══╤═══╗
deque.push_back(6); ║ 7f2 │ 6b│   ║
                    ╚═══╧═══╧═══╧═══╝
                    ╔═══╤═══╤═══╤═══╗
deque.push_back(1); ║ 7f26 │ 1b║
                    ╚═══╧═══╧═══╧═══╝
                    ╔═══╤═══╤═══╤═══╗
deque.push_back(3); ║ 3b│ 2f61// element '7' was automatically removed from front
                    ╚═══╧═══╧═══╧═══╝
  1. Accessing to min, max or median elements
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

About

C++11, STL-like API, bidirectional iterator, min, max, median, one memory allocation in the circular buffer.

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published