C++ 链表：重载方括号运算符 []

Question

所以，我决定回顾一些数据结构来保持自己的敏锐度；）

我开始实现哈希表时，想起需要链表来避免哈希冲突。于是我开始了我的链表...

我实现了链表类的所有功能方法（添加、获取、删除等），然后我决定尝试一些之前没有尝试过的东西。重载数组索引运算符，使得可以像访问数组一样检索或分配链表索引。

我成功地实现了检索部分：

template <class T>
T LinkedList<T>::operator[](const int &i) {
    return get(i);
}

get函数返回相关节点的数据，而非节点本身...setter应该将提供的值存储到给定索引处节点的数据属性中...我的设想是用户不需要接触ListNode类。

我的最终目标是拥有一个智能LinkedList，它会表现得像这样：

LinkedList<int> list;

list[0] = 1;    //Allocates memory for 0th node and stores 1 as the data
list[3] = 2;    //Allocates memory for 1th,2th,and 3th nodes and sets 2 as the data
                //Unassigned nodes should use default constructors on data

int a = list[3];  //Sets a to 2
cout << list[0] << endl;  //prints 1

getter 方法运行良好，但是 setter 方法出了问题。假设 set 函数已经完成了所有的索引错误检查和内存分配。如果有任何帮助，将不胜感激。如果无法实现，请在我继续投入时间之前告诉我。谢谢。

- jyore

---

由于getter函数必须实现为迭代，因此似乎很容易添加setter。然而，我认为这个接口使用起来会很笨拙。在上面的示例中，碰撞列表的预期“大小”是多少？作为用户，我如何知道两个项目[1,2]是“空”的？您计划如何在删除时保持关联性，因为常数时间删除是链接列表的主要优势之一？ - Chad

Answer 1

看起来您想通过引用返回节点：

template <typename T>
class LinkedList {
...
  T& operator[](const size_t& i) { return this->get(i); }
  const T& operator[](const size_t& i) const { return this->get(i); }
...
};

（还假设LinkedList::get()返回引用）

- justin

---

const size_t＆i 没有太多意义，因为它不是必需的。size_t i就足够了。 - Nawaz

@Justin：我认为这有些过度了。或者你认为这样会让调用更快？ - Nawaz

@Nawaz 在我编写的 C++ 程序和库中，通过 const 引用传递参数是默认惯例。如果在特定情况下有充分的理由偏离惯例，我会这样做。 - justin

@Justin：它引发的问题是为什么“在C++程序中通过const引用传递参数是默认约定”？ - Nawaz

因为我偏爱一致的书写风格，只有少数例外情况："通过const引用传递参数，如果参数被改变则通过引用传递。必要时可以进行异常处理。"而不是其他方法，例如："如果它们是内置的，则按值传递，并且某些类型如果它们很小并且复制起来很容易，或者如果在实现中必须进行复制/更改，则通过const引用...但可变参数应通过指针传递"。优化器仍然可以发挥作用。希望这有所帮助...但为什么这变得如此重要呢？毕竟，OP也通过const引用传递了。 - justin

Answer 2

operator[]和get()应该返回数据的引用。

template <class T>
T& LinkedList<T>::operator[](const int &i) {
    return get(i);
}

- Pubby