Container data types
====================

Gnulib provides several generic container data types.  They can be used to organize collections of application-defined objects.

Data type
Details
Module
Main include file
Include file for operations with out-of-memory checking
Sequential list
Can contain any number of objects in any given order.
Duplicates are allowed, but can optionally be forbidden.
list
"gl_list.h"
"gl_xlist.h"
Set
Can contain any number of objects; the order does not matter.
Duplicates (in the sense of the comparator) are forbidden.
set
"gl_set.h"
"gl_xset.h"
Ordered set
Can contain any number of objects in the order of a given comparator
function.
Duplicates (in the sense of the comparator) are forbidden.
oset
"gl_oset.h"
"gl_xoset.h"
Map
Can contain any number of (key, value) pairs, where keys and values
are objects;
there are no (key, value1) and (key, value2) pairs with the same key
(in the sense of a given comparator function).
map
"gl_map.h"
"gl_xmap.h"
Ordered map
Can contain any number of (key, value) pairs, where keys and values
are objects;
the (key, value) pairs are ordered by the key, in the order of a given
comparator function;
there are no (key, value1) and (key, value2) pairs with the same key
(in the sense of the comparator function).
omap
"gl_omap.h"
"gl_xomap.h"

Operations without out-of-memory checking (suitable for use in libraries) are declared in the ``main include file''.  Whereas operations with out-of-memory checking (suitable only in programs) are declared in the ``include file for operations with out-of-memory checking''.

For each of the data types, several implementations are available, with different performance profiles with respect to the available operations. This enables you to start with the simplest implementation (ARRAY) initially, and switch to a more suitable implementation after profiling your application. The implementation of each container instance is specified in a single place only: in the invocation of the function gl_*_create_empty that creates the instance.

The implementations and the guaranteed average performance for the operations for the ``sequential list'' data type are:

Operation
ARRAY
CARRAY
LINKED
TREE
LINKEDHASH with duplicates
LINKEDHASH without duplicates
TREEHASH with duplicates
TREEHASH without duplicates
gl_list_size
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
gl_list_node_value
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
gl_list_node_set_value
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O((log n)^2)
O(1)
gl_list_next_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_previous_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_get_at
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_set_at
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_search
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(log n)
O(1)
gl_list_search_from
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_search_from_to
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_indexof
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_indexof_from
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_indexof_from_to
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_add_first
O(n)
O(1)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_last
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_before
O(n)
O(n)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_after
O(n)
O(n)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_at
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_remove_node
O(n)
O(n)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_remove_at
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_remove
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_iterator
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_iterator_from_to
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_iterator_next
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_sortedlist_search
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_search_from
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_indexof
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_indexof_from
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_add
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_sortedlist_remove
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)

The implementations and the guaranteed average performance for the operations for the ``set'' data type are:

Operation
ARRAY
LINKEDHASH, HASH
gl_set_size
O(1)
O(1)
gl_set_add
O(n)
O(1)
gl_set_remove
O(n)
O(1)
gl_set_search
O(n)
O(1)
gl_set_iterator
O(1)
O(1)
gl_set_iterator_next
O(1)
O(1)

The implementations and the guaranteed average performance for the operations for the ``ordered set'' data type are:

Operation
ARRAY
TREE
gl_oset_size
O(1)
O(1)
gl_oset_add
O(n)
O(log n)
gl_oset_remove
O(n)
O(log n)
gl_oset_search
O(log n)
O(log n)
gl_oset_search_atleast
O(log n)
O(log n)
gl_oset_iterator
O(1)
O(log n)
gl_oset_iterator_next
O(1)
O(log n)

The implementations and the guaranteed average performance for the operations for the ``map'' data type are:

Operation
ARRAY
LINKEDHASH, HASH
gl_map_size
O(1)
O(1)
gl_map_get
O(n)
O(1)
gl_map_put
O(n)
O(1)
gl_map_remove
O(n)
O(1)
gl_map_search
O(n)
O(1)
gl_map_iterator
O(1)
O(1)
gl_map_iterator_next
O(1)
O(1)

The implementations and the guaranteed average performance for the operations for the ``ordered map'' data type are:

Operation
ARRAY
TREE
gl_omap_size
O(1)
O(1)
gl_omap_get
O(log n)
O(log n)
gl_omap_put
O(n)
O(log n)
gl_omap_remove
O(n)
O(log n)
gl_omap_search
O(log n)
O(log n)
gl_omap_search_atleast
O(log n)
O(log n)
gl_omap_iterator
O(1)
O(log n)
gl_omap_iterator_next
O(1)
O(log n)

For C++, Gnulib provides a C++ template class for each of these container data types.

Data type
C++ class
Module
Include file
Sequential list
gl_List
list-c++
"gl_list.hh"
Set
gl_Set
set-c++
"gl_set.hh"
Ordered set
gl_OSet
oset-c++
"gl_oset.hh"
Map
gl_Map
map-c++
"gl_map.hh"
Ordered map
gl_OMap
omap-c++
"gl_omap.hh"