Introduction

std::vector can access any valid element index in constant time because it stores elements contiguously in memory. The distance between logical indices does not matter to the access operation itself. What does matter is that all elements up to the highest used index must actually exist, which makes std::vector a poor fit for truly sparse data.

Why Access Is Still Fast

The core idea behind std::vector is contiguous storage. If data() points to the first element, then element i lives at a fixed offset from that base address.

Conceptually, vec[i] is just pointer arithmetic:

1#include <iostream>
2#include <vector>
3
4int main() {
5    std::vector<int> values = {10, 20, 30, 40};
6    std::cout << values[2] << '\n';  // 30
7}

Because the address of element i is derived directly from the base address plus i * sizeof(T), the lookup does not depend on how far apart used indices are from each other.

The Real Cost Is Memory, Not Index Math

Suppose you want to store values only at indices 5 and 1_000_000. A vector can do that only if its size is at least 1_000_001.

1#include <iostream>
2#include <vector>
3
4int main() {
5    std::vector<int> values(1'000'001, 0);
6    values[5] = 42;
7    values[1'000'000] = 99;
8
9    std::cout << values[5] << '\n';
10    std::cout << values[1'000'000] << '\n';
11}

Access is still constant time, but the vector had to allocate space for every element in between. That is why std::vector is dense storage, not sparse storage.

Huge Gaps Do Not Mean Hidden Compression

The vector does not "skip" unused positions or remember only the populated indices. If the highest index is large, capacity and size must cover that range. The intermediate elements are real objects with real storage.

That means huge gaps are fine only when:

• the element type is small
• the maximum index is still reasonable
• dense contiguous storage is what you actually want

If the data is sparse, you are paying memory cost for mostly empty slots.

When a Different Container Is Better

For sparse keys, containers such as std::unordered_map or std::map are usually a better match:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5    std::unordered_map<int, int> values;
6    values[5] = 42;
7    values[1'000'000] = 99;
8
9    std::cout << values[5] << '\n';
10    std::cout << values[1'000'000] << '\n';
11}

Now only the used indices are stored. You lose true contiguous layout, but you stop allocating millions of unused elements.

Another Subtle Point: Bounds Still Matter

vec[1'000'000] is only valid if the vector actually has that many elements. Accessing beyond size() is undefined behavior:

std::vector<int> values(10);
// values[1000000] = 1;  // Undefined behavior

If safety matters, use at() while debugging:

values.at(5) = 10;

at() checks bounds and throws an exception on invalid access.

A Good Mental Model

Think of a vector as a dynamic array, not as a dictionary keyed by integers. Integer index lookup is fast because the memory is laid out densely. That same density is exactly why large unused gaps become wasteful.

So the answer to the question is:

• it accesses distant indices quickly because indexing is pointer arithmetic
• it does not avoid allocating the gap between them

Common Pitfalls

The biggest pitfall is confusing fast random access with sparse storage. std::vector gives the first but not the second.

Another issue is resizing a vector to a very large maximum index just to store a few values. That may compile and run, but it can waste a huge amount of memory.

People also forget that out-of-range indexing is undefined behavior with operator[]. If the vector size does not cover the index, the program is already in trouble.

Summary

• 'std::vector supports constant-time indexing because elements are stored contiguously.'
• Large gaps between used indices do not hurt access speed directly.
• But the vector still allocates storage for all elements up to the highest index.
• For sparse integer keys, std::unordered_map or std::map is often a better fit.
• Fast access and efficient sparse storage are different design goals.