Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
Сыроежка
Заблокирован
#1

Алгоритм std::find_end - аналог std::search_n - C++

03.08.2011, 20:58. Просмотров 2655. Ответов 10
Метки нет (Все метки)

Есть два семейства стандартных алгоритмов: std::search и std::find_end. Первое семейство предназначено для поиска первого совпадения подстроки в строке, второе - для поиска последнего совпадения подстроки в строке. Но у семейчтва std::search есть вариация, называемая std::search_n, которая позволяет найти в строке подстроку, состоящую из n одинаковых значений.

Можно ли с помощью других стандартнных алгоиртмов реализовать такую же функцию для алгоритма std::find_end, то есть чтобы находить в строке подстроку, состоящую из n одинаковых значений?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 20:58     Алгоритм std::find_end - аналог std::search_n
Посмотрите здесь:
Как искать по std::vecotr из std::pait по одному значению из пары? C++
C++ что использовать std::cout или просто using namespace std?
Операция std::cout для Объекта типа std::string C++
C++ Как можно еще использовать std::placeholders вне в связки с std::bind?
C++ зачем часто писать std:: если можно один раз using namespace std?
C++ Стандартный поток и STL (std::copy to std::cout)
C++ Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
03.08.2011, 21:06     Алгоритм std::find_end - аналог std::search_n #2
Ну накидал бы свою реализацию, максимально близкую на твой взгляд к желаемой. А то получится как в прошлый раз
Сыроежка
Заблокирован
03.08.2011, 21:22  [ТС]     Алгоритм std::find_end - аналог std::search_n #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Ну накидал бы свою реализацию, максимально близкую на твой взгляд к желаемой. А то получится как в прошлый раз
У меня есть своя, то есть оригинальная реализация этого алгоритма. Но меня интересует, как решить такую задачу на основе существующих алгоритмов? Например, один из способов - это создать вектор из нужного числа элементов, а затем запустить std::find_end Допустим, нужно в массиве найти последние три совпадающих элемента равных 10. Тогда можно написать

C++
1
2
3
4
int a[] = { 10, 10 , 10, 1, 2, 3, 10, 10, 4, 5, 6, 10, 10, 10, 2, 10, 10 };
std::vector<int> v( 3, 10 ); 
 
int *p = std::find_end( a, a + sizeof( a ) / sizeof( *a ), v.begin(), v.end() );

Но это выглядет слишком вычурно. Может быть есть еще какие-то приемы?
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
03.08.2011, 21:27     Алгоритм std::find_end - аналог std::search_n #4
Сыроежка, ну я пока не очень задумывался, но первая мысль: использовать std::search_n с реверс-итераторами. Оно, конечно, найдёт конец последнего вхождения, и итератор, вроде, реверсивным останется, но n известно, значит легко получить и прямой итератор на начало. Нет?
Сыроежка
Заблокирован
03.08.2011, 21:31  [ТС]     Алгоритм std::find_end - аналог std::search_n #5
Цитата Сообщение от grizlik78 Посмотреть сообщение
Сыроежка, ну я пока не очень задумывался, но первая мысль: использовать std::search_n с реверс-итераторами. Оно конечно найдёт конец последнего вхождения, и итератор, вроде, реверсивным останется, но n известно, значит легко получить и прямой итератор на начало. Нет?
Здоровая первая мысль! Проблема только в том, что алгоритм std::find_end потому и создан, что он рассчитан на последовательные итераторы, а не начиная с двунаправленных итераторов. В этом и состоит проблема. То есть почему возник такой алгоритм, как std::find_end? Есть же однонаправленные контейнеры, как, например, односвязный список. И для них реверсивные итераторы не подходят. Поэтому и нужен алгоритм std::find_end. Но только для него почему-то забыли написать аналог std::search_n....
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
03.08.2011, 21:35     Алгоритм std::find_end - аналог std::search_n #6
для однонаправленных search_end всё-равно вынужден просмотреть контейнер от начала и до конца. Иначе откуда он узнает, что это последнее совпадение? А раз так, то никто не мешает search_n в цикле выполнять, пока что-то находится.
Другое дело, если цикл по религиозным соображениям недопустим
Сыроежка
Заблокирован
03.08.2011, 21:39  [ТС]     Алгоритм std::find_end - аналог std::search_n #7
С циклом связаны не только религиозные предубеждения, но и некоторая неэффективность запуска алгоритма std::search_n последовательно для каждого следующего элемента последовательности, если она состоит из элементов одного значения. Например,

C++
1
int a[] = { 10, 10, 10, 10, 10, 10, 10, 10 10, 10, 10, 10, 10 };
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
03.08.2011, 21:49     Алгоритм std::find_end - аналог std::search_n #8
Да, если начинать поиск со следующей позиции после начала найденного интервала то согласен. Продолжать поиск надо начиная со следующего, за конечным, а конечный результат придётся корректировать. Когда ожидать изменения в стандарте?
Сыроежка
Заблокирован
03.08.2011, 21:51  [ТС]     Алгоритм std::find_end - аналог std::search_n #9
Цитата Сообщение от grizlik78 Посмотреть сообщение
Да, если начинать поиск со следующей позиции после начала найденного интервала то согласен. Продолжать поиск надо начиная со следующего, за конечным, а конечный результат придётся корректировать. Когда ожидать изменения в стандарте?
Сначала надо посмотреть, что народ скажет по поводу этого алгоритма.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
03.08.2011, 22:03     Алгоритм std::find_end - аналог std::search_n #10
Кстати, если посмотреть на требования по сложности, которые предъявляются стандартом к find_end и search_n, то даже такая тупая реализация вполне допустима Хотя, надеюсь, разработчики библиотеки используют более эффективные алгоритмы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2011, 23:30     Алгоритм std::find_end - аналог std::search_n
Еще ссылки по теме:
C++ В чем отличия между std::cref() и std::bind()?
C++ Как правильно перевести std::wstring в std::string ?
статическая и динамическая матрица на std::array and std::vector C++
Какая реализация лучше? std::pointer_to_binary_function vs std::function C++
Стоит ли очищать в деструкторе std::map , std::vecotor? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
03.08.2011, 23:30     Алгоритм std::find_end - аналог std::search_n #11
Сыроежка, boost::algorithm::string Наслаждайтесь.
Yandex
Объявления
03.08.2011, 23:30     Алгоритм std::find_end - аналог std::search_n
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru