ordered_map.h

Go to the documentation of this file.

/*
 * Copyright 2025 MusicScience37 (Kenta Kabashima)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once
 
#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <unordered_map>
#include <utility>
#include <vector>
 
namespace stat_bench {
namespace util {

template <typename Key, typename MappedValue>
class OrderedMap {
public:
    using iterator =
        typename std::vector<std::pair<Key, MappedValue>>::iterator;

    using const_iterator =
        typename std::vector<std::pair<Key, MappedValue>>::const_iterator;

    OrderedMap() = default;

    OrderedMap(
        std::initializer_list<std::pair<Key, MappedValue>> initializer_list) {
        for (auto& pair : initializer_list) {
            emplace(std::move(pair.first), std::move(pair.second));
        }
    }

    [[nodiscard]] auto empty() const noexcept -> bool {
        return key_to_index_.empty();
    }

    [[nodiscard]] auto size() const noexcept -> std::size_t {
        return key_to_index_.size();
    }

    [[nodiscard]] auto count(const Key& key) const -> std::size_t {
        return key_to_index_.count(key);
    }

    void reserve(std::size_t size) {
        key_to_index_.reserve(size);
        pairs_.reserve(size);
    }

    template <typename... Args>
    auto emplace(Args&&... args) -> std::pair<iterator, bool> {
        pairs_.emplace_back(std::forward<Args>(args)...);
        const auto [iter, success] =
            key_to_index_.emplace(pairs_.back().first, pairs_.size() - 1);
        if (!success) {
            pairs_.pop_back();
        }
        return {pairs_.begin() + static_cast<std::ptrdiff_t>(iter->second),
            success};
    }

    template <typename... Args>
    auto try_emplace(const Key& key, Args&&... args)
        -> std::pair<iterator, bool> {
        const auto iter = key_to_index_.find(key);
        if (iter != key_to_index_.end()) {
            return {pairs_.begin() + static_cast<std::ptrdiff_t>(iter->second),
                false};
        }
        pairs_.emplace_back(key, MappedValue{std::forward<Args>(args)...});
        key_to_index_[key] = pairs_.size() - 1;
        return {pairs_.end() - 1, true};
    }

    auto erase(const_iterator iter) -> iterator {
        const auto index = iter - pairs_.begin();
        key_to_index_.erase(pairs_[index].first);
        pairs_.erase(iter);
        for (std::size_t i = index; i < pairs_.size(); ++i) {
            key_to_index_[pairs_[i].first] = i;
        }
        return pairs_.begin() + static_cast<std::ptrdiff_t>(index);
    }

    [[nodiscard]] auto operator[](const Key& key) -> MappedValue& {
        const auto iter = key_to_index_.find(key);
        if (iter == key_to_index_.end()) {
            pairs_.emplace_back(key, MappedValue{});
            key_to_index_[key] = pairs_.size() - 1;
            return pairs_.back().second;
        }
        return pairs_[iter->second].second;
    }

    [[nodiscard]] auto at(const Key& key) const -> const MappedValue& {
        return pairs_[key_to_index_.at(key)].second;
    }

    [[nodiscard]] auto find(const Key& key) const -> const_iterator {
        const auto iter = key_to_index_.find(key);
        if (iter == key_to_index_.end()) {
            return pairs_.end();
        }
        return pairs_.begin() + static_cast<std::ptrdiff_t>(iter->second);
    }

    [[nodiscard]] auto begin() -> iterator { return pairs_.begin(); }

    [[nodiscard]] auto begin() const -> const_iterator {
        return pairs_.begin();
    }

    [[nodiscard]] auto end() -> iterator { return pairs_.end(); }

    [[nodiscard]] auto end() const -> const_iterator { return pairs_.end(); }

    [[nodiscard]] auto operator==(const OrderedMap& rhs) const -> bool {
        if (key_to_index_.size() != rhs.key_to_index_.size()) {
            return false;
        }
        return std::all_of(key_to_index_.begin(), key_to_index_.end(),
            [this, &rhs](const auto& pair) {
                const auto rhs_iter = rhs.key_to_index_.find(pair.first);
                return rhs_iter != rhs.key_to_index_.end() &&
                    pairs_[pair.second].second ==
                    rhs.pairs_[rhs_iter->second].second;
            });
    }

    [[nodiscard]] auto operator!=(const OrderedMap& rhs) const -> bool {
        return !(*this == rhs);
    }

    [[nodiscard]] auto pairs() const noexcept
        -> const std::vector<std::pair<Key, MappedValue>>& {
        return pairs_;
    }
 
private:
    std::vector<std::pair<Key, MappedValue>> pairs_;

    std::unordered_map<Key, std::size_t> key_to_index_;
};
 
}  // namespace util
}  // namespace stat_bench