Introduction

A standard std::set does not provide rank queries in O(log n). You can find an element in O(log n), but computing its rank by measuring the distance from begin() is linear because std::set iterators are only bidirectional, not random-access. So the real answer is: not with plain std::set alone.

Why std::set Is Not Enough

The usual idea is:

auto it = s.find(x);
auto rank = std::distance(s.begin(), it);

The lookup is O(log n), but std::distance over a std::set iterator walks element by element, so that part is O(n).

That means the full operation is not logarithmic.

This is a very common misconception because std::set is tree-based internally, but the standard interface does not expose subtree sizes needed for order statistics.

What You Actually Need: An Order-Statistic Tree

To answer rank queries in O(log n), you need a tree that maintains subtree counts. Then each left or right turn during the search can add the number of elements skipped so far.

The C++ standard library does not provide such a container directly.

A common non-standard solution on GCC is Policy-Based Data Structures, often called PBDS.

1#include <ext/pb_ds/assoc_container.hpp>
2#include <ext/pb_ds/tree_policy.hpp>
3
4using namespace __gnu_pbds;
5
6using ordered_set = tree<
7    int,
8    null_type,
9    std::less<int>,
10    rb_tree_tag,
11    tree_order_statistics_node_update>;

This container supports both:

• 'order_of_key(x): number of elements strictly less than x'
• 'find_by_order(k): iterator to the element with zero-based order k'

Rank Query Example

1#include <iostream>
2#include <ext/pb_ds/assoc_container.hpp>
3#include <ext/pb_ds/tree_policy.hpp>
4
5using namespace __gnu_pbds;
6
7using ordered_set = tree<
8    int,
9    null_type,
10    std::less<int>,
11    rb_tree_tag,
12    tree_order_statistics_node_update>;
13
14int main() {
15    ordered_set s;
16    s.insert(10);
17    s.insert(30);
18    s.insert(20);
19
20    std::cout << s.order_of_key(20) << "\n";
21}

This prints 1 because only 10 is smaller than 20.

That is the logarithmic rank operation people usually want.

What If You Must Use Standard C++ Only

If you must stay within the standard library, then you need a different approach based on the overall problem.

Options include:

• a sorted std::vector if updates are rare and queries are frequent
• a Fenwick tree or segment tree after coordinate compression
• a custom balanced tree with subtree sizes

Those solutions depend on the workload. There is no hidden std::set trick that turns rank into O(log n).

Be Clear About the Meaning of Rank

Rank usually means the number of elements strictly smaller than x.

That definition matters because:

• if x is absent, you may still want the insertion position
• duplicates require extra thought if you use a multiset-like structure
• some APIs use zero-based rank while others use one-based rank

The PBDS order_of_key(x) definition is strict-less-than, which is often exactly what you want for insertion position logic.

Common Pitfalls

The most common mistake is assuming std::distance(begin, it) is logarithmic just because find was logarithmic.

Another mistake is relying on implementation details of red-black trees and forgetting that the standard API is what determines available complexity guarantees.

A third issue is using PBDS without noting that it is GNU-specific and not part of portable ISO C++.

Finally, if duplicates matter, an ordered_set of raw values is not enough. You may need pairs such as (value, unique_id) or a different data structure entirely.

Summary

• Plain std::set does not support rank queries in O(log n).
• 'find is logarithmic, but std::distance on set iterators is linear.'
• For logarithmic rank queries, use an order-statistic tree.
• GCC PBDS offers order_of_key and find_by_order for this purpose.
• In standard C++, you need an alternative data structure or problem-specific redesign.
• The key missing feature in std::set is subtree-size information exposed through the interface.