OrderedMap.hpp

浏览该文件的文档.

 
 
#pragma once
 
#include "AstGlobal.h"
#include <vector>
#include <unordered_map>
#include <stdexcept>   // for std::out_of_range
#include <utility>     // for std::pair
 
AST_NAMESPACE_BEGIN
 
template<typename Key, typename Value>
class OrderedMap {
private:
    using vector_type = std::vector<std::pair<Key, Value>>;
    using map_type = std::unordered_map<Key, std::size_t>;
    
    // 按插入顺序存储键值对
    vector_type items_;
    // 键到下标位置的快速映射
    map_type index_map_;
public: // ---------- 迭代器支持 ----------
 
    using iterator = typename vector_type::iterator;
    using const_iterator = typename vector_type::const_iterator;
 
    iterator begin() { return items_.begin(); }
    iterator end()   { return items_.end(); }
    const_iterator begin() const { return items_.begin(); }
    const_iterator end() const   { return items_.end(); }
    const_iterator cbegin() const { return items_.cbegin(); }
    const_iterator cend() const   { return items_.cend(); }
 
public: // ---------- 容量 ----------
 
    bool empty() const noexcept {
        return items_.empty();
    }
 
    std::size_t size() const noexcept {
        return items_.size();
    }
 
public: // ---------- 访问元素 ----------
    
    Value& at(const Key& key) {
        auto it = index_map_.find(key);
        if (it == index_map_.end())
            throw std::out_of_range("OrderedMap::at: key not found");
        return items_[it->second].second;
    }
 
    const Value& at(const Key& key) const {
        auto it = index_map_.find(key);
        if (it == index_map_.end())
            throw std::out_of_range("OrderedMap::at: key not found");
        return items_[it->second].second;
    }
 
    Value& operator[](const Key& key) {
        auto it = index_map_.find(key);
        if (it != index_map_.end()) {
            return items_[it->second].second;
        }
        // 不存在则插入默认构造的值
        index_map_[key] = items_.size();
        items_.emplace_back(key, Value{});
        return items_.back().second;
    }
 
public: // ---------- 插入/更新 ----------
 
    void insert(const Key& key, const Value& value) {
        auto it = index_map_.find(key);
        if (it != index_map_.end()) {
            // 已存在：更新值
            items_[it->second].second = value;
        } else {
            // 不存在：追加到末尾
            index_map_[key] = items_.size();
            items_.emplace_back(key, value);
        }
    }
 
    void insert(std::pair<Key, Value>&& pair) {
        insert(pair.first, std::move(pair.second));
    }
 
public: // ---------- 查找 ----------
 
    iterator find(const Key& key) {
        auto it = index_map_.find(key);
        if (it == index_map_.end())
            return items_.end();
        return items_.begin() + it->second;
    }
 
    const_iterator find(const Key& key) const {
        auto it = index_map_.find(key);
        if (it == index_map_.end())
            return items_.end();
        return items_.begin() + it->second;
    }
 
    bool contains(const Key& key) const {
        return index_map_.find(key) != index_map_.end();
    }
 
public:
    void clear() {
        items_.clear();
        index_map_.clear();
    }
 
public: 
    std::vector<Key> keys() const {
        std::vector<Key> result;
        result.reserve(items_.size());
        for (const auto& pair : items_) {
            result.push_back(pair.first);
        }
        return result;
    }
 
    std::vector<Value> values() const {
        std::vector<Value> result;
        result.reserve(items_.size());
        for (const auto& pair : items_) {
            result.push_back(pair.second);
        }
        return result;
    }
 
    const vector_type& items() const { return items_; }
};
 
AST_NAMESPACE_END