自定义关联容器迭代器：如何返回合法的键值对引用/指针？

我实现了一个关联容器，其内部由两个线性数组实现：一个存储键（Key），一个存储值（Value）。两个数组均保持有序，因此可通过对键数组进行二分查找得到对应值的索引。这种设计旨在当键与值的大小关系严重不对称时提升查询性能，该容器的使用场景为极少修改但频繁查询。

容器的代码实现如下：

template<typename Key, typename Value>
struct Container
{
  // 创建时分配内存
  Key* mKeys;
  Value* mValues; 
  unsigned mCount;

  class iterator
  {
       Container* mContainer;
       unsigned mIndex;

       // 返回支持修改值但不能修改键的 pair
       std::pair<const Key &,Value &> MakePair() { 
           return std::make_pair( mContainer->mKeys[mIndex], 
                                  mContainer->mValues[mIndex] ); 
           };
  
       // 此处没有可返回引用的 std::pair；也不能返回临时对象
       std::pair<const Key,Value> & operator*();   
       std::pair<const Key,Value> * operator->();  
  }

}

我尝试为该容器实现一个迭代器，使其能像std::map那样返回键值对。

我的困惑在于reference operator*()和pointer operator->()的实现：我并没有实际的std::pair可以返回其引用，但仍希望使用container.begin()->first或(*container.begin()).second这样的语法。

请问有什么方法可以返回std::pair<const Key, Value>的引用或指针？或者，我是否可以返回一个持有键和值引用的对象（分别命名为first和second）来满足语法要求？

你完全可以自定义一个模仿std::pair结构的代理类来满足语法需求，这是解决这类问题的常规手段，不需要依赖实际的std::pair实例。

步骤1：定义代理类 #

在迭代器内部定义一个代理类，持有键的const引用和值的引用，并且提供first和second成员，完全匹配std::pair的访问方式：

class iterator
{
    Container* mContainer;
    unsigned mIndex;

    // 自定义代理类，模拟std::pair<const Key&, Value&>的行为
    class proxy
    {
    public:
        const Key& first;
        Value& second;

        proxy(const Key& k, Value& v) : first(k), second(v) {}

        // 支持隐式转换为std::pair<const Key, Value>（如果需要）
        operator std::pair<const Key, Value>() const {
            return {first, second};
        }
    };

public:
    // 迭代器构造函数
    iterator(Container* cont, unsigned idx) : mContainer(cont), mIndex(idx) {}

    // operator* 返回代理对象
    proxy operator*() {
        return proxy(mContainer->mKeys[mIndex], mContainer->mValues[mIndex]);
    }

    // operator-> 返回代理对象的指针
    proxy* operator->() {
        // 更新内部存储的代理实例，返回其指针
        m_proxy = proxy(mContainer->mKeys[mIndex], mContainer->mValues[mIndex]);
        return &m_proxy;
    }

    // 迭代器基础操作：自增
    iterator& operator++() {
        ++mIndex;
        return *this;
    }

    iterator operator++(int) {
        iterator temp = *this;
        ++mIndex;
        return temp;
    }

    // 相等判断
    bool operator==(const iterator& other) const {
        return mContainer == other.mContainer && mIndex == other.mIndex;
    }

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

private:
    proxy m_proxy; // 用于operator->的临时存储
};

方案原理 #

• 对于(*it).second的语法：operator*返回的代理对象直接拥有second成员，可以直接访问，且值的引用会直接关联到原容器的数组元素，修改会同步到容器内。
• 对于it->first的语法：C++中operator->会被链式调用，直到返回一个指针，这里返回的proxy*的first成员会被正确访问，完全符合语法要求。
• 键的const引用保证了迭代器无法修改容器内的键，符合你的设计需求。

不推荐的临时对象方案 #

如果尝试直接返回std::pair<const Key&, Value&>的临时对象，operator*可以这样写：

std::pair<const Key&, Value&> operator*() {
    return {mContainer->mKeys[mIndex], mContainer->mValues[mIndex]};
}

但这种方式下operator->无法直接实现——临时对象的指针不能被返回，会导致悬空指针问题，因此代理类方案是更可靠的选择。

内容的提问来源于stack exchange，提问作者Steven