Блог

Главная - Вопросы по программированию - std::поиск, чтобы найти крайнюю правую подпоследовательность

std::поиск, чтобы найти крайнюю правую подпоследовательность

#c #algorithm #c 11 #c 14

#c #алгоритм #c 11 #c 14

Вопрос:

Я пытаюсь найти крайнюю правую подпоследовательность в диапазоне с std::search помощью и std::make_reverse_iterator .

Однако возвращаемый итератор всегда указывает на начало диапазона. Что я делаю не так?

 TEST(basic_test, find_from_right)
{
    std::vector<uint8_t> array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::array<uint8_t, 2> subSeq{3, 4};

    auto found = std::search(std::make_reverse_iterator(array.cend()),
                             std::make_reverse_iterator(array.cbegin()),
                             subSeq.cbegin(),
                             subSeq.cend());
// makes no difference
//                             std::make_reverse_iterator(subSeq.cend()),
//                             std::make_reverse_iterator(subSeq.cbegin()));


    auto distance = std::distance(found.base(), array.cbegin());

    EXPECT_EQ(distance, 3);
}

Вывод:

 Failure
Expected equality of these values:
  distance
    Which is: 0
  3

У меня есть функция, которая снабжена 2 шаблонами RandomIterators, поэтому я должен вызвать std::make_reverse_iterator . Эти контейнеры предназначены только для воспроизведения проблемы и компиляции примера.

Комментарии:

1. Вы выполняете поиск в обратном направлении, поэтому последовательности 3, 4 отсутствуют в вашем векторе. Если вы искали 4, 3, это должно сработать.

2. @john тогда как насчет раскомментированного кода, когда я ищу подпоследовательность с обратными итераторами? Он по-прежнему ничего не находит.

3. Уже пробовал отладку? Каковы ваши выводы?

4. Если вы используете обратные итераторы, но хотите получить смещение к началу искомой подпоследовательности, то вам необходимо учитывать длину подпоследовательности. Пример здесь . Справедливое предупреждение: убедитесь, что ваша подпоследовательность действительно была найдена, прежде чем выполнять этот окончательный расчет.

5. @john Ну, если я буду искать подпоследовательность {4, 3} , она найдет reverse_iterator указание на 4-й элемент. Я думаю, это можно рассматривать как ответ

Ответ №1:

Я думаю, это могло бы решить вашу проблему (если вас устраивает C 17).:

Из https://en.cppreference.com/w/cpp/algorithm/find_end:

 #include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    std::vector<int>::iterator resu<
 
    std::vector<int> t1{1, 2, 3};
 
    result = std::find_end(v.begin(), v.end(), t1.begin(), t1.end());
    if (result == v.end()) {
        std::cout << "sequence not foundn";
    } else {
        std::cout << "last occurrence is at: "
                  << std::distance(v.begin(), result) << "n";
    }
 
    std::vector<int> t2{4, 5, 6};
    result = std::find_end(v.begin(), v.end(), t2.begin(), t2.end());
    if (result == v.end()) {
        std::cout << "sequence not foundn";
    } else {
        std::cout << "last occurrence is at: " 
                  << std::distance(v.begin(), result) << "n";
    }
}

Итак, в вашем случае:

     auto result = std::find_end(array.begin(), array.end(), subSeq.begin(), subSeq.end());
    if (result == array.end()) {
        std::cout << "sequence not foundn";
    } else {
        std::cout << "last occurrence is at: "
                  << std::distance(array.begin(), result) << "n";
    }