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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
Сыроежка
Заблокирован
03.08.2011, 20:58     Алгоритм std::find_end - аналог std::search_n #1
Есть два семейства стандартных алгоритмов: std::search и std::find_end. Первое семейство предназначено для поиска первого совпадения подстроки в строке, второе - для поиска последнего совпадения подстроки в строке. Но у семейчтва std::search есть вариация, называемая std::search_n, которая позволяет найти в строке подстроку, состоящую из n одинаковых значений.

Можно ли с помощью других стандартнных алгоиртмов реализовать такую же функцию для алгоритма std::find_end, то есть чтобы находить в строке подстроку, состоящую из n одинаковых значений?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
Еще ссылки по теме:

Передача функции указатель на элемент std::vector<std::string> C++
C++ что использовать std::cout или просто using namespace std?
Как искать по std::vecotr из std::pait по одному значению из пары? C++

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Ответ Создать тему
Опции темы

Текущее время: 14:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru