Skip to main content


In this article

xtd mainly uses std collections. To complete the std, xtd implements some owner collections.

std collections

Sequence collections

Sequence collections implement data structures which can be accessed sequentially.

std::arrayRepresents a static contiguous array.
std::vectorRepresents a sdynamic contiguous array.
std::dequeRepresents a sdouble-ended queue.
std::forward_listRepresents a ssingly-linked list.
std::listRepresents a sdoubly-linked list.

Associative collections

Associative collections implement sorted data structures that can be quickly searched (O(log n) complexity).

std::setRepresents a scollection of unique keys, sorted by keys.
std::map Represents a scollection of key-value pairs, sorted by keys, keys are unique.
std::multisetRepresents a scollection of keys, sorted by keys.
std::multimapRepresents a scollection of key-value pairs, sorted by keys.

Unordered associative collections

Unordered associative collections implement unsorted (hashed) data structures that can be quickly searched (O(1) average, O(n) worst-case complexity).

std::unordered_setRepresents a scollection of unique keys, hashed by keys.
std::unordered_mapRepresents a scollection of key-value pairs, hashed by keys, keys are unique.
std::unordered_multisetRepresents a scollection of keys, hashed by keys.
std::unordered_multimapRepresents a scollection of key-value pairs, hashed by keys.

Container adaptors

Container adaptors provide a different interface for sequential collections.

std::stackAdapts a container to provide stack (LIFO data structure).
std::queueAdapts a container to provide queue (FIFO data structure).
std::priority_queueAdapts a container to provide priority queue.
std::flat_setAdapts a container to provide a collection of unique keys, sorted by keys.
std::flat_mapAdapts two collections to provide a collection of key-value pairs, sorted by unique keys.
std::flat_multisetAdapts a container to provide a collection of keys, sorted by keys.
std::flat_multimapAdapts two collections to provide a collection of key-value pairs, sorted by keys.

xtd collections

Collections with events

arranged_element_collectionRepresents a collection with events to which you can connect.

Remarks The arranged_element_collection Collections is overloaded in various classes such as control, list_control, tab_control, status_bar, tool_bar, ...

Specialized collections

Specialized and strongly-typed collections.

xtd::collections::hash_tableRepresents a collection of key/value pairs that are organized based on the hash code of the key.
xtd::collections::queueRepresents a first-in, first-out collection of objects.
xtd::collections::stackRepresents a simple last-in-first-out (LIFO) non-generic collection of objects.
xtd::collections::vector_listRepresents a collection of std::any.
xtd::collections::specialized::string_mapImplements a std::map with the key and the value strongly typed to be strings.
xtd::collections::specialized::string_vectorRepresents a collection of strings.

Thread-safe collections

Thread-safe collections can be used for multithreading.

xtd::collections::concurrent::concurrent_bagRepresents a thread-safe, unordered collection of objects.
xtd::collections::concurrent::concurrent_queueRepresents a thread-safe first in-first out (FIFO) collection.
xtd::collections::concurrent::concurrent_mapRepresents a thread-safe collection of key/value pairs that can be accessed by multiple threads concurrently.
xtd::collections::concurrent::concurrent_stackRepRepresents a thread-safe last in-first out (LIFO) collection.

Remarks Not yet implemented, but coming soon.

Choose a collection

In general, you should use generic collections. The following table describes some common collection scenarios and the collection classes you can use for those scenarios. If you're new to generic collections, the following table will help you choose the generic collection that works best for your task:

 I want to…Generic collection optionsNon-generic collection optionsThread-safe collection options
Store items as key/value pairs for quick look-up by keystd::map
Access items by indexstd::vector
Use items first-in-first-out (FIFO)std::queuextd::collections::queuextd::collections::concurrent::concurrent_queue
Use data Last-In-First-Out (LIFO)std::stackxtd::collections::stackxtd::collections::concurrent::concurrent_stack
Access items sequentiallystd::listNo recommendationNo recommendation
A set for mathematical functionsstd::set
No recommendationNo recommendation

Algorithmic complexity of collections

Lors du choix d'une classe de collection, il convient de tenir compte des compromis possibles en termes de performances. Utilisez le tableau suivant pour comparer la complexité algorithmique de divers types de collection.

OperationAmortizedWorst Case
std::set<type_t>::insertO(log n)O(n)
std::unordered_map<type_t>::findO(1)O(1) – or strictly O(n)
std::map<type_t>::insertO(log n)O(n log n)

See also