Compressor (other/compressor.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-18 22:02:23+07:00
• Include: #include "other/compressor.hpp"

Description

Compressor maps values to consecutive integers starting from 0. Useful for coordinate compression when working with large value ranges. Supports compressing individual values, pairs, and containers.

Operations

• Compressor<T>(int n = 0)
  • Constructs compressor with reserved capacity n
  • Time complexity: $\mathcal O(1)$
• void push(Ts &...x)
  • Adds values to be compressed (can take multiple arguments, pairs, or containers)
  • Time complexity: $\mathcal O(1)$ per value
• int build()
  • Builds the compression mapping and assigns compressed values
  • Must be called after all push operations and before using operator[] or operator()
  • Returns the number of distinct values
  • Time complexity: $\mathcal O(n \log n)$ where $n$ is the number of values
• int size()
  • Returns the number of distinct values
  • Time complexity: $\mathcal O(1)$
• T operator[](int i)
  • Returns the original value corresponding to compressed index i
  • Time complexity: $\mathcal O(1)$
• int operator()(T x)
  • Returns the compressed index of value x, or the insertion point if not found
  • Time complexity: $\mathcal O(\log n)$
• bool find(T x)
  • Returns whether value x was compressed
  • Time complexity: $\mathcal O(\log n)$

Verified with

• test/yosupo/ds/static_range_inversions_query.test.cpp

Code

#pragma once

// clang-format off
template<class T = int> struct Compressor {
    vector<reference_wrapper<T>> val;
    vector<T> og;

    Compressor(int n = 0) { val.reserve(n); }

    template<class... Ts> void push(Ts &...x) { (_push(x), ...); }
    int build() {
        sort(begin(val), end(val));
        og.reserve(val.size());
        T id = -1;
        for (auto x : val) {
            if (og.empty() || og.back() != x) id++, og.push_back(x);
            x.get() = id;
        }
        og.shrink_to_fit();
        return size();
    }
    int size() const { return (int)og.size(); }
    T operator[](int i) const { return og[i]; }
    int operator()(T x) const { return int(lower_bound(begin(og), end(og), x) - begin(og)); }
    bool find(T x) const { return binary_search(begin(og), end(og), x); }

  private:
    void _push(T &x) { val.push_back(x); }
    void _push(pair<T, T> &p) { push(p.first, p.second); }
    template<class V> void _push(V &a) { for (auto &x : a) _push(x); }
};
// clang-format on

#line 2 "other/compressor.hpp"

// clang-format off
template<class T = int> struct Compressor {
    vector<reference_wrapper<T>> val;
    vector<T> og;

    Compressor(int n = 0) { val.reserve(n); }

    template<class... Ts> void push(Ts &...x) { (_push(x), ...); }
    int build() {
        sort(begin(val), end(val));
        og.reserve(val.size());
        T id = -1;
        for (auto x : val) {
            if (og.empty() || og.back() != x) id++, og.push_back(x);
            x.get() = id;
        }
        og.shrink_to_fit();
        return size();
    }
    int size() const { return (int)og.size(); }
    T operator[](int i) const { return og[i]; }
    int operator()(T x) const { return int(lower_bound(begin(og), end(og), x) - begin(og)); }
    bool find(T x) const { return binary_search(begin(og), end(og), x); }

  private:
    void _push(T &x) { val.push_back(x); }
    void _push(pair<T, T> &p) { push(p.first, p.second); }
    template<class V> void _push(V &a) { for (auto &x : a) _push(x); }
};
// clang-format on

Back to top page