Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Можно ли с помощью других стандартнных алгоиртмов реализовать такую же функцию для алгоритма std::find_end, то есть чтобы находить в строке подстроку, состоящую из n одинаковых значений?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм std::find_end - аналог std::search_n (C++):

Не воспринимает ни std::cout, ни std::cin. Вобщем ничего из std. Также не понимает iostream - C++
Здравствуйте! Я хотел начать изучать язык C++. Набрал литературы. Установил Microsoft Visual C++ 2005 Express Edition. Образ диска...

ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri - C++
на вод поступают 2 строки типа string. определить количество вхождений строки 2 в строку 1 ошибка error: cannot convert 'std::string {aka...

STL std::set, std::pair, std::make_pair - C++
Я не знаю как описать тему в двух словах, поэтому не обращайте внимание на название темы. Собственно перейдем к нашим баранам: есть...

На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами - C++
подскажите есть вот такая задача. Есть список . Создать второй список, в котором будут все эти же числа, но не в виде строк, а в виде...

(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const& - C++
astxx::manager::connection::connection(std::basic_string&lt;char, std::char_traits&lt;char&gt;, std::allocator&lt;char&gt; &gt; const&amp;, unsigned short); ...

Как искать по std::vecotr из std::pait по одному значению из пары? - C++
? :) Пункт 4.7 Правил: Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты...

10
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
03.08.2011, 21:06 #2
Ну накидал бы свою реализацию, максимально близкую на твой взгляд к желаемой. А то получится как в прошлый раз
0
Сыроежка
Заблокирован
03.08.2011, 21:22  [ТС] #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() );

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

C++
1
int a[] = { 10, 10, 10, 10, 10, 10, 10, 10 10, 10, 10, 10, 10 };
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
03.08.2011, 21:49 #8
Да, если начинать поиск со следующей позиции после начала найденного интервала то согласен. Продолжать поиск надо начиная со следующего, за конечным, а конечный результат придётся корректировать. Когда ожидать изменения в стандарте?
0
Сыроежка
Заблокирован
03.08.2011, 21:51  [ТС] #9
Цитата Сообщение от grizlik78 Посмотреть сообщение
Да, если начинать поиск со следующей позиции после начала найденного интервала то согласен. Продолжать поиск надо начиная со следующего, за конечным, а конечный результат придётся корректировать. Когда ожидать изменения в стандарте?
Сначала надо посмотреть, что народ скажет по поводу этого алгоритма.
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
03.08.2011, 22:03 #10
Кстати, если посмотреть на требования по сложности, которые предъявляются стандартом к find_end и search_n, то даже такая тупая реализация вполне допустима Хотя, надеюсь, разработчики библиотеки используют более эффективные алгоритмы.
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
03.08.2011, 23:30 #11
Сыроежка, boost::algorithm::string Наслаждайтесь.
1
03.08.2011, 23:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2011, 23:30
Привет! Вот еще темы с ответами:

Реализация класса MyString. Стандартная библиотека, std::string, std::vector - C++
как добавить реализацию конкатенации строк через перегрузку оператора &quot;+=&quot; в классе MyString и почему ошибка выдается???#include...

Операция std::cout для Объекта типа std::string - C++
Кто детально объяснит почему не выводит ? Дает вот так &quot;Отсутствует оператор &quot;&lt;&lt;&quot;, соответствующий этим операндам&quot; void...

что использовать std::cout или просто using namespace std? - C++
Приветствую! Сейчас учу С++, постигаю азы так сказать. В арсенале две книги - Джефф Кент, &quot;Основы программирования &quot; и Х.М....

Передача функции указатель на элемент std::vector<std::string> - C++
Доброй ночи тем, кому не спится (или живет в другом часовом поясе:p)! Есть функция, требующая в качестве параметра указатель на...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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