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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
Сыроежка
Заблокирован
31.07.2011, 18:44     Реализация алгоритма find_firdt_not_of через другие алгоритмы #1
Хотел создать эту тему в разделе С/С++ для экспертов, но мне было отказано в виду отсутствия неких прав. Поэтому формулирую тему здесь.

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2011, 18:44     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Посмотрите здесь:

Реализация алгоритма C++
C++ реализация алгоритма кодирования
Реализация алгоритма Йена на С++ C++
Алгоритмы поиска. Подскажите, в чем суть алгоритма? C++
Реализация алгоритма FOREL C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
02.08.2011, 04:20  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #41
Цитата Сообщение от 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 оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
Да, вы правы. Я в данном случае имел в виду некоммутативные операции для одного типа. Тем более это демонстрирует то, что реализация алгоритма через другие стандартные алгоритмы совершенно не очевидна.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.08.2011, 04:27     Реализация алгоритма find_firdt_not_of через другие алгоритмы #42
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я в данном случае имел в виду некоммутативные операции для одного типа.
Ну если для разных типов некоммутативное сравнение ещё как-то можно с натяжкой понять/оправдать, то для однотипных некоммутативное сравнение на равенство и некоммутативный предикат эквивалентности — это практически преступление!

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

Не по теме:

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

Причем здесь логика "моей программы"? Вы попробуйте для этого алгоритма написать версию с предикатом. И как вы там будете переставлять операнды для предиката?!
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.08.2011, 05:00     Реализация алгоритма find_firdt_not_of через другие алгоритмы #44
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вы попробуйте для этого алгоритма написать версию с предикатом.
Да не вопрос!
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;
}
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.08.2011, 05:12     Реализация алгоритма find_firdt_not_of через другие алгоритмы #45
Без циклов и с некоммутативным предикатом
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;
}
Сыроежка
Заблокирован
02.08.2011, 05:15  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #46
Цитата Сообщение от 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;
}
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.08.2011, 05:20     Реализация алгоритма find_firdt_not_of через другие алгоритмы #47
Цитата Сообщение от Сыроежка Посмотреть сообщение
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
На это следует классический вопрос-ответ: Вам шашечки, или ехать?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.08.2011, 05:36     Реализация алгоритма find_firdt_not_of через другие алгоритмы #48
Цитата Сообщение от Сыроежка Посмотреть сообщение
На это следует классический вопрос: а что делать, если в качестве предиката передается указатель на функцию?!
Классический ответ ptr_fun. Как прикрутить - сами догадайтесь...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.08.2011, 06:34     Реализация алгоритма find_firdt_not_of через другие алгоритмы #49
В моей последней реализации, кстати, тоже должна бы быть bind1st, но из-за неправильного расположения интервалов пришлось заменить на bind2nd.
Сыроежка
Заблокирован
02.08.2011, 23:23  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #50
Цитата Сообщение от 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 );
пользователь получит ошибку компиляции: алгоритм не работает.

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

Спасибо всем за участие в теме. Я убедился, что нельзя создать этот алгоритм на основе других стандартных алгоритмов, а значит это упущение стандарта, что этот алгоритм остался за его бортом.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.08.2011, 23:37     Реализация алгоритма find_firdt_not_of через другие алгоритмы #51
Цитата Сообщение от Сыроежка Посмотреть сообщение
Как и следовало ожидать, сказать в ответ вам нечего.
Было. Собственно это Вам уже и сказали, fun_ptr. Прямо так, как есть, мой последний код с fun_ptr не работает, но если заменить bind2nd на bind1st, как и должно быть на самом деле, то код вполне себе позволяет использовать функцию f. Не напрямую, конечно, через адаптер, но вопрос повторять не буду.

Цитата Сообщение от Сыроежка Посмотреть сообщение
а значит это упущение стандарта, что этот алгоритм остался за его бортом.
Настолько серьёзное, что надо срочно пересесть на другой язык. Где всё-всё-всё есть сразу из коробки.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.08.2011, 23:45     Реализация алгоритма find_firdt_not_of через другие алгоритмы #52
Цитата Сообщение от Сыроежка Посмотреть сообщение
Для работы с функциями придется писать дополнительную частную реализацию алгоритма.
Регистр флагов Вам в руки...

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

Вот Вы сами-то как-нибудь это упущение в стандарте восполнить не пытались? А то уже 6 страниц темы, а от Вас пока кроме замечаний и претензий и не видно ничего...
Такое впечатление, что вас кто-то обидел! Расслабьтесь. У меня к вам претензий нет. Я как раз и занимаюсь тем, что пытаюсь выявить упущения в стандарте. И это всего лишь одно из многочисленных упущений в библиотеки алгоритмов.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
03.08.2011, 21:19     Реализация алгоритма find_firdt_not_of через другие алгоритмы #54
Цитата Сообщение от Сыроежка Посмотреть сообщение
У меня к вам претензий нет.
И на том спасибо!
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я как раз и занимаюсь тем, что пытаюсь выявить упущения в стандарте.
Просто из любопытства: с какой целью?
Складывается впечатление, что зря мы тут что-то Вам придумывали, и решение вообще не нужно. Достаточно самого факта, что в STL такого нет. Ну так мир вообще не совершенен...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
04.08.2011, 00:25     Реализация алгоритма find_firdt_not_of через другие алгоритмы #55
Сыроежка,
И это всего лишь одно из многочисленных упущений в библиотеки алгоритмов.
Для того и написаны boost и куча других либ... Ни в одном языке в стандарте нету всего. Всегда есть доп. либы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2011, 16:38     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Еще ссылки по теме:

C++ Реализация алгоритма
C++ Реализация алгоритма Дейкстры
C++ Циклические алгоритмы. Реализация рядов

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

Или воспользуйтесь поиском по форуму:
Сыроежка
Заблокирован
04.08.2011, 16:38  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #56
Цитата Сообщение от easybudda Посмотреть сообщение
И на том спасибо!

Просто из любопытства: с какой целью?
Складывается впечатление, что зря мы тут что-то Вам придумывали, и решение вообще не нужно. Достаточно самого факта, что в STL такого нет. Ну так мир вообще не совершенен...
Нет, не зря придумывали. Мне нужно было убедиться, что нет решений, которых я не знаю. То есть что я не заблуждаюсь.
Yandex
Объявления
04.08.2011, 16:38     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Ответ Создать тему
Опции темы

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