Overview

In this article

• Overview
• std collections
  • Sequence collections
  • Associative collections
  • Unordered associative collections
  • Collections adaptors
• xtd collections
  • Collections with events
  • Specialized collections
  • Thread-safe collections
• Choose a collection
• Algorithmic complexity of collections

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.

Container	Definition
std::array	Represents a static contiguous array.
std::vector	Represents a sdynamic contiguous array.
std::deque	Represents a sdouble-ended queue.
std::forward_list	Represents a ssingly-linked list.
std::list	Represents a sdoubly-linked list.

Associative collections

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

Container	Definition
std::set	Represents a scollection of unique keys, sorted by keys.
std::map	Represents a scollection of key-value pairs, sorted by keys, keys are unique.
std::multiset	Represents a scollection of keys, sorted by keys.
std::multimap	Represents 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).

Container	Definition
std::unordered_set	Represents a scollection of unique keys, hashed by keys.
std::unordered_map	Represents a scollection of key-value pairs, hashed by keys, keys are unique.
std::unordered_multiset	Represents a scollection of keys, hashed by keys.
std::unordered_multimap	Represents a scollection of key-value pairs, hashed by keys.

Container adaptors

Container adaptors provide a different interface for sequential collections.

Container	Definition
std::stack	Adapts a container to provide stack (LIFO data structure).
std::queue	Adapts a container to provide queue (FIFO data structure).
std::priority_queue	Adapts a container to provide priority queue.
std::flat_set	Adapts a container to provide a collection of unique keys, sorted by keys.
std::flat_map	Adapts two collections to provide a collection of key-value pairs, sorted by unique keys.
std::flat_multiset	Adapts a container to provide a collection of keys, sorted by keys.
std::flat_multimap	Adapts two collections to provide a collection of key-value pairs, sorted by keys.

xtd collections

Collections with events

Container	Definition
arranged_element_collection	Represents 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.

Container	Definition
xtd::collections::hash_table	Represents a collection of key/value pairs that are organized based on the hash code of the key.
xtd::collections::queue	Represents a first-in, first-out collection of objects.
xtd::collections::stack	Represents a simple last-in-first-out (LIFO) non-generic collection of objects.
xtd::collections::vector_list	Represents a collection of std::any.
xtd::collections::specialized::string_map	Implements a std::map with the key and the value strongly typed to be strings.
xtd::collections::specialized::string_vector	Represents a collection of strings.

Thread-safe collections

Thread-safe collections can be used for multithreading.

Container	Definition
xtd::collections::concurrent::concurrent_bag	Represents a thread-safe, unordered collection of objects.
xtd::collections::concurrent::concurrent_queue	Represents a thread-safe first in-first out (FIFO) collection.
xtd::collections::concurrent::concurrent_map	Represents a thread-safe collection of key/value pairs that can be accessed by multiple threads concurrently.
xtd::collections::concurrent::concurrent_stack	RepRepresents 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 options	Non-generic collection options	Thread-safe collection options
Store items as key/value pairs for quick look-up by key	std::map std::unordered_map	xtd::collections::hash_table	xtd::collections::concurrent::concurrent_map
Access items by index	std::vector std::array	xtd::collections::vector_list	xtd::collections::concurrent::concurrent_map
Use items first-in-first-out (FIFO)	std::queue	xtd::collections::queue	xtd::collections::concurrent::concurrent_queue
Use data Last-In-First-Out (LIFO)	std::stack	xtd::collections::stack	xtd::collections::concurrent::concurrent_stack
Access items sequentially	std::list	No recommendation	No recommendation
A set for mathematical functions	std::set std::unordered_set	No recommendation	No 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.

Operation	Amortized	Worst Case
std::stack<type_t>::push	O(1)	O(n)
std::queue<type_t>::push	O(1)	O(n)
std::vector<type_t>::push_back	O(1)	O(n)
std::vector<type_t>::operator[size_t]	O(1)	O(1)
std::vector<type_t>::iterator	O(n)	O(n)
std::unordered_set<type_t>::insert	O(1)	O(n)
std::unordered_set<type_t>::find	O(1)	O(n)
std::set<type_t>::insert	O(log n)	O(n)
std::unordered_map<type_t>::insert	O(1)	O(n)
std::unordered_map<type_t>::find	O(1)	O(1) – or strictly O(n)
std::map<type_t>::insert	O(log n)	O(n log n)

See also

​

• Guides
• Documentation