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

This project is licensed under the GNU LGPL v3 License - see the LICENSE file for details.