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

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

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

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

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

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

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
31.07.2011, 20:33  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #21
Цитата Сообщение от easybudda Посмотреть сообщение
По-моему он у Вас не до конца доделан... А стандартные контейнеры/алгоритмы с ним работают? В общем случае если a = b, то b = a. Если это не так - "определённо не всё в порядке"(с)... Да и вариант с предиктатом написать никто не запрещает...
Это верно, если a и b одного типа! А что делать, если у вас, как в моем примере, происходит сравнение разных типов. Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет. То есть нет коммутативности. И как я уже сказал, а что делать с предикатами?! Ведь для предикатов, которые задаются пользователями, совершенно не обязательно, что pred( a, b ) == pred( b, a )
Kastaneda
31.07.2011, 20:36
  #22

Не по теме:

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

grizlik78
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
31.07.2011, 20:36     Реализация алгоритма find_firdt_not_of через другие алгоритмы #23
Монстрик на основе кода easybudda. Конечно, проблема сохранилась и здесь, но функтор можно переписать через цикл и поставить v с нужной стороны (слева). Но согласен, что не всё в порядке в королевстве датском
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
#include <iostream>
#include <algorithm>
 
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)
    {
        return std::find(b, e, v) == e;
    }
};
 
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));
}
 
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;
}
diagon
31.07.2011, 20:37
  #24

Не по теме:

Цитата Сообщение от Kastaneda Посмотреть сообщение

Не по теме:

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

А что с ней работать, она интуитивно понятная =)
О алгоритмах такое сказать сложнее.

Kastaneda
31.07.2011, 20:40
  #25

Не по теме:

Цитата Сообщение от diagon Посмотреть сообщение
А что с ней работать, она интуитивно понятная =)
Просто когда доходишь до STL, то, как правило, подобные вещь уже должны "от зубов отскакивать"

grizlik78
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
31.07.2011, 20:41     Реализация алгоритма find_firdt_not_of через другие алгоритмы #26
А интересно, find_first_of даёт какие-либо гарантии по поводу того, что версия без предиката вызовет == с правильной расстановкой аргументов?
LosAngeles
Заблокирован
31.07.2011, 20:42     Реализация алгоритма find_firdt_not_of через другие алгоритмы #27
Цитата Сообщение от Сыроежка Посмотреть сообщение
Ежели вы просто сделаете оператор не членом класса, то ничего не изменится, так как конструктор имеет спецификатор explicit
тут всё просто - убери explicit, зачем он нужен в подобном классе? сам себе геморой создаёшь
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
31.07.2011, 20:46     Реализация алгоритма find_firdt_not_of через другие алгоритмы #28
Сыроежка, а не вариант в класс добавить
C++
1
bool operator == ( int a, const Int & b) { return a == b.x; }
grizlik78
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
31.07.2011, 20:51     Реализация алгоритма find_firdt_not_of через другие алгоритмы #29
easybudda, как друга?

Добавлено через 1 минуту
по-моему лучше вне класса объявить такую:
C++
1
2
inline
bool operator == ( int a, const Int & b) { return b == a; }
alex_x_x
бжни
2443 / 1648 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
31.07.2011, 20:52     Реализация алгоритма find_firdt_not_of через другие алгоритмы #30
Цитата Сообщение от grizlik78 Посмотреть сообщение
А интересно, find_first_of даёт какие-либо гарантии по поводу того, что версия без предиката вызовет == с правильной расстановкой аргументов?
Returns: The first iterator i in the range [first1, last1) such that for some integer j in the range
[first2, last2) the following conditions hold: *i == *j, pred(*i,*j) != false.
Returns last1 if no such iterator is found.
в стандарте все четко
Kastaneda
Форумчанин
Эксперт С++
4259 / 2791 / 219
Регистрация: 12.12.2009
Сообщений: 7,120
Записей в блоге: 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
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
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
550 / 503 / 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
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
31.07.2011, 22:06     Реализация алгоритма find_firdt_not_of через другие алгоритмы #34
Цитата Сообщение от Сыроежка Посмотреть сообщение
Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет.
Что-то я не понял, зачем тогда вообще так изгаляться? Должна быть функция-член класса, которая принимает фамилию и возвращает true/false в зависимости от наличия такого в базе, и функция-член класса, которая по переданной фамилии возвращает номер, или вызывает исключение... Ну и функция, которая по заданному номеру возвращает фамилию, или опять же исключение вызывает... Вы бы толком написали, что Вам нужно. Есть мнение, что просто не в ту сторону роете...
grizlik78
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
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
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
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
Эксперт С++
1897 / 1429 / 106
Регистрация: 29.05.2011
Сообщений: 2,985
02.08.2011, 03:50     Реализация алгоритма find_firdt_not_of через другие алгоритмы #39
Цитата Сообщение от Сыроежка Посмотреть сообщение
хотел бы заметить что этот недостаток легко исправит, заменив
Ну уж нет. У equal_to оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2011, 04:02     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
02.08.2011, 04:02     Реализация алгоритма find_firdt_not_of через другие алгоритмы #40
Цитата Сообщение от Сыроежка Посмотреть сообщение
Возвращаясь к вашему решению, к которому я уже сделал замечание
Это, конечно, хорошо, что есть, кому мне замечания делать. Проблема в другом. С алгоритмом всё в порядке и никакие костыли ему не нужны. Просто не пытайтесь круглое с красным сравнивать. Ещё раз говорю - проверьте логику своей программы - 99.9 % проще всё можно сделать.

Не по теме:

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

Yandex
Объявления
02.08.2011, 04:02     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Ответ Создать тему
Опции темы

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