c++ - 如何在 C++ 中比较两个非随机访问迭代器

Question

我有这个:

vector<int> vec = {10, 4, 18, 7, 2, 10, 25, 30};
auto& pos25 = find(vec.cbegin(), vec.cend(), 25);
auto& pos18 = find(vec.cbegin(), vec.cend(), 18);

现在，我想查询在两个位置之间搜索 7。我可以使用 operator<在 pos25 之间和 pos18因为它们是随机访问迭代器，所以我可以 find 7 在该范围内的位置。

但是如果我的容器是 forward_list 怎么办？ .我将如何实现，因为我没有 operator<比较这两个迭代器；因此我不知道是否pos25或 pos18首先出现给find一个范围功能。

我在一本书上找到了这个方法:

pos18 = find (vec.begin(), vec.end(), // range
18); // value
pos25 = find (vec.begin(), pos18, // range
25); // value
if (pos18 != coll.end() && pos25 != pos18) {
// pos25 is in front of pos18
// so, only [pos25,pos18) is valid
...
}
else {
pos25 = find (pos25, vec.end(), // range
25); // value
if (pos25 != coll.end()) {
// pos18 is in front of pos25
// so, only [pos18,pos25) is valid
...
}
else {
// 18 and/or 25 not found
...
}
}

虽然这很简单，但有没有更高效的方法呢？

Answer 1

迭代链表的成本相对较高，因为必须对内存进行潜在访问。您需要尽量减少这些访问。为此，您可以做几件事:

1. 使用find_if搜索 18 或 25
2. 然后再次使用 find_if 从 那个点搜索 7 或另一个边界
3. 如果第 1^st 找到另一个边界，则没有干预 7 如果首先找到 7 确保另一个边界存在<

因此您的代码可能如下所示:

const auto start = find_if(cbegin(vec), cend(vec), [](const auto& i){ return i == 18 || i == 25; });
const auto target = find_if(start, cend(vec), [finish = *start == 18 ? 25 : 18](const auto& i){ return i == 7 || i == finish; });
const auto finish = *target == 7 ? find(target, cend(vec), *start == 18 ? 25 : 18) : cend(vec);

在此之后，如果 finish 不指向 cend(vec)，则 target 是指向 1^{st 的有效指针} 7 在范围内。

Live Example

---

Vlad from Moscow's solution通过使用 find_first_of 巧妙地避免了对 lambda 的需要，但它不止一次迭代 vec 的内容，使其比我的算法更昂贵。这两种算法的结合产生了一种比我原来的算法更快的算法，同时保留了只访问每个元素一次的好处:

const int a[] = { 18, 25 };
const auto start = find_first_of(cbegin(vec), cend(vec), cbegin(a), cend(a));
const int b[] = { *start == *cbegin(a) ? *crbegin(a) : *cbegin(a), 7 };
const auto target = find_first_of(start, cend(vec), cbegin(b), cend(b));
const auto finish = *target == *crbegin(b) ? find(target, cend(vec), *cbegin(b)) : cend(vec);

同样，如果 finish 不指向 cend(vec)，则 target 是指向 1^{st< 的有效指针/sup> 7 在范围内。}

Live Example