cqueue

cqueue is a C++20 header-only circular queue container.

Statement	Length	Reserved	Content
`cqueue<int> queue;`	`0`	`0`	`-`
`queue.push(1);`	`1`	`8`	➊☉☉☉☉☉☉☉
`queue.push(2);`	`2`	`8`	➊➁☉☉☉☉☉☉
`queue.push(3);`	`3`	`8`	➊➁➂☉☉☉☉☉
`queue.pop();`	`2`	`8`	☉➋➂☉☉☉☉☉
`x = queue[1]; // = 3`	`2`	`8`	`= buffer[(1+1)%8]`
`for (int i = 4; i <= 8; ++i)` `queue.push(i);`	`7`	`8`	☉➋➂➃➄➅➆➇
`queue.push(9);`	`8`	`8`	➈➋➂➃➄➅➆➇
`queue.push(10);`	`9`	`16`	➋➂➃➄➅➆➇➈➉☉☉☉☉☉☉☉
`queue.clear();`	`0`	`16`	☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉☉

cqueue is similar to a std::vector

Random access iterators
Dynamic memory management
Constant time on access, insert and erase operations
No external dependences
Not thread-safe

... but it behaves like a queue

push() add an element at the end
pop() remove the first element
Cannot insert or remove items in the middle

... where

Items are stored 'modulus' n (queue[pos] = buffer[(mFront+pos)%mReserved])
Memory new/delete calls are minimized

... having some extras

Access index always is checked
push_front() support
pop_back() support

... and some lacks

Comparison operators currently not supported
Restricted to C++20 compilers

Motivation

Memory management (alloc/free) done by std::deque is very intense in queue-like operations (push/pop). deque-prof.cpp and cqueue-prof.cpp implements a trivial use case of a queue where we push n items and pop n items repeatedly.

Using std::deque:

> valgrind --leak-check=full --show-leak-kinds=all ./deque-prof
...
==10003== HEAP SUMMARY:
==10003==     in use at exit: 0 bytes in 0 blocks
==10003==   total heap usage: 156,253 allocs, 156,253 frees, 80,073,280 bytes allocated
...

Using gto:cqueue:

> valgrind --leak-check=full --show-leak-kinds=all ./cqueue-prof
...
==10024== HEAP SUMMARY:
==10024==     in use at exit: 0 bytes in 0 blocks
==10024==   total heap usage: 4 allocs, 4 frees, 72,928 bytes allocated
...

Usage

Drop off cqueue.hpp in your project and start using the cqueue.

Read cqueue-example.cpp file to see how to use it.

Testing

# example
make example

# unit tests
make tests

# code coverage
make coverage
firefox coverage/index.html &

Contributors

Name	Contribution
Gerard Torrent	Initial work Code maintainer
G. Sliepen	Code review (I) Code review (II)
Toby Speight	Code review (II)
372046933	Fix compile Fix performance issue

License