Part 17: Collections

Until now every sequence had a length fixed while compiling. Real data rarely does: lines read from a file, orders placed today, words in a text. This part introduces the containers of the Collections package, which hold as many values as arrive and manage their own memory through an allocator. By the end you will know eleven of them, what each is quick and slow at, and which to reach for.

What you will learn

• Vector<T>, the growable sequence, and the difference between its length and its capacity.
• Array<T>, a sequence whose length is chosen at run time and then fixed.
• Deque<T>, quick at both ends — the natural queue.
• HashMap<K, V> and HashSet<T>: lookup by key and membership tests in about constant time, with no order.
• TreeMap<K, V> and TreeSet<T>: the same, kept sorted, with ordered questions such as Floor, Ceiling and Range.
• PriorityQueue<T>, which always hands out its largest element next, by the element's own <.
• BitSet, a set of small integers at one bit each, with union, intersection and difference a word at a time.
• SmallVector<T>, a vector that keeps its first few elements inside itself and allocates only past them.
• LruCache<K, V>, a map of bounded size that forgets the entry used least recently.
• The pattern every collection shares: made from an allocator, fallible where it needs memory, optional where a value may be missing, and freed by its destructor.

Which collection?

flowchart LR
    q{"How do you find<br/>a value again?"} -- "by position" --> pos{"How does the<br/>length change?"}
    pos -- "never — known<br/>while compiling" --> inline["Inline array<br/>`T[n]`"]
    pos -- "never — known<br/>only at run time" --> arr["`Array`"]
    pos -- "values come and go<br/>at the end" --> vec["`Vector`"]
    pos -- "values come and go<br/>at both ends" --> dq["`Deque`"]
    q -- "by key" --> korder{"Do the keys need<br/>to stay in order?"}
    korder -- "no" --> hm["`HashMap`"]
    korder -- "yes" --> tm["`TreeMap`"]
    q -- "only: is it here?" --> sorder{"Do the members need<br/>to stay in order?"}
    sorder -- "no" --> hs["`HashSet`"]
    sorder -- "yes" --> ts["`TreeSet`"]

When in doubt, start with a Vector for a list and a HashMap for lookups. Switch to a Deque when values join at the front, and to a tree when the order of the keys is part of the answer.

The last four lessons are specialists, each the better choice for one particular job:

Lessons

Before you start

Every collection takes an allocator, so finish Part 15: Memory first. The lessons also lean on generic types from Part 13, a fallible Main and ? from Part 9, optionals from Part 8, moves from Part 11, Comparable and Operator overload from Part 12, and Bitwise from Part 16. Each lesson's package is in the Examples repository's Collections/ folder:

cd Examples/Collections/Vector
rux run

After this part

Part 18: Algorithms sorts, searches and folds the values you can now collect. Parts 18 to 26 tour the standard packages and can be read in any order. Before moving on, try the checkpoint projects Word count, which counts words in a hash map and prints them in order through a tree map, and Inventory, a shop's stock kept as structs in a vector.

For the rules behind the inline sequences these containers are compared with, see Arrays and Slices in the Rux Reference.