Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
Заблокирован

Реализация алгоритма find_firdt_not_of через другие алгоритмы

31.07.2011, 18:44. Показов 6105. Ответов 55
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Хотел создать эту тему в разделе С/С++ для экспертов, но мне было отказано в виду отсутствия неких прав. Поэтому формулирую тему здесь.

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
31.07.2011, 18:44
Ответы с готовыми решениями:

Алгоритмы поиска. Подскажите, в чем суть алгоритма?
нужно написать алгоритм поиска прямым методом (С.Чарас), а я понятия не имею, что это за метод и в и-нэте найти не могу(

Для одномерного массива составить блок схему алгоритма - Алгоритмы
Доброго времени суток, прошу помощи в составлении алгоритма.. Задан одномерный массив {xi} (i=1,2,...,n). Значение элементов...

Циклические алгоритмы. Реализация рядов
Всем привет. Задали контрольную, есть задание: вывести на экран таблицу значений функции y(x) для х, изменяющегося от 0.1 до 1.2 с шагом...

55
Заблокирован
02.08.2011, 04:20  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от grizlik78 Посмотреть сообщение
Алгоритм find, в отличие от find_first_not_of, требуется довольно часто. Видимо алгоритм find_first_not_of кроме как для строк некому особо нужен не был, а Сыроежка не являлся членом комиссии по стандартизации. Или есть сведения, что было предложение включить этот алгоритм в стандарт, но оно было отклонено? Стандартная библиотека не может объять необъятное.
Кстати, если верить Джосаттису, даже алгоритм find_first_of не входил в исходную версию STL, чего не скажешь про find.
На счет исходной версии STL надо смотреть библиотеку Hewlett-Packard. Насколько мне известно, напротив, в ней было много алгоритмов, которые не вошли в стандарт. И даже алгоритм copy_if был исключен из стандарта Строустропом, после чего сам Строустроп по этому поводу постоянно извинялся перед программистами в своих книгах.

Что касается find_first_not_of, то я понимаю, почему он включен в класс std::basic_string. Дело в том, что в С есть аналогичная функция strspn, поэтому было очевидно решено реализовать такую функцию для класса basic_string. Но тем не менее в любом случае на мой взгляд было бы корректно сделать такой же общий алгоритм в стандарт.

То есть я рассматриваю эту постановку вопроса как упущение стандарта.

Добавлено через 16 минут
Цитата Сообщение от grizlik78 Посмотреть сообщение
Ну уж нет. У equal_to оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
Да, вы правы. Я в данном случае имел в виду некоммутативные операции для одного типа. Тем более это демонстрирует то, что реализация алгоритма через другие стандартные алгоритмы совершенно не очевидна.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 04:27
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я в данном случае имел в виду некоммутативные операции для одного типа.
Ну если для разных типов некоммутативное сравнение ещё как-то можно с натяжкой понять/оправдать, то для однотипных некоммутативное сравнение на равенство и некоммутативный предикат эквивалентности — это практически преступление!

Цитата Сообщение от Сыроежка Посмотреть сообщение
Тем более это демонстрирует то, что реализация алгоритма через другие стандартные алгоритмы совершенно не очевидна.
Ну не знаю, для меня с использованием 2 функторов вполне очевидна, через алгоритм find(_if)
0
Заблокирован
02.08.2011, 04:27  [ТС]
Цитата Сообщение от easybudda Посмотреть сообщение
Это, конечно, хорошо, что есть, кому мне замечания делать. Проблема в другом. С алгоритмом всё в порядке и никакие костыли ему не нужны. Просто не пытайтесь круглое с красным сравнивать. Ещё раз говорю - проверьте логику своей программы - 99.9 % проще всё можно сделать.

Не по теме:

Следующий по логике вопрос - "Почему меня не спросили?" ;)

Причем здесь логика "моей программы"? Вы попробуйте для этого алгоритма написать версию с предикатом. И как вы там будете переставлять операнды для предиката?!
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
02.08.2011, 05:00
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вы попробуйте для этого алгоритма написать версию с предикатом.
Да не вопрос!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <functional>
 
template <class ForwardIter1, class ForwardIter2>
ForwardIter1 find_first_not_of(ForwardIter1 start1, ForwardIter1 stop1, ForwardIter2 start2, ForwardIter2 stop2){
    ForwardIter1 i;
    for ( i = start1; i != stop1; ++i )
        if ( std::find(start2, stop2, *i) == stop2 )
            break;
    return i;
}
 
template <class ForwardIter1, class ForwardIter2, class BinPred>
ForwardIter1 find_first_not_of(ForwardIter1 start1, ForwardIter1 stop1, ForwardIter2 start2, ForwardIter2 stop2, BinPred bp){
    ForwardIter1 i;
    for ( i = start1; i != stop1; ++i )
        if ( std::find_if(start2, stop2, std::bind1st(bp,*i)) == stop2 )
            break;
    return i;
}
 
 
int main(void){
    const int SIZE = 5;
    int arr1[SIZE] = { 1, 2, 3, 11, 5 };
    int arr2[SIZE] = { 6, 7, 8, 9, 10 };
    int * ptr;
    
    if ( ( ptr = (int*)find_first_not_of(arr1, arr1 + SIZE, arr2, arr2 + SIZE, std::less<int>()) ) == arr1 + SIZE )
        std::cout << "all elements from arr1 less then elements from arr2" << std::endl;
    else 
        std::cout << "First element from arr1 that is bigger elements in arr2 is " << *ptr << std::endl;
    
    return 0;
}
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 05:12
Без циклов и с некоммутативным предикатом
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <vector>
 
template <typename Iter, typename Pred>
class NotIn
{
    Iter b;
    Iter e;
    Pred p;
public:
    NotIn(Iter const& start, Iter const& stop, Pred const& pred) :
        b(start), e(stop), p(pred) {}
    template <typename T>
    bool operator() (T const& v) const
        { return std::find_if(b, e, std::bind2nd(p, v)) == e;   }
};
 
template <typename Iter1, typename Iter2, typename Pred>
Iter1 find_first_not_of(Iter1 start1, Iter1 stop1, Iter2 start2, Iter2 stop2, Pred const& p)
{
    return std::find_if(start1, stop1, NotIn<Iter2, Pred>(start2, stop2, p));
}
 
class MyInt
{
    int iv;
public:
    MyInt() : iv() {}
    explicit MyInt(int v) : iv(v) {}
    MyInt(MyInt const& mi) : iv(mi.iv) {}
    bool operator == (int v) const { return iv == v; }
};
 
struct MyIntEqualToInt : public std::binary_function<MyInt, int, bool>
{
    bool operator() (MyInt const& mi, int v) const
        { return mi == v; }
};
 
int main(void){
    const int SIZE = 5;
    int arr1[SIZE] = { 1, 2, 3, 6, 5 };
    std::vector<MyInt> arr2;
    arr2.push_back(MyInt(1));
    arr2.push_back(MyInt(2));
    arr2.push_back(MyInt(3));
    arr2.push_back(MyInt(4));
    arr2.push_back(MyInt(5));
    int * ptr;
 
    if ( ( ptr = (int*)find_first_not_of(arr1, arr1 + SIZE,
                    arr2.begin(), arr2.end(),
                    MyIntEqualToInt()) 
         ) == arr1 + SIZE )
        std::cout << "all elements from arr1 found in arr2" << std::endl;
    else 
        std::cout << "First element from arr1 that not found in arr2 is " << *ptr << std::endl;
 
    return 0;
}
0
Заблокирован
02.08.2011, 05:15  [ТС]
Цитата Сообщение от easybudda Посмотреть сообщение
Да не вопрос!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <functional>
 
template <class ForwardIter1, class ForwardIter2>
ForwardIter1 find_first_not_of(ForwardIter1 start1, ForwardIter1 stop1, ForwardIter2 start2, ForwardIter2 stop2){
    ForwardIter1 i;
    for ( i = start1; i != stop1; ++i )
        if ( std::find(start2, stop2, *i) == stop2 )
            break;
    return i;
}
 
template <class ForwardIter1, class ForwardIter2, class BinPred>
ForwardIter1 find_first_not_of(ForwardIter1 start1, ForwardIter1 stop1, ForwardIter2 start2, ForwardIter2 stop2, BinPred bp){
    ForwardIter1 i;
    for ( i = start1; i != stop1; ++i )
        if ( std::find_if(start2, stop2, std::bind1st(bp,*i)) == stop2 )
            break;
    return i;
}
 
 
int main(void){
    const int SIZE = 5;
    int arr1[SIZE] = { 1, 2, 3, 11, 5 };
    int arr2[SIZE] = { 6, 7, 8, 9, 10 };
    int * ptr;
    
    if ( ( ptr = (int*)find_first_not_of(arr1, arr1 + SIZE, arr2, arr2 + SIZE, std::less<int>()) ) == arr1 + SIZE )
        std::cout << "all elements from arr1 less then elements from arr2" << std::endl;
    else 
        std::cout << "First element from arr1 that is bigger elements in arr2 is " << *ptr << std::endl;
    
    return 0;
}
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 05:20
Цитата Сообщение от Сыроежка Посмотреть сообщение
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
На это следует классический вопрос-ответ: Вам шашечки, или ехать?
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
02.08.2011, 05:36
Цитата Сообщение от Сыроежка Посмотреть сообщение
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
Классический ответ ptr_fun. Как прикрутить - сами догадайтесь...
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 06:34
В моей последней реализации, кстати, тоже должна бы быть bind1st, но из-за неправильного расположения интервалов пришлось заменить на bind2nd.
0
Заблокирован
02.08.2011, 23:23  [ТС]
Цитата Сообщение от grizlik78 Посмотреть сообщение
На это следует классический вопрос-ответ: Вам шашечки, или ехать?
Как и следовало ожидать, сказать в ответ вам нечего. То есть если есть какая-нибудь функция 'f', которую можно вызвать со стандартным алгоритмом std::find_first_of, например,

C++
1
std::find_first_of( first1, last1, first2, last2, &f );

то при попытке сделать тоже самое для алгоритма find_first_not_of, то есть при задании совершенно идентичного кода

C++
1
find_first_not_of( first1, last1, first2, last2, &f );
пользователь получит ошибку компиляции: алгоритм не работает.

Фактически, имеется лишь частная реализация алгоритма для функциональных объектов. Для работы с функциями придется писать дополнительную частную реализацию алгоритма.

Спасибо всем за участие в теме. Я убедился, что нельзя создать этот алгоритм на основе других стандартных алгоритмов, а значит это упущение стандарта, что этот алгоритм остался за его бортом.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 23:37
Цитата Сообщение от Сыроежка Посмотреть сообщение
Как и следовало ожидать, сказать в ответ вам нечего.
Было. Собственно это Вам уже и сказали, fun_ptr. Прямо так, как есть, мой последний код с fun_ptr не работает, но если заменить bind2nd на bind1st, как и должно быть на самом деле, то код вполне себе позволяет использовать функцию f. Не напрямую, конечно, через адаптер, но вопрос повторять не буду.

Цитата Сообщение от Сыроежка Посмотреть сообщение
а значит это упущение стандарта, что этот алгоритм остался за его бортом.
Настолько серьёзное, что надо срочно пересесть на другой язык. Где всё-всё-всё есть сразу из коробки.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
02.08.2011, 23:45
Цитата Сообщение от Сыроежка Посмотреть сообщение
Для работы с функциями придется писать дополнительную частную реализацию алгоритма.
Регистр флагов Вам в руки...

Цитата Сообщение от Сыроежка Посмотреть сообщение
Я убедился, что нельзя создать этот алгоритм на основе других стандартных алгоритмов, а значит это упущение стандарта, что этот алгоритм остался за его бортом.
Да на раз-два этот алгоритм реализуется. Я выдал Вам вполне рабочий вариант. По поводу передачи функций в качестве предиктатов (если оно действительно так необходимо, и по-другому просто никак) есть спец. средство - ptr_fun, пользуйтесь... Так ведь нет - Вам подавай, чтоб баксетбольные мячи с ананасами при помощи нивелира сравнивало. Ну так пожалуйста - grizlik78 Вам и такое сделал. Опять не так? Ну тогда последнее остаётся - писать ноты протеста тем, кто стандарт утверждает. Скорее всего таки добавят просто, чтобы отвязаться...
И кстати... Вот Вы сами-то как-нибудь это упущение в стандарте восполнить не пытались? А то уже 6 страниц темы, а от Вас пока кроме замечаний и претензий и не видно ничего...
0
Заблокирован
03.08.2011, 20:42  [ТС]
Цитата Сообщение от easybudda Посмотреть сообщение
Регистр флагов Вам в руки...

Вот Вы сами-то как-нибудь это упущение в стандарте восполнить не пытались? А то уже 6 страниц темы, а от Вас пока кроме замечаний и претензий и не видно ничего...
Такое впечатление, что вас кто-то обидел! Расслабьтесь. У меня к вам претензий нет. Я как раз и занимаюсь тем, что пытаюсь выявить упущения в стандарте. И это всего лишь одно из многочисленных упущений в библиотеки алгоритмов.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
03.08.2011, 21:19
Цитата Сообщение от Сыроежка Посмотреть сообщение
У меня к вам претензий нет.
И на том спасибо!
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я как раз и занимаюсь тем, что пытаюсь выявить упущения в стандарте.
Просто из любопытства: с какой целью?
Складывается впечатление, что зря мы тут что-то Вам придумывали, и решение вообще не нужно. Достаточно самого факта, что в STL такого нет. Ну так мир вообще не совершенен...
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
04.08.2011, 00:25
Сыроежка,
И это всего лишь одно из многочисленных упущений в библиотеки алгоритмов.
Для того и написаны boost и куча других либ... Ни в одном языке в стандарте нету всего. Всегда есть доп. либы.
0
Заблокирован
04.08.2011, 16:38  [ТС]
Цитата Сообщение от easybudda Посмотреть сообщение
И на том спасибо!

Просто из любопытства: с какой целью?
Складывается впечатление, что зря мы тут что-то Вам придумывали, и решение вообще не нужно. Достаточно самого факта, что в STL такого нет. Ну так мир вообще не совершенен...
Нет, не зря придумывали. Мне нужно было убедиться, что нет решений, которых я не знаю. То есть что я не заблуждаюсь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
04.08.2011, 16:38

Реализация наложений изображений, масок на другие изображения.
Всем привет:) Суть: изменение графики наложением изображений друг на друга; это можно сделать, отобразив полупрозрачный TImage поверх...

Реализация алгоритма
помогите пожалуйсто написать программу: 1. Реализовать алгоритм Insertion-Sort (сортировка вставками) и Merge-Sort (сортировка слиянием)...

Реализация алгоритма МТ
Прибавление единицы к двоичному числу 1q1-&gt;1q1R 0q1-&gt;0q1R Bq1-&gt;Bq2L 1q2-&gt;0q2L 0q2-&gt;1q3L Bq2-&gt;1STOP 0q3-&gt;0q3L ...

Реализация алгоритма
Смотрите, есть функция для рисования сегмента круга: pieslice(int x, int y, int start, int end, int radius) - int start и int ende угол...

Реализация алгоритма
Всем привет! Подскажите плиз,как можно реализовать алгоритм. Есть поле,которое может принемать любой размер,к примеру такое ...


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

Или воспользуйтесь поиском по форуму:
56
Ответ Создать тему
Новые блоги и статьи
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru