Как сравнить два неслучайный итератор доступа в 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); 

Теперь я хочу, чтобы сделать запрос для поиска между там две позиции. Я могу просто использовать operator< между pos25 и pos18, так как они случайные итераторы acess, а затем я могу find местоположение в этом диапазоне.

Но что делать, если мой контейнер является 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 или
2. Тогда поиск из что точка с find_if снова либо или другая связанная связь
3. Если бы другая граница была найдена 1 ^st нет если был найден первый обеспечить другой грань существует

Так что ваш код может выглядеть следующим образом:

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 в диапазоне.

Live Example

---

Vlad from Moscow's solution ловко избежать необходимости лямбды с помощью find_first_of, но итерации содержимое более vec, чем когда-то, что делает его более дорогим, чем мой алгоритм. Брак этих 2-х алгоритмов приводит к алгоритму, который быстрее, чем мой оригинал, сохраняя преимущество только доступ к каждому элементу раз:

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 7 в диапазоне.

Live Example

Answer 2

У вас нет никаких вариантов, чтобы сравнить два ForwardIterator «s кроме operator ==. Это означает, что у вас есть только два способа:

1. Используйте std::find, чтобы гарантировать, что итераторы принадлежат к определенной части вашего массива. Этот метод реализован в коде, который вы указали, и в ответе @ Джонатана.
2. Сравните два итератора, написав специальную процедуру для таких операций.

Например, вы можете написать следующий код:

template<typename ForwardIterator> 
bool less(ForwardIterator lhs, ForwardIterator rhs, ForwardIterator end) { 
    if (lhs == rhs) { 
     return false; // Equal 
    } 
    while (lhs++ != end) { 
     if (lhs == rhs) { 
      return true; // rhs is after lhs 
     } 
    } 
    return false; // lhs is after rhs 
} 

Обратите внимание, что эта процедура предполагает, что оба итератора принадлежат к одной и той же емкости и имеет линейную временную сложность.

Лично я рекомендовал бы в такой ситуации использовать RandomAccessIterator. Да, std::list не предоставляет один, но вместо этого вы можете использовать std::vector.

Answer 3

Для начала этот фрагмент кода (если обновить опечатку) неправильно

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); 

Вы не можете связать временный объект с непостоянной ссылки.

Что касается этого подхода

pos18 = find (vec.begin(), vec.end(), // range 
18); // value 
pos25 = find (vec.begin(), pos18, // range 
25); // value 

, то вам нужно будет проверить много условий. Например перед вызовом

pos25 = find (vec.begin(), pos18, // range 
25); // value 

вы должны проверить, является ли pos19 не равна vec.end().

Что касается определения, какой итератор меньше или больше, чем вы можете использовать стандартную функцию std::distance. Однако он неэффективен для итераторов контейнера std::forward_list.

Более эффективным подходом является использование стандартного алгоритма std::find_first_of вместо алгоритма std::find для поиска первого итератора диапазона.

Вот демонстративной программа

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    std::vector<int> vec = { 10, 4, 18, 7, 2, 10, 25, 30 }; 
    int a[] = { 25, 18 }; 

    auto first = std::find_first_of(vec.cbegin(), vec.cend(), 
     std::begin(a), std::end(a)); 

    auto last = vec.cend(); 
    auto target = vec.cend(); 

    if (first != vec.cend()) 
    { 
     last = std::find(first, vec.cend(), 
      *first == a[0] ? a[1] : a[0]); 
    } 

    if (last != vec.cend()) 
    { 
     target = std::find(first, last, 7); 
    } 

    if (target != vec.end()) 
    { 
     std::cout << 7 << " is between " << *first 
      << " and " << *last << std::endl; 
    } 
} 

Выход программы является

7 is between 18 and 25