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

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

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

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

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

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

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 1
Завершенные тесты: 1
31.07.2011, 20:53     Реализация алгоритма find_firdt_not_of через другие алгоритмы #31
Может добавить operator int(){return x;} ?

Добавлено через 53 секунды
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Int
{
public:
   Int() : x( 0 ) {}
   explicit Int( int i ) : x( i ) {}
  /* bool operator ==( int i ) const
   {
      return ( x == i );
   }*/
   operator int(){return x;}
private:
   int x;
};
 
int main(){
    Int a(5);
    std::cout<<std::boolalpha<<(a==10)<<std::endl<<(5==a)<<std::endl;
}
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
31.07.2011, 21:14     Реализация алгоритма find_firdt_not_of через другие алгоритмы #32
alex_x_x, спасибо. Сегодня ломает в стандарт лезть

Добавлено через 20 минут
Функтор-предикат с сохранением порядка аргументов к предыдущему моему коду.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename ForwardIter>
class NotIn
{
    ForwardIter b;
    ForwardIter e;
public:
    NotIn(ForwardIter start, ForwardIter stop) :
        b(start), e(stop)
    {}
    template <typename T>
    bool operator() (T const& v) const
    {
        ForwardIter i = b;
        while (i != e)
            if (v == *i++)
                return false;
        return true;
    }
};
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 21:55     Реализация алгоритма find_firdt_not_of через другие алгоритмы #33
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я вам не только пример, но и прототип алгоритма напишу

C++
1
2
3
4
5
template <typename ForwardIterator1,
          typename ForwardIterator2>
 
ForwardIterator1 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2 );
Если, допустим, у вас есть массив

int a[] = { 1, 2, 3, 3, 1, 4, 2 };

и вектор

std::vector<int> v( a, a + 3 );

то вам нужно найти в массиве 'a' первый элемент, который не содержится в векторе 'v', точнее сказать, который не равен ни одному элементу вектора 'v'.
так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename ForwardIterator1, typename ForwardIterator2>
 
ForwardIterator1 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2 ){
    ForwardIterator1 it_first = first1;
    ForwardIterator1 it;
 
    while (true){
        if (it_first != last1){
            it = std::find_first_of (it_first, last1, first2, last2);//ищем "первый один из"
            if (it == last1 || it != it_first){//если не нашли, или нашли, и оно непервое, то возвращаем первый элемент
                return it_first;
            } else {//если нашли, и он первый, то повторяем все для всей коллекции, исключая первый элемент.
                it_first++;
            }
        } else {//если коллекция пуста, возвращаем ::npos
            return last1;
        }
    }
}
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
31.07.2011, 22:06     Реализация алгоритма find_firdt_not_of через другие алгоритмы #34
Цитата Сообщение от Сыроежка Посмотреть сообщение
Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет.
Что-то я не понял, зачем тогда вообще так изгаляться? Должна быть функция-член класса, которая принимает фамилию и возвращает true/false в зависимости от наличия такого в базе, и функция-член класса, которая по переданной фамилии возвращает номер, или вызывает исключение... Ну и функция, которая по заданному номеру возвращает фамилию, или опять же исключение вызывает... Вы бы толком написали, что Вам нужно. Есть мнение, что просто не в ту сторону роете...
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
31.07.2011, 22:42     Реализация алгоритма find_firdt_not_of через другие алгоритмы #35
Между прочим в C++0x есть алгоритм none_of, действие которого похоже на мой предикат NotIn

Добавлено через 20 минут
Ну и для полноты картины реализация через него.
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
template <typename T1>
class EqualTo
{
    T1 m_v;
public:
    EqualTo(T1 const& v) : m_v(v) {}
    template <typename T2>
    bool operator() (T2 const& v) const
        { return m_v == v; }
};
 
template <typename Iter>
class NotIn
{
    Iter b;
    Iter e;
public:
    NotIn(Iter start, Iter stop) :
        b(start), e(stop) {}
    template <typename T>
    bool operator() (T const& v) const
        { return std::none_of(b, e, EqualTo<T>(v)); }
};
 
template <typename ForwardIter1, typename ForwardIter2>
ForwardIter1 find_first_not_of(ForwardIter1 start1, ForwardIter1 stop1, ForwardIter2 start2, ForwardIter2 stop2){
        return std::find_if(start1, stop1, NotIn<ForwardIter2>(start2, stop2));
}
Сыроежка
Заблокирован
02.08.2011, 03:22  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #36
Цитата Сообщение от Kastaneda Посмотреть сообщение

Не по теме:

Мне вот просто интересно, как так получилось, что человек работает с STL, а свою реализацию простого алгоритма написать не может?

У меня к вам встречный вопрос: как так получилось, что вы, не способный понять простой постановки вопроса, считаете себя программистом?!
Спецмально для вас разъясняю: меня не интересует собственная реализация этого алгоритма. Меня интересует, можно ли этот алгоритм выразить через другие стандартные алгоритмы.

Вопрос стоит так:почему этот алгоритм не включен в стандартную библиотеку С++?! Какие на это были основания?!

Ведь этот алгоритм ни чем не проще и не сложнее других подобных алгоритмов. Почему для калсса std::basic_string он представлен как самостоятельный алгоритм, а для других контейнеров он отсуствует? Если предполагается, что его легко вывести из других алгоритмов, то почему для класса std::basic_string он написан отдельно, а не выведен из других алгоритмов?

Вы сами-то можете сказать достоверно, почему разработчики стандарта обошли стороной этот алгоритм?

Вы что-то там пытаетесь подправить мой класс Int, и до вас не доходит, а что делать, если условие поиска задано предикатом, как, например, std::less? Как в этом случае быть с перестановкой операндов для предиката?!

У меня была лишь одна идея, почему этот алгоритм не включили в стандартную библиотеку С++: его легко реализовать с помощью других алгоритмов. Но оказывается, это не так! То есть никаких веских причин, почему этот алгоритм отсуствует, я не вижу. С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
02.08.2011, 03:43     Реализация алгоритма find_firdt_not_of через другие алгоритмы #37
Цитата Сообщение от Сыроежка Посмотреть сообщение
С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
Алгоритм find, в отличие от find_first_not_of, требуется довольно часто. Видимо алгоритм find_first_not_of кроме как для строк некому особо нужен не был, а Сыроежка не являлся членом комиссии по стандартизации. Или есть сведения, что было предложение включить этот алгоритм в стандарт, но оно было отклонено? Стандартная библиотека не может объять необъятное.
Кстати, если верить Джосаттису, даже алгоритм find_first_of не входил в исходную версию STL, чего не скажешь про find.
Сыроежка
Заблокирован
02.08.2011, 03:46  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #38
Цитата Сообщение от 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
#include <iostream>
#include <algorithm>
 
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;
}
 
int main(void){
    const int SIZE = 5;
    int arr1[SIZE] = { 1, 2, 3, 6, 5 };
    int arr2[SIZE] = { 1, 2, 3, 4, 5 };
    int * ptr;
    
    if ( ( ptr = (int*)find_first_not_of(arr1, arr1 + SIZE, arr2, arr2 + SIZE) ) == 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;
}
Возвращаясь к вашему решению, к которому я уже сделал замечание, что в нем происходит перестановка операндов в операции сравнения при вызове алгоритма std::find, хотел бы заметить что этот недостаток легко исправит, заменив

C++
1
 std::find(start2, stop2, *i)
на

C++
1
std::find_if( start2, stop2, std::bind1st( std::equal_to<typename std::iterator_traits<ForwardIter2>::type_name>(), *i ) )
Но проблема возникает, когда надо написать версию этого алгоритма с предикатом, и, во-вторых, ваща реализация на самом деле не является реализацией на основе других алгоритмов, так как в ней присутствует явный цикл по итераторам.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
02.08.2011, 03:50     Реализация алгоритма find_firdt_not_of через другие алгоритмы #39
Цитата Сообщение от Сыроежка Посмотреть сообщение
хотел бы заметить что этот недостаток легко исправит, заменив
Ну уж нет. У equal_to оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
02.08.2011, 04:02     Реализация алгоритма find_firdt_not_of через другие алгоритмы #40
Цитата Сообщение от Сыроежка Посмотреть сообщение
Возвращаясь к вашему решению, к которому я уже сделал замечание
Это, конечно, хорошо, что есть, кому мне замечания делать. Проблема в другом. С алгоритмом всё в порядке и никакие костыли ему не нужны. Просто не пытайтесь круглое с красным сравнивать. Ещё раз говорю - проверьте логику своей программы - 99.9 % проще всё можно сделать.

Не по теме:

Цитата Сообщение от Сыроежка Посмотреть сообщение
почему этот алгоритм не включен в стандартную библиотеку С++?! Какие на это были основания?!
Следующий по логике вопрос - "Почему меня не спросили?"

Сыроежка
Заблокирован
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
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
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
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2011, 05:12     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Еще ссылки по теме:
Реализация Алгоритма Грэхема на С++ C++
C++ Реализация алгоритма DBSCAN
C++ Реализация волнового алгоритма
Реализация циклического алгоритма C++
C++ Реализация алгоритма Мандельброта

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
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;
}
Yandex
Объявления
02.08.2011, 05:12     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Ответ Создать тему
Опции темы

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