Insert, delete and random pick in O(1)

Why this matters

Many programs keep a collection of items and need three things from it. They add an item, remove an item, and pick one item at random. A card game draws a random card from a deck that keeps changing. A load test picks a random server from a pool. A survey tool picks a random respondent from the people who agreed to be contacted.

A plain list makes at least one of these slow. This lesson shows a structure that does all three in constant time. Constant time, written O(1), means the time for one operation stays about the same when the collection grows from ten items to ten million. The idea is short. It combines two simple containers so that each one covers the weakness of the other.

The two containers come from the C++ standard library. A vector, written std::vector, stores values in one row, one after another. A hash map, written std::unordered_map, finds a value from a key, such as finding a person's record from their ID. You need one fact about hash maps here: looking up a key takes about the same time whatever the size of the map. The other lessons in this module use hash maps in more depth.

The problem with a plain vector

Suppose you store four numbers in a vector: 10, 20, 30 and 40. The positions are 0, 1, 2 and 3.

Picking a random item is easy. Choose a random position from 0 to 3 and read that item. The time does not depend on how many items there are.

Checking whether 30 is present is harder. The vector does not know where 30 is, so you must read the items one at a time until you reach it. In the worst case you read every item. With a million items, that can mean a million reads.

Removing 20 is also costly. The vector stores its items side by side with no gaps. If you erase position 1, every item after it must move one place to the left. With a million items, that can mean a million moves.

So a vector gives a fast random pick but a slow search and a slow delete. A hash map gives a fast search and a fast delete, but it does not let you choose the item at position 7 or any other position. A random pick needs positions. The structure in this lesson uses both containers. The vector gives the random pick. The hash map answers the question "where is this value in the vector?"

The two parts and the one rule

The structure has two parts, and they must always agree:

• The vector holds each value once. The order of the values does not matter.
• The map uses each value as its key and stores the value's position in the vector.

For the four numbers above, the two parts look like this.

The rule is simple. If the value v sits at position i in the vector, then looking up v in the map must give i. Every operation in this lesson keeps that rule true after it finishes.

Insert: add at the end

To insert a new value, add it at the end of the vector. Its position is the old size of the vector, because the last position is always size minus 1. Then store that position in the map.

Take the four numbers and insert 50. The old size is 4, so 50 goes to position 4. The map gets a new entry, 50 to 4. The vector now holds 10, 20, 30, 40 and 50.

Before you insert, check the map. If the value is already a key, it is already in the set, so you do nothing and report that nothing changed. Inserting 20 again does nothing.

Each insert is one check in the map, one push onto the end of the vector, and one write to the map. Pushing onto the end of a vector takes constant time on average. The vector keeps some spare room, and only now and then copies itself into a bigger block. That copy is slow, but it happens rarely enough that the average cost per push stays constant.

Delete: swap the target with the last item

This is the main trick. Suppose you want to remove 20 from the middle of the vector. You could shift 30 and 40 left by one place, but that costs time when the vector is large. Instead, do this.

1. Look up 20 in the map. It is at position 1. Call position 1 the hole, because it is about to be empty.
2. Read the last item in the vector. It is 40, at position 3.
3. Copy 40 into the hole at position 1.
4. Update the map so that 40 now points to position 1.
5. Remove the last position from the vector. This drops the extra copy of 40 at the end.
6. Remove 20 from the map.

The table below shows the state after each step.

Only one value changed its position, which was 40. The value 30 did not move at all. The vector's order changed from 10, 20, 30, 40 to 10, 40, 30, the order does not matter, and each remaining value still appears exactly once.

Think of a shelf of books. To take a book out of the middle without sliding every book along, you move the last book into the gap and then remove the book at the end of the shelf. You change one book's place instead of many.

Random pick: choose a position

To pick a random value, choose a random position between 0 and size minus 1, then return the value there. Every position has the same chance, so every value has the same chance. The cost is one random number and one read from the vector. The return type, std::optional<int>, holds either a value or nothing, and std::nullopt means nothing.

The code uses two tools from the standard library. std::mt19937 is a random number generator, which produces a long sequence of numbers that look random. std::uniform_int_distribution turns that sequence into numbers in a range where every number is equally likely. Passing the generator in from outside lets the caller choose the seed. A fixed seed gives the same sequence every run on the same standard library, which makes the output below repeatable.

The full class

The class below puts the three operations together. It also has contains and size, which are small helpers that make the test program easier to read.

#include <cstddef>
#include <iostream>
#include <optional>
#include <random>
#include <unordered_map>
#include <vector>
 
class RandomSet {
public:
    bool insert(int value) {
        if (position_.contains(value)) {
            return false;
        }
        position_[value] = values_.size();
        values_.push_back(value);
        return true;
    }
 
    bool remove(int value) {
        auto found = position_.find(value);
        if (found == position_.end()) {
            return false;
        }
        std::size_t hole = found->second;
        int last = values_.back();
        values_[hole] = last;
        position_[last] = hole;
        values_.pop_back();
        position_.erase(value);
        return true;
    }
 
    bool contains(int value) const {
        return position_.contains(value);
    }
 
    std::size_t size() const {
        return values_.size();
    }
 
    std::optional<int> random_pick(std::mt19937& rng) const {
        if (values_.empty()) {
            return std::nullopt;
        }
        std::uniform_int_distribution<std::size_t> pick(0, values_.size() - 1);
        return values_[pick(rng)];
    }
 
    void print() const {
        std::cout << "values:";
        for (int v : values_) {
            std::cout << ' ' << v;
        }
        std::cout << '\n';
    }
 
private:
    std::vector<int> values_;
    std::unordered_map<int, std::size_t> position_;
};
 
int main() {
    RandomSet set;
    std::mt19937 rng(7);
 
    for (int v : {10, 20, 30, 40}) {
        set.insert(v);
    }
    set.print();
 
    std::cout << "insert 20 again: " << std::boolalpha << set.insert(20) << '\n';
    std::cout << "remove 20: " << set.remove(20) << '\n';
    set.print();
    std::cout << "contains 20: " << set.contains(20) << '\n';
    std::cout << "remove 99: " << set.remove(99) << '\n';
 
    std::cout << "remove 40: " << set.remove(40) << '\n';
    set.print();
 
    std::cout << "size: " << set.size() << '\n';
    std::cout << "five random picks:";
    for (int i = 0; i < 5; ++i) {
        std::cout << ' ' << *set.random_pick(rng);
    }
    std::cout << '\n';
 
    RandomSet empty;
    std::cout << "pick from empty set has value: " << empty.random_pick(rng).has_value() << '\n';
}

Save the code as random_set.cpp. Compile it with a C++20 compiler and warnings on, then run it.

g++ -std=c++20 -Wall -Wextra -o random_set random_set.cpp
./random_set

The output is:

values: 10 20 30 40
insert 20 again: false
remove 20: true
values: 10 40 30
contains 20: false
remove 99: false
remove 40: true
values: 10 30
size: 2
five random picks: 10 10 30 10 10
pick from empty set has value: false

Read the output line by line. The second line is false because 20 is already a key in the map, so the insert did nothing. The third line shows the swap from the table above: 40 moved into position 1. Removing 40 in the last few lines moves 30 into its place, and the vector becomes 10, 30. The random picks come from the generator with seed 7. The exact picks depend on how std::uniform_int_distribution is written in your standard library, so your numbers may differ, but the picks always come from the values that are in the set at that moment.

A second example: removing the last item

Consider removing a value that is already the last item. Take the vector 10, 30 and remove 30. The hole is position 1, and the last item is also position 1. Step 3 copies 30 onto itself. Step 4 sets 30 to point to position 1, which it already does. Step 5 removes the last position. Step 6 removes 30 from the map. Nothing breaks, and the code needs no special case for this.

The same is true when the set has only one value. Removing 42 from a set that holds only 42 gives a hole at position 0, copies 42 onto itself, removes the last position, and erases 42 from the map. The set ends empty.

The order of the steps matters, and the next section explains why.

A third example: a raffle that removes the winner

The swap trick does not need the map when you only remove items by position. Suppose a raffle has a list of entries, and each draw picks one entry at random and removes it. Each winner must leave the list, so the next draw cannot pick the same person.

#include <cstddef>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
 
std::optional<int> pop_random(std::vector<int>& values, std::mt19937& rng) {
    if (values.empty()) {
        return std::nullopt;
    }
    std::uniform_int_distribution<std::size_t> pick(0, values.size() - 1);
    std::size_t index = pick(rng);
    int chosen = values[index];
    values[index] = values.back();
    values.pop_back();
    return chosen;
}
 
int main() {
    std::mt19937 rng(3);
    std::vector<int> entries = {1, 2, 3};
    std::cout << "draw: " << *pop_random(entries, rng) << ", entries left: " << entries.size() << '\n';
    std::cout << "draw: " << *pop_random(entries, rng) << ", entries left: " << entries.size() << '\n';
    std::cout << "draw: " << *pop_random(entries, rng) << ", entries left: " << entries.size() << '\n';
    std::cout << "draw from empty list has value: " << pop_random(entries, rng).has_value() << '\n';
}

The function picks a position, saves the value there, moves the last item into the gap, and removes the last position. It is the same swap as the delete step, with the position already known from the random pick. Save it as raffle.cpp, then compile and run it as before. The output from g++ 15 with the libstdc++ standard library is:

draw: 2, entries left: 2
draw: 1, entries left: 1
draw: 3, entries left: 0
draw from empty list has value: 0

The draws come from the generator with seed 3. Another standard library may use a different random distribution and print other numbers, but each draw is still one of the entries that was left.

Common mistakes

Forgetting to update the moved value

The most common mistake is to move the last item into the hole and forget its position in the map. The sample below does that on purpose.

std::size_t hole = position[20];
values[hole] = values.back();
values.pop_back();
position.erase(20);
// position[40] still says 3, but 40 is now at 1

A check that compares each value's map position with its index would find 40 at index 1 while the map says 3.

Later, a call to remove 40 finds position 3 in the map. After the pop, the vector has only three positions, so position 3 is outside the vector. Writing to it is undefined behavior in C++. That means the program makes no promise about what happens next. In practice it can crash or silently corrupt the vector.

Erasing the key in the wrong order

The code erases the removed value first and writes the moved value's position afterwards. If the removed value is the last item, the two lines work against each other. The sample below does the steps in the wrong order.

position.erase(value);      // remove 40 first
position[last] = hole;      // then write 40 again

When last is the same as value, the second line puts 40 back into the map. A later contains(40) then returns true for a value that is no longer in the set. The output from a test of this order is:

contains 40: 1
map size: 2 vector size: 1

The vector has one item, but the map has two keys. The map and the vector no longer agree. The fix is the order in the class above: update the moved value first, then erase the removed value.

Taking the value from an empty optional

random_pick returns std::optional<int>, which may hold no value. A plain int cannot hold "no value", so assigning the result directly fails to compile. g++ 15 reports this error:

err_optional.cpp:13:22: error: cannot convert 'std::optional<int>' to 'int' in initialization
   13 |     int chosen = pick(v, rng);
      |                  ~~~~^~~~~~~~
      |                      |
      |                      std::optional<int>

The fix is to check the result first, or to read it with * only after you know the set is not empty. The has_value call in the test program shows the first option.

Reading the last item of an empty vector

values.back() on an empty vector is undefined behavior. Unlike the compile error above, the compiler does not warn you. The remove function in this lesson is safe because it first checks the map for the value. If the map has the value, the vector cannot be empty. Keep that check in your own code, and check the size before any call that reads the last item.

Using a map alone for the random pick

A map cannot pick a random key in constant time. You cannot ask for "the key at position 7", because a hash map does not store its keys in a row. The workaround of copying all the keys into a vector on every pick costs time proportional to the size of the map. The fix is the structure in this lesson: keep the vector as the source for picks.

Practice

Exercise 1. Start with the vector 5, 6, 7, 8 and the matching map entries. Remove 6 using the six steps. Write the vector after the removal and say which value changed its position.

Show the answer

The hole is position 1. The last item is 8, at position 3. Copy 8 into position 1, so the vector is 5, 8, 7, 8. Update the map so 8 points to 1. Remove the last position, giving 5, 8, 7. Remove 6 from the map. The vector is 5, 8, 7. Only 8 changed its position, from 3 to 1.

Exercise 2. Explain in two or three sentences why the delete does not need to shift the items after the removed value.

Show the answer

The vector has no required order, so shifting the items only keeps an order that nobody needs. Moving the last item into the gap changes one position, and the map is updated to match. Each delete does a fixed number of steps instead of one step for every item after the removed value.

Exercise 3. Add a method std::optional<int> pop_random(std::mt19937& rng) to RandomSet. It must choose a value at random, remove it from the set, and return it. It must return an empty optional when the set is empty. Test it on a set that holds 10, 20 and 30, then check that size drops by one each time.

Show the answer

Pick a random value with random_pick. If there is none, return std::nullopt. Otherwise copy the value and call remove with it, then return the copy. The example below shows the method.

std::optional<int> pop_random(std::mt19937& rng) {
    std::optional<int> chosen = random_pick(rng);
    if (chosen) {
        remove(*chosen);
    }
    return chosen;
}

Each call removes one value, so the size drops from 3 to 2 to 1 to 0. A fourth call returns no value. This version uses random_pick and remove, so it reuses the code that already keeps the map and vector in step. Calling it four times on a set of 10, 20 and 30, with std::mt19937 rng(7), and printing each value and the size after each call gives this line:

pop test: 10(size 2) 30(size 1) 20(size 0) none(size 0)

Exercise 4. A set holds 10, 20 and 30. Explain why removing 30 gives the same result as removing 10 if you only look at the vector. Then explain what differs in the map.

Show the answer

Removing 30 gives 10, 20, which is the vector after the last position is dropped. Removing 10 moves 30 into position 0, which gives 30, 20. The vectors differ in order, but both hold the same two values. In the map, the entry for 30 is removed in the first case. In the second case the entry for 30 changes from position 2 to position 0, and the entry for 10 is removed.

Exercise 5. Write a rule in one sentence that a reviewer could use to check the remove function. Then say which line would break the rule if it were moved above the line that updates the moved value.

Show the answer

Rule: after remove finishes, every value in the vector is a key in the map, and its stored position is the index where it sits in the vector. Moving the position_.erase(value) line above the update to the moved value breaks this rule when the removed value is the last item, because the update writes the removed value back into the map.

Summary

• A vector gives a fast random pick, and a hash map gives a fast search for a value's position.
• Insert adds the value at the end of the vector and records its position in the map.
• Delete moves the last value into the hole, updates its map entry, then removes the last position and the deleted key.
• Each of the three operations takes constant time on average, because none of them shifts other items.
• The order of the vector has no meaning, so changing it during a delete is safe.
• The order of the steps in delete matters when the removed value is the last item.