Introduction

The right STL approach for median calculation depends on whether you need the median once or you need to maintain it as values arrive over time. For a one-time calculation, a std::vector plus std::nth_element is usually the best choice. For a streaming median, you want a data structure that keeps the lower and upper halves balanced after each insertion.

One-Time Median: Use std::vector and std::nth_element

If all values are already available, you do not need a tree-based container. A std::vector is cache-friendly and simple. std::nth_element rearranges the elements so the target position contains the element that would be there in sorted order, without fully sorting the range.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5double median(std::vector<int> values) {
6    const std::size_t n = values.size();
7    const std::size_t mid = n / 2;
8
9    std::nth_element(values.begin(), values.begin() + mid, values.end());
10
11    if (n % 2 == 1) {
12        return values[mid];
13    }
14
15    int upper = values[mid];
16    std::nth_element(values.begin(), values.begin() + mid - 1, values.begin() + mid);
17    int lower = values[mid - 1];
18    return (lower + upper) / 2.0;
19}
20
21int main() {
22    std::cout << median({7, 1, 5, 3}) << '\n';
23}

This is usually better than inserting into std::set or std::multiset first and paying balancing overhead unnecessarily.

Streaming Median: Keep Two Balanced Halves

If numbers arrive continuously and you need the median after each insertion, a single STL container is usually not enough. The standard design keeps:

• a max-oriented structure for the lower half
• a min-oriented structure for the upper half

In STL, this is naturally modeled with two std::priority_queue instances.

1#include <functional>
2#include <iostream>
3#include <queue>
4
5class RunningMedian {
6public:
7    void add(int value) {
8        if (lower.empty() || value <= lower.top()) {
9            lower.push(value);
10        } else {
11            upper.push(value);
12        }
13        rebalance();
14    }
15
16    double get() const {
17        if (lower.size() == upper.size()) {
18            return (lower.top() + upper.top()) / 2.0;
19        }
20        return lower.top();
21    }
22
23private:
24    std::priority_queue<int> lower;
25    std::priority_queue<int, std::vector<int>, std::greater<int>> upper;
26
27    void rebalance() {
28        if (lower.size() > upper.size() + 1) {
29            upper.push(lower.top());
30            lower.pop();
31        } else if (upper.size() > lower.size()) {
32            lower.push(upper.top());
33            upper.pop();
34        }
35    }
36};

This gives O(log n) insertion and O(1) median lookup.

When multiset Makes Sense

A std::multiset can also work, especially if you need ordered traversal or deletion of arbitrary elements. Some implementations keep an iterator pointing at the median and adjust it during insertions and removals.

That approach can be elegant, but it is more subtle than the two-heap design. If you only need insertion plus median lookup, the heap approach is usually easier to reason about.

Pick the Container for the Workload

The wrong approach is usually choosing the container first and the requirement second. Ask these questions:

• one median at the end, or median after every insertion
• are deletions required
• is preserving full sorted order useful beyond finding the median
• what input size and update rate are expected

For a single batch, std::vector is usually fastest and simplest. For online updates, use a dynamic structure.

Common Pitfalls

• Fully sorting a vector when only the median is needed once.
• Reaching for std::set or std::multiset without a streaming requirement that justifies the extra complexity.
• Forgetting that an even number of values requires the average of the two middle elements.
• Using heaps for a workload that also needs efficient arbitrary deletions without planning for that extra logic.
• Treating STL container choice as the main issue when the real issue is whether the problem is batch or streaming.

Summary

• For a one-time median, prefer std::vector with std::nth_element.
• For a running median, use two balanced heaps or another structure that maintains lower and upper halves.
• 'multiset is viable when ordered traversal or deletions matter, but it is more complex.'
• Choose the data structure based on workload, not habit.
• The correct STL approach is different for batch computation and online computation.