Overview

Collections or containers are used to create and manage groups of related objects.

Fixed containers have a fixed capacity. They are useful for creating and working with a fixed number of objects.

Dynamic containers are more flexible. They are used for creating and working with a dynamic number of objects.

Associative containers use keys to uniquely identify objects.

In C++, the standard library provides several types of containers.

In C#, the Collections.Generic namespace provides various collections of objects.

Containers

Array

An array is a static collection of elements.

It's implemented as a fixed single block of memory.

Advantages

• Contiguous memory location (cache-friendly)

• No allocation and deallocation

Disadvantages

• Fixed capacity

• No insertions and erases

Use cases

• Collections of elements

• Capacity is known

• Order is important

• Access by index is important

C++

• std::array

C++/CX

• Platform::Array

C#

• Array

Vector

A vector is a dynamic collection of elements.

It's implemented as a single block of memory.

Advantages

• Contiguous memory location (cache-friendly)

• Few allocations and deallocations

Disadvantages

• Slow insertions and erases

Use cases

• Collections of elements

• Capacity is not known

• Order is important

• Access by index is important

• Few insertions and erases

C++

• std::vector

C++/CX

• Platform::Collections::Vector

C#

• List<T>

List

A list is a dynamic collection of elements.

It's implemented as a double-linked list.

Advantages

• Fast insertions and erases

Disadvantages

• Non contiguous memory location (not cache-friendly)

Use cases

• Collections of elements

• Order is not important

• Access by index is not important

• Frequent insertions and erases

C++

• std::list

C#

• LinkedList<T>

Intrusive List

An intrusive list is a dynamic collection of elements.

It's implemented as a double-linked list that does not contain any data.

Decouples memory allocation from the container itself.

The list can be implemented as a circular list.

Advantages

• To add an element to the list, it is not necessary to perform an allocation

• To remove an element from the list, it doesn't need to be looked up and it is not necessary to perform a deallocation

• The list node and the surrounding data are cache-friendly

Disadvantages

• An element can only belong to a single list

• The debugger cannot inspect the data

https://www.gamasutra.com/view/news/128568/InDepth_Intrusive_Lists.php

https://github.com/Edgarins29/Doom3/blob/master/neo/idlib/containers/LinkList.h

Set

A set is a dynamic collection of unique elements.

It's typically implemented as a binary search tree.

Advantages

• Fast insertions and erases

• Fast lookups

Disadvantages

• Non contiguous memory location (not cache-friendly)

Use cases

• Collections of unique elements

• Order is not important

• Access by index is not important

• Frequent insertions and erases

• Frequent lookups

C++

• std::set

C#

• SortedSet<T>

Vector Set

A vector set is a set implemented like an ordered vector.

Advantages

• Contiguous memory location (cache-friendly)

• Fast lookups

Disadvantages

• Slow insertions and erases

Use cases

• Cache-friendly set

C#

• HashSet<T>

Map

A map is a dynamic collection of key / value elements.

It's typically implemented as a binary search tree.

Advantages

• Fast insertions and erases

• Fast lookups

• Distinction of key and value

Disadvantages

• Non contiguous memory location (not cache-friendly)

Use cases

• Collections of elements with unique keys

• Order is not important

• Access by index is not important

• Frequent insertions and erases

• Frequent lookups with keys

C++

• std::map

• std::unordered_map

C++/CX

• Platform::Collections::Map

• Platform::Collections::UnorderedMap

C#

• Dictionary<T>

Vector Map

A vector map is a map implemented like an ordered vector.

It's implemented as either a vector of key / value pairs or as separate vectors of keys and values.

Advantages

• Contiguous memory location (cache-friendly)

• Fast lookups

Disadvantages

• Slow insertions and erases

• Large values cause cache misses when key / value pairs are stored in contiguous memory location

Use cases

• Cache-friendly map