稀疏向量的重载算子[]

Question

我试图在C++中创建一个“稀疏”向量类，如下所示：

template<typename V, V Default>
class SparseVector {
    ...
}

在内部，它将由一个std::map<int, V>表示(其中V是存储的值的类型)。如果映射中没有元素，我们将假装它等于模板参数中的值Default。

但是，我在重载下标操作符[]时遇到了问题。我必须重载[]操作符，因为我要将对象从该类传递到一个期望[]正常工作的Boost函数中。

const版本非常简单:检查索引是否在映射中，如果是，则返回其值，否则返回Default。

然而，非const版本要求我返回一个引用，而这正是我遇到麻烦的地方。如果只读取值，则不需要(也不希望)向地图添加任何内容；但如果正在编写该值，则可能需要在地图中添加一个新条目。问题是，重载的[]不知道是读取还是写入一个值。它只是返回一个引用。

有办法解决这个问题吗？或者绕开这条路？

Answer 1

可能有一些非常简单的技巧，但我认为operator[]只需要返回一些可以从V(并转换为V)的东西，而不一定是V&。因此，我认为您需要使用重载的operator=(const V&)返回一些对象，这将在稀疏容器中创建条目。

您将必须检查Boost函数如何使用其模板参数--用户定义的转换到V会影响到哪些转换链是可能的，例如，防止在同一链中出现更多用户定义的转换。

Answer 2

不要让非const操作符和实现返回引用，而是返回代理对象。然后，您可以实现代理对象的赋值操作符，以区分对operator[]的读访问和写访问。

这里有一些代码草图来说明这个想法。这种方法不是很好，但很好-这是C++。C++程序员不会浪费时间参加选美比赛(他们也不会有机会)。;-)

template <typename V, V Default>
ProxyObject SparseVector::operator[]( int i ) {
   // At this point, we don't know whether operator[] was called, so we return
   // a proxy object and defer the decision until later
   return ProxyObject<V, Default>( this, i );
}

template <typename V, V Default>
class ProxyObject {
    ProxyObject( SparseVector<V, Default> *v, int idx );
    ProxyObject<V, Default> &operator=( const V &v ) {
      // If we get here, we know that operator[] was called to perform a write access,
      // so we can insert an item in the vector if needed
    }

    operator V() {
      // If we get here, we know that operator[] was called to perform a read access,
      // so we can simply return the existing object
    }
};

Answer 3

我想知道这个设计是否合理。

如果要返回引用，这意味着类的客户端可以将调用operator[]的结果存储在引用中，并在以后的任何时候对其进行读取/写入。如果您不返回引用，并且/或不每次处理特定索引时插入一个元素，那么它们如何做到这一点？(而且，我觉得标准需要一个提供operator[]的适当的STL容器来让该操作符返回一个引用，但我不确定。)

您可能也可以通过给代理提供一个operator V&() (它将创建条目并分配默认值)来规避这一问题，但我不确定这是否会打开另一个循环洞--在某些情况下我还没有想到。

std::map通过指定该操作符的非const版本总是插入一个元素(而根本不提供const版本)来解决这个问题。

当然，您总是可以说这不是现成的STL容器，而且operator[]不返回用户可以存储的普通引用。也许这没什么关系。我只是好奇。