Next: Specialized container data types, Up: Container data types [Contents][Index]
| 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_first_node | O(1) | O(1) | O(1) | O(log n) | O(1) | O(1) | O(log n) | O(log n) |
gl_list_last_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_get_first | O(1) | O(1) | O(1) | O(log n) | O(1) | O(1) | O(log n) | O(log n) |
gl_list_get_last | O(1) | O(1) | O(1) | O(log n) | O(1) | O(1) | 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_set_first | O(1) | O(1) | O(1) | O(log n) | O(n) | O(1) | O((log n)2) | O(log n) |
gl_list_set_last | O(1) | O(1) | O(1) | O(log n) | O(n) | O(1) | 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_first | O(n) | O(1) | O(1) | O(log n) | O(n) | O(1) | O((log n)2) | O(log n) |
gl_list_remove_last | O(1) | O(1) | O(1) | O(log n) | O(n) | O(1) | 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" |
Next: Specialized container data types, Up: Container data types [Contents][Index]