c++ - 为不使用元组的自定义映射模拟 std::map 迭代器

Question

我想创建一个自定义 map ，它实际上使用一组固定的键，但应该表现得像 std::map .基本上我在内部使用一个数组并将键映射到索引，从而实现非常高效的查找。然而，我正在努力实现行为类似于 std::map 的迭代器。迭代器，因为我没有内部 std::pair这是我可以分发的引用资料。

是否可以在保留 std::map 的同时将其实现为零开销抽象？接口(interface)，尤其是迭代器？

我能想到的最好的 operator*是返回一个右值 std::pair<key_type, mapped_type*> ，它基本上允许相同的操作，但不幸的是具有不同的使用模式。

我也试过std::pair<key_type, boost::referene_wrapper<mapped_type>> , 但这仍然不允许 for(auto& elem : map)并且经常需要 elem.second.get()出于我不明白的原因。

如果对用例有任何帮助，我很乐意使用 boost 或轻量级头库。

为了说明这种情况，下面是一个包含所有字母“a”-“z”的 map 的最小示例。

using letter = char;
static const letter letter_begin = 'a';
static const letter letter_end = 'z' + 1;

template <typename T>
class letter_map
{
private:
    using self = letter_map<T>;

    template <typename IT, typename M>
    class iterator_base : public std::iterator<std::input_iterator_tag, T>
    {
    public:
        iterator_base(letter index, M& map) : index_(index), data_(map)
        {
        }

        using self_iter = iterator_base<IT, M>;
        IT operator*()
        {
            return IT(index_, &data_[index_]);
        }

        self_iter& operator++()
        {
            index_++;
            return *this;
        }

        self_iter operator++(int)
        {
            self_iter tmp(*this);
            operator++();
            return tmp;
        }

        bool operator==(self_iter other) const
        {
            assert(&data_ == &other.data_);
            return index_ == other.index_;
        }

        bool operator!=(self_iter other) const
        {
            return !(*this == other);
        }

    private:
        letter index_;
        M& data_;
    };

public:
    using key_type = letter;
    using mapped_type = T;
    using value_type = std::pair<const key_type, mapped_type*>;
    using const_value_type = std::pair<const key_type, const mapped_type*>;

private:
    static const size_t data_size = letter_end - letter_begin;
    using container_type = std::array<mapped_type, data_size>;

public:
    using iterator = iterator_base<value_type, self>;
    using const_iterator = iterator_base<const_value_type, const self>;

public:
    mapped_type& operator[](letter l)
    {
        return data_[l - letter_begin];
    }

    const mapped_type& operator[](letter l) const
    {
        return data_[l - letter_begin];
    }

    auto begin()
    {
        return iterator(letter_begin, *this);
    }

    auto end()
    {
        return iterator(letter_end, *this);
    }

    auto begin() const
    {
        return const_iterator(letter_begin, *this);
    }

    auto end() const
    {
        return const_iterator(letter_end, *this);
    }

private:
    container_type data_;
};

void print_string_letter_map(const letter_map<std::string>& lm)
{
    for (auto elem : lm)
    {
        std::cout << elem.first << "->" << *(elem.second) << std::endl;
    }
}

template<typename T>
class std_letter_map : public std::map<letter, T>
{
public:
    std_letter_map()
    {
        for (letter l = letter_begin; l != letter_end; ++l) {
            this->emplace(l, T());
        }
    }
};

void print_string_std_letter_map(const std_letter_map<std::string>& lm)
{
    for (const auto& elem : lm)
    {
        std::cout << elem.first << "->" << elem.second << std::endl;
    }
}

int main()
{
    letter_map<std::string> lm;
    // usually I would use auto& elem here
    for (auto elem : lm) {
        auto let = elem.first;
        // usually this would be without the *
        auto& str = *(elem.second);
        str = std::string("foo ") + let;
    }
    print_string_letter_map(lm);
    return 0;
}

Answer 1

实现 operator *很简单 - 只需返回 std::pair<const Key, Value&>或 ..., Value const&>对于 const 迭代器，就像在这个简化的例子中一样:

template <typename T>
class iterator_array_as_map
{
public:

    iterator_array_as_map(T* array, int index) 
       : array(array), index(index) 
    {}

    bool operator == (const iterator_array_as_map& other) const
    {
        return index == other.index;
    }
    bool operator != (const iterator_array_as_map& other) const
    {
        return index != other.index;
    }
    iterator_array_as_map& operator ++ ()
    {
        ++index;
        return *this;
    }

    auto operator * ()
    {
        return std::pair<const int, T&>(index, array[index]);
    }


private:
    T* array;
    int index;
};

和用法:

int main() {
    int array[2] = {2, 4};
    auto begin = iterator_array_as_map<int>(array, 0);
    auto end = iterator_array_as_map<int>(array, 2);

    for (auto it = begin; it != end; ++it)
    {
        std::cout << (*it).first << " " << (*it).second << std::endl;
     }

    (*begin).second = 7;

    for (auto it = begin; it != end; ++it)
    {
        std::cout << (*it).first << " " << (*it).second << std::endl;
    }
}

---

operator ->有点难 - 因为你必须返回需要模拟的东西 pointer to std::pair - 但如果不介意动态内存碎片 - 你可以返回 std::shared_ptr<std::pair<....>> ...

    auto operator -> ()
    {
        return std::make_shared<std::pair<const int, T&>>(index, array[index]);
    }

如果您不想使用动态内存 - 那么您可以尝试使用指向自身的指针解决方案:

template<typename data>    
class pointer_to_data
{
public:
    template<typename ...Arg>
    pointer_to_data(Arg&&... arg)
      : data{std::forward<Arg>(arg)...}
    {}
    Data* operator -> ()
    {
        return &data;
     }
  private:
      Data data;
  };

只需返回上面的内容而不是 shared_ptr...

---

查看此 what-is-the-correct-way-of-using-c11s-range-based-for ，“代理迭代器的特例”部分。无法定义 for(auto&e:b)如果b是例如std::vector<bool> - 因为通常不可能引用临时文件，而且这个容器在这个意义上与您的相似，因为它具有“特殊”引用类型。

您可以尝试让迭代器中的特殊成员保持“返回值”——但这会很麻烦——所以我提出的这个解决方案可能不会更好。