📖 Complete Guide to ordered_set in C++

1. Introduction

C++ STL already provides:

• std::set → stores unique elements in sorted order, allows logarithmic-time insertion, deletion, and search.

• std::multiset → allows duplicates, sorted order.

• std::unordered_set → stores unique elements in no particular order, average O(1) operations.

But none of these standard containers allow:

• Accessing elements by index (like an array) while keeping them sorted.

• Finding the order (rank) of an element in sorted order.

That’s where ordered_set from GNU Policy-Based Data Structures (PBDS) comes in.

---

2. What is ordered_set?

ordered_set is not part of the standard C++ STL.
It’s an extension provided by GCC’s libstdc++ under the ext/pb_ds library.

It’s essentially:

• A balanced BST (like std::set)

• + Extra features:

  1. Order-statistics: find the k-th smallest/largest element.

  2. Rank queries: find the index (0-based rank) of an element.

Internally, it’s implemented as a Red-Black tree with extra metadata to track subtree sizes.

---

3. Syntax

You must include:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

Then define:

template <typename T>
using ordered_set = tree<
    T,
    null_type,
    less<T>,
    rb_tree_tag,
    tree_order_statistics_node_update>;

---

4. Member Functions

An ordered_set works like a normal std::set plus:

---

5. Basic Example

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    cout << *s.find_by_order(0) << "\n"; // 10
    cout << *s.find_by_order(2) << "\n"; // 30
    cout << s.order_of_key(25) << "\n";  // 2 (10, 20 are less than 25)

    return 0;
}

Output:

10
30
2

---

6. Example with All Operations

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_set<int> s;

    // Insert elements
    s.insert(5);
    s.insert(1);
    s.insert(10);
    s.insert(7);

    // Elements are automatically sorted: {1, 5, 7, 10}

    // Access by index
    cout << *s.find_by_order(0) << "\n"; // 1
    cout << *s.find_by_order(2) << "\n"; // 7

    // Find index of element
    cout << s.order_of_key(7) << "\n"; // 2 (1 and 5 are before 7)
    cout << s.order_of_key(8) << "\n"; // 3 (1, 5, 7 are before 8)

    // Remove element
    s.erase(5);
    cout << s.order_of_key(7) << "\n"; // 1 (only 1 before 7 now)

    // Check if element exists
    if (s.find(10) != s.end()) {
        cout << "10 exists\n";
    }

    return 0;
}

Output:

1
7
2
3
1
10 exists

---

7. Handling Duplicates

The normal ordered_set doesn’t allow duplicates.
For duplicates, store pairs or use a trick by inserting (value, index).

Example:

ordered_set<pair<int,int>> ms;
ms.insert({5, 0});
ms.insert({5, 1});
ms.insert({7, 0});

---

8. Time Complexity

• Insertion: O(log n)

• Deletion: O(log n)

• Search: O(log n)

• find_by_order: O(log n)

• order_of_key: O(log n)

---

9. Common Use Cases

1. K-th smallest/largest queries in dynamic data.

2. Order statistics problems in competitive programming.

3. Maintaining a sorted set while needing index-based access.

4. Problems involving rank of elements.

5. Dynamic median finding (insert elements, find median in O(log n)).

---

10. Special Notes

• Works only in GCC/Clang with libstdc++ (not MSVC).

• Be careful with large memory usage for big datasets.

• find_by_order(k) is undefined if k >= size().