Compressor
(utilities/compressor.hpp)

• View this file on GitHub
• Last update: 2026-06-16 01:13:59+09:00
• Include: #include "utilities/compressor.hpp"

Overview

Coordinate compression helper. It stores sorted unique values and maps original values to dense zero-based indices.

Methods

Method	Description	Complexity
Compressor()	Creates an empty compressor.	$O(1)$
Compressor(vector<T> values)	Builds from a vector.	$O(N \log N)$
Compressor(first, last)	Builds from an iterator range.	$O(N \log N)$
void add(const T& value)	Adds a value before rebuilding.	Amortized $O(1)$
void build()	Sorts and removes duplicates.	$O(N \log N)$
int get(const T& value) const	Returns the compressed index of an existing value.	$O(\log N)$
int lower_bound(const T& value) const	Returns the first compressed index with value >= value.	$O(\log N)$
int upper_bound(const T& value) const	Returns the first compressed index with value > value.	$O(\log N)$
bool contains(const T& value) const	Returns whether the value exists.	$O(\log N)$
const T& operator[](int index) const	Restores an original value from a compressed index.	$O(1)$
const vector<T>& values() const	Returns all sorted unique values.	$O(1)$

Example

#include "utilities/compressor.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> xs = {100, -5, 100, 7};
    m1une::utilities::Compressor<long long> comp(xs);

    int id = comp.get(100);     // 2
    long long value = comp[id]; // 100
    std::cout << id << " " << value << "\n";
}

Verified with

• verify/utilities/extra_utilities.test.cpp

Code

#ifndef M1UNE_COMPRESSOR_HPP
#define M1UNE_COMPRESSOR_HPP 1

#include <algorithm>
#include <initializer_list>
#include <stdexcept>
#include <utility>
#include <vector>

namespace m1une {
namespace utilities {

template <typename T>
struct Compressor {
   private:
    std::vector<T> _values;

   public:
    Compressor() = default;

    explicit Compressor(std::vector<T> values) : _values(std::move(values)) {
        build();
    }

    Compressor(std::initializer_list<T> values) : _values(values) {
        build();
    }

    template <typename Iterator>
    Compressor(Iterator first, Iterator last) : _values(first, last) {
        build();
    }

    void add(const T& value) {
        _values.push_back(value);
    }

    void build() {
        std::sort(_values.begin(), _values.end());
        _values.erase(std::unique(_values.begin(), _values.end()), _values.end());
    }

    int get(const T& value) const {
        auto it = std::lower_bound(_values.begin(), _values.end(), value);
        if (it == _values.end() || *it != value) {
            throw std::out_of_range("value is not contained in Compressor");
        }
        return static_cast<int>(it - _values.begin());
    }

    int lower_bound(const T& value) const {
        return static_cast<int>(std::lower_bound(_values.begin(), _values.end(), value) - _values.begin());
    }

    int upper_bound(const T& value) const {
        return static_cast<int>(std::upper_bound(_values.begin(), _values.end(), value) - _values.begin());
    }

    bool contains(const T& value) const {
        auto it = std::lower_bound(_values.begin(), _values.end(), value);
        return it != _values.end() && *it == value;
    }

    const T& operator[](int index) const {
        return _values.at(index);
    }

    const std::vector<T>& values() const {
        return _values;
    }

    int size() const {
        return static_cast<int>(_values.size());
    }

    bool empty() const {
        return _values.empty();
    }
};

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_COMPRESSOR_HPP

#line 1 "utilities/compressor.hpp"



#include <algorithm>
#include <initializer_list>
#include <stdexcept>
#include <utility>
#include <vector>

namespace m1une {
namespace utilities {

template <typename T>
struct Compressor {
   private:
    std::vector<T> _values;

   public:
    Compressor() = default;

    explicit Compressor(std::vector<T> values) : _values(std::move(values)) {
        build();
    }

    Compressor(std::initializer_list<T> values) : _values(values) {
        build();
    }

    template <typename Iterator>
    Compressor(Iterator first, Iterator last) : _values(first, last) {
        build();
    }

    void add(const T& value) {
        _values.push_back(value);
    }

    void build() {
        std::sort(_values.begin(), _values.end());
        _values.erase(std::unique(_values.begin(), _values.end()), _values.end());
    }

    int get(const T& value) const {
        auto it = std::lower_bound(_values.begin(), _values.end(), value);
        if (it == _values.end() || *it != value) {
            throw std::out_of_range("value is not contained in Compressor");
        }
        return static_cast<int>(it - _values.begin());
    }

    int lower_bound(const T& value) const {
        return static_cast<int>(std::lower_bound(_values.begin(), _values.end(), value) - _values.begin());
    }

    int upper_bound(const T& value) const {
        return static_cast<int>(std::upper_bound(_values.begin(), _values.end(), value) - _values.begin());
    }

    bool contains(const T& value) const {
        auto it = std::lower_bound(_values.begin(), _values.end(), value);
        return it != _values.end() && *it == value;
    }

    const T& operator[](int index) const {
        return _values.at(index);
    }

    const std::vector<T>& values() const {
        return _values;
    }

    int size() const {
        return static_cast<int>(_values.size());
    }

    bool empty() const {
        return _values.empty();
    }
};

}  // namespace utilities
}  // namespace m1une

Back to top page