如何用链表代替std::vector

Question

我使用std::vector来制作我的算法。我想用链表代替向量

为了做到这一点，我正在考虑使用std::list，但我不知道如何做到这一点，例如，我已经尝试了以下示例来查找向量/列表中的值:

void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2)
{
  if (input_vector[0] >= value) { // too small
    rv1 = 0; rv2 = 0; return;
  }
  int index = (int)input_vector.size() - 1;
  if (input_vector[index] <= value) { // too big
    rv1 = index; rv2 = index; return;
  }
  // somewhere inside
  index = 0;
  while (input_vector[index] <= value) {
    index++;
  }
  rv1 = index - 1; rv2 = index; return;
}
void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2)
{
  if (*input_list.begin() >= value) { // too small
    rv1 = 0; rv2 = 0; return;
  }
  if (*input_list.end() <= value) { // too big
    rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return;
  }
  // somewhere inside
  int index = 0; int temp = *input_list.begin();
  while (temp <= value) {
    temp = *input_list.next(); index++;
  }
  rv1 = index - 1; rv2 = index; return;
}

这似乎不起作用，因为成员函数next()不存在。然而，我记得浏览链表是通过从开始开始，并进一步移动到下一个元素，直到到达某个点来完成的。我已经看到有一种方法可以通过在for循环中使用interator来完成此操作，但我想知道我的方法有什么问题?我的印象是std::list是一个双向链表的标准实现，或者我错了，在这种情况下，什么std类是一个链表的实现(它不需要是一个双向链表)?

Answer 1

遍历容器的标准方法如下:

for(std::list<int>::iterator it = input_list.begin();
    it != input_list.end();
    it++)
{
    ....
}

这也适用于vector,map,deque等。迭代器的概念在整个STL中都是一致实现的，所以最好习惯这个概念。

对于不同类型的迭代器，还有std::distance和std::advance等迭代器操作(我建议你仔细阅读它们以及它们的优点/局限性)

如果你有c++ 11可用，你也可以使用这个语法(可能对你的问题没有帮助)

for(const auto& value : input_list)
{
   ...
}

这也适用于整个STL容器。

Answer 2

对于vector、list、deque和set(假设内容已经排序)都可以使用。

template <class T>
void find_values_in_container(const T& container, int value, int &rv1, int &rv2)
{
  rv1 = rv2 = 0;  // Initialize
  if (container.empty() || container.front() >= value)
  {
    return;
  }
  for (const auto& v : container)
  {
     rv2++;
     if (v > value)
     {
         break;
     }
     rv1++;
  }
  return;
}