-
Notifications
You must be signed in to change notification settings - Fork 7
queue
Defined in header <ctl/queue.h>, CTL prefix queue, derived from deque.
#undef POD
#define T int
#include <ctl/queue.h>
queue_int a = queue_int_init ();
for (int i=0; i<rand(); i++)
queue_int_push (&a, i);
for (int i=0; i<rand(); i++)
queue_int_pop (&a); // ignores empty queue
queue_int_free(&a);
The queue is a container adapter that gives the programmer the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.
The header acts as a wrapper to the underlying container - only a specific set of functions is provided. The queue pushes the elements on the back of the underlying container and pops them from the front.
The function names are composed of the prefix queue_, the user-defined type
T and the method name. E.g queue_int with #define T int.
As opposed to vector, the elements of a queue are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to queue must perform two pointer dereferences, compared to vector's indexed access which performs only one.
The storage of a queue is automatically expanded and contracted as needed. Expansion of a queue is cheaper than the expansion of a vector because it does not involve copying of the existing elements to a new memory location. On the other hand, queues typically have large minimal memory cost; a queue holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++).
T value type
A being queue_T container type
B being queue_T_node node type
I being queue_T_it iterator type
init ()
constructs the queue.
free (A* self)
destructs the queue.
copy (A* self)
returns a copy of the container.
front (A* self)
access the first element
back (A* self)
access the last element
empty (A* self)
checks whether the container is empty
size (A* self)
returns the number of elements
max_size ()
returns the maximum possible number of elements
shrink_to_fit (A* self)
reduces memory usage by freeing unused memory.
push (A* self, T value)
Push element to the end
emplace (A* self, T values...)
Push elements to the end. C++11, NYI
pop (A* self)
Removes the first element
swap (A* self, A* other)
Swaps the contents
find (A* self, T value)
finds element with specific value
equal (A* self, A* other, int T_equal(T*, T*))
Returns 0 or 1 if all elements are equal.