Ch9.1: Overview of Sequential Containers

Overview

This section introduces all sequential containers available in fast_io_dsal. Sequential containers store elements in order — the first element added is at position 0, the second at position 1, and so on. We present every container, explain data locality, and give rules of thumb for choosing the right container.

1. Container Catalogue

The following tables list every container. The IPA column shows how each name is pronounced using the International Phonetic Alphabet.

Owning Containers

Container	IPA	Memory Layout	Description
`::fast_io::array<T, N>`	/əˈreɪ/	Contiguous (stack or static)	Fixed-size, compile-time known number of elements.
`::fast_io::vector<T>`	/ˈvɛktər/	Contiguous (heap)	Default container. Dynamic-size, contiguous storage.
`::fast_io::string`	/strɪŋ/	Contiguous (heap)	Dynamic character sequence. Alias for `basic_string<char>`.
`::fast_io::deque<T>`	/dɛk/	Chunked blocks (heap)	Double-ended queue. Fast insertion/removal at both ends, with random access.
`::fast_io::list<T>`	/lɪst/	Doubly-linked nodes (heap)	Doubly-linked list. Θ(1) insertion/removal anywhere once positioned.
`::fast_io::forward_list<T>`	/ˈfɔɹwəɹd lɪst/	Singly-linked nodes (heap)	Singly-linked list. Minimal per-element overhead, forward iteration only.
`::fast_io::bitvec`	/bɪt vɛk/	Packed bits (heap)	Dynamic bit vector. Stores individual bits, not `bool` values.

View Types (Non-owning)

View Type	IPA	Description
`::fast_io::span<T>`	/spæn/	Non-owning view over contiguous memory with dynamic size.
`::fast_io::index_span<T, N>`	/ˈɪndɛks spæn/	Non-owning view with compile-time fixed size N.
`::fast_io::string_view`	/strɪŋ vjuː/	Non-owning view over a character sequence.
`::fast_io::cstring_view`	/ˈsiː strɪŋ vjuː/	Non-owning view with a null-termination guarantee.

2. Data Locality and Performance

The way a container stores its elements in memory has a profound effect on performance. Modern CPUs rely heavily on caches (L1, L2, L3). When elements are stored contiguously, accessing one element typically brings its neighbours into cache, making subsequent accesses nearly free.

Layout	Containers	Cache Behaviour	Iteration Speed
Contiguous	`array`, `vector`, `string`	Excellent — hardware prefetcher works perfectly	Fastest
Chunked	`deque`	Good within a block, occasional cache miss at block boundaries	Near-contiguous for large containers
Linked nodes	`list`, `forward_list`	Poor — each node is a separate heap allocation	Slowest — pointer chasing
Packed bits	`bitvec`	Excellent — 64× more compact than `vector<bool>`	Fast, but individual bits require masking

For most workloads, contiguous storage wins. The CPU cache line is typically 64 bytes. A vector<::std::size_t> brings 16 elements per cache line. A list<::std::size_t> brings only 1 element per cache line (and wastes memory on pointers). So even though a list offers Θ(1) insertion, the constant factor for traversal can be 10–50× worse.

3. Choosing a Container

Here are rules of thumb for selecting which container to use:

Avoid containers entirely if you can. If you can accomplish the task with I/O operations (e.g. printing “Hello, World!”), do that instead. I/O provides an abstraction for processing an unbounded amount of data without dynamic allocation. I/O buffers are often more efficient than both stack and heap allocations.

Unless you have a reason to use another container, use ::fast_io::vector. It offers the best cache locality and is the fastest for almost all operations.
If your program has lots of small elements and space overhead matters, don’t use list or forward_list. Each node in a linked list carries at least one pointer (8 bytes on 64-bit systems) of overhead.
If the program requires random access to elements, use a vector or a deque. Both provide Θ(1) operator[]. Linked lists do not.
If the program needs to insert or delete elements in the middle of the container, use a list or forward_list. Once an iterator is positioned, insertion and removal are Θ(1).
If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque. A vector can only efficiently grow at the back.
If the program needs to insert elements in the middle only while reading input, and subsequently needs random access:
- First, consider whether you actually need middle insertion. It is often easier to append to a vector and then call ::std::ranges::sort afterwards.
- If you must insert into the middle, consider using a list during the input phase. Once input is complete, copy the list into a vector.

Best Practice: If you are not sure which container to use, write your code so that it uses only operations common to both vectors and lists: use iterators (or _index operations) and avoid assuming random access. That way it will be easy to switch to either a vector or a list as necessary.

What if the program needs random access and needs to insert or delete elements in the middle? The answer depends on the relative cost of accessing elements in a linked list versus the cost of inserting or deleting in a vector or deque. In general, the predominant operation of the application (whether it does more access or more insertion/deletion) will determine the choice. In such cases, performance testing with both containers will probably be necessary.

Key takeaways

Sequential containers store elements in insertion order.
The default container is ::fast_io::vector.
Contiguous containers (vector, array, string) have the best cache locality.
Linked containers (list, forward_list) have poor cache locality but Θ(1) insertion/removal.
deque sits in the middle: chunked blocks with random access and fast growth at both ends.
Avoid containers entirely when I/O operations can do the job.
Start with vector; switch only when profiling shows a bottleneck.
View types (span, string_view) do not own memory.