Next: , Previous: , Up: Particular Modules   [Contents][Index]


15.11 Container data types

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

Data typeDetailsModuleMain include fileInclude file for operations with out-of-memory checking
Sequential listCan contain any number of objects in any given order. Duplicates are allowed, but can optionally be forbidden.list"gl_list.h""gl_xlist.h"
SetCan 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 setCan 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"
MapCan 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 mapCan 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:

OperationARRAYCARRAYLINKEDTREELINKEDHASH with duplicatesLINKEDHASH without duplicatesTREEHASH with duplicatesTREEHASH without duplicates
gl_list_sizeO(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)
gl_list_node_valueO(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)
gl_list_node_set_valueO(1)O(1)O(1)O(1)O(1)O(1)O((log n)2)O(1)
gl_list_next_nodeO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_list_previous_nodeO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_list_get_atO(1)O(1)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_list_get_firstO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_list_get_lastO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_list_set_atO(1)O(1)O(n)O(log n)O(n)O(n)O((log n)2)O(log n)
gl_list_set_firstO(1)O(1)O(1)O(log n)O(n)O(1)O((log n)2)O(log n)
gl_list_set_lastO(1)O(1)O(1)O(log n)O(n)O(1)O((log n)2)O(log n)
gl_list_searchO(n)O(n)O(n)O(n)O(n)O(1)O(log n)O(1)
gl_list_search_fromO(n)O(n)O(n)O(n)O(n)O(1)O((log n)2)O(log n)
gl_list_search_from_toO(n)O(n)O(n)O(n)O(n)O(1)O((log n)2)O(log n)
gl_list_indexofO(n)O(n)O(n)O(n)O(n)O(n)O(log n)O(log n)
gl_list_indexof_fromO(n)O(n)O(n)O(n)O(n)O(n)O((log n)2)O(log n)
gl_list_indexof_from_toO(n)O(n)O(n)O(n)O(n)O(n)O((log n)2)O(log n)
gl_list_add_firstO(n)O(1)O(1)O(log n)O(1)O(1)O((log n)2)O(log n)
gl_list_add_lastO(1)O(1)O(1)O(log n)O(1)O(1)O((log n)2)O(log n)
gl_list_add_beforeO(n)O(n)O(1)O(log n)O(1)O(1)O((log n)2)O(log n)
gl_list_add_afterO(n)O(n)O(1)O(log n)O(1)O(1)O((log n)2)O(log n)
gl_list_add_atO(n)O(n)O(n)O(log n)O(n)O(n)O((log n)2)O(log n)
gl_list_remove_nodeO(n)O(n)O(1)O(log n)O(n)O(1)O((log n)2)O(log n)
gl_list_remove_atO(n)O(n)O(n)O(log n)O(n)O(n)O((log n)2)O(log n)
gl_list_remove_firstO(n)O(1)O(1)O(log n)O(n)O(1)O((log n)2)O(log n)
gl_list_remove_lastO(1)O(1)O(1)O(log n)O(n)O(1)O((log n)2)O(log n)
gl_list_removeO(n)O(n)O(n)O(n)O(n)O(1)O((log n)2)O(log n)
gl_list_iteratorO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_list_iterator_from_toO(1)O(1)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_list_iterator_nextO(1)O(1)O(1)O(log n)O(1)O(1)O(log n)O(log n)
gl_sortedlist_searchO(log n)O(log n)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_sortedlist_search_fromO(log n)O(log n)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_sortedlist_indexofO(log n)O(log n)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_sortedlist_indexof_fromO(log n)O(log n)O(n)O(log n)O(n)O(n)O(log n)O(log n)
gl_sortedlist_addO(n)O(n)O(n)O(log n)O(n)O(n)O((log n)2)O(log n)
gl_sortedlist_removeO(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:

OperationARRAYLINKEDHASH, HASH
gl_set_sizeO(1)O(1)
gl_set_addO(n)O(1)
gl_set_removeO(n)O(1)
gl_set_searchO(n)O(1)
gl_set_iteratorO(1)O(1)
gl_set_iterator_nextO(1)O(1)

The implementations and the guaranteed average performance for the operations for the “ordered set” data type are:

OperationARRAYTREE
gl_oset_sizeO(1)O(1)
gl_oset_addO(n)O(log n)
gl_oset_removeO(n)O(log n)
gl_oset_searchO(log n)O(log n)
gl_oset_search_atleastO(log n)O(log n)
gl_oset_iteratorO(1)O(log n)
gl_oset_iterator_nextO(1)O(log n)

The implementations and the guaranteed average performance for the operations for the “map” data type are:

OperationARRAYLINKEDHASH, HASH
gl_map_sizeO(1)O(1)
gl_map_getO(n)O(1)
gl_map_putO(n)O(1)
gl_map_removeO(n)O(1)
gl_map_searchO(n)O(1)
gl_map_iteratorO(1)O(1)
gl_map_iterator_nextO(1)O(1)

The implementations and the guaranteed average performance for the operations for the “ordered map” data type are:

OperationARRAYTREE
gl_omap_sizeO(1)O(1)
gl_omap_getO(log n)O(log n)
gl_omap_putO(n)O(log n)
gl_omap_removeO(n)O(log n)
gl_omap_searchO(log n)O(log n)
gl_omap_search_atleastO(log n)O(log n)
gl_omap_iteratorO(1)O(log n)
gl_omap_iterator_nextO(1)O(log n)

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

Data typeC++ classModuleInclude file
Sequential listgl_Listlist-c++"gl_list.hh"
Setgl_Setset-c++"gl_set.hh"
Ordered setgl_OSetoset-c++"gl_oset.hh"
Mapgl_Mapmap-c++"gl_map.hh"
Ordered mapgl_OMapomap-c++"gl_omap.hh"

Next: , Previous: , Up: Particular Modules   [Contents][Index]