Заблокирован
1

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

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

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

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.07.2011, 18:44
Ответы с готовыми решениями:

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

Для одномерного массива составить блок схему алгоритма - Алгоритмы
Доброго времени суток, прошу помощи в составлении алгоритма.. Задан одномерный массив {xi}...

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

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

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

Не по теме:

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

0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
31.07.2011, 20:36 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;
}
0
diagon
31.07.2011, 20:37
  #24

Не по теме:

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

Не по теме:

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

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

0
Kastaneda
31.07.2011, 20:40
  #25

Не по теме:

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

0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
31.07.2011, 20:41 26
А интересно, find_first_of даёт какие-либо гарантии по поводу того, что версия без предиката вызовет == с правильной расстановкой аргументов?
0
Заблокирован
31.07.2011, 20:42 27
Цитата Сообщение от Сыроежка Посмотреть сообщение
Ежели вы просто сделаете оператор не членом класса, то ничего не изменится, так как конструктор имеет спецификатор explicit
тут всё просто - убери explicit, зачем он нужен в подобном классе? сам себе геморой создаёшь
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,755
31.07.2011, 20:46 28
Сыроежка, а не вариант в класс добавить
C++
1
bool operator == ( int a, const Int & b) { return a == b.x; }
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
31.07.2011, 20:51 29
easybudda, как друга?

Добавлено через 1 минуту
по-моему лучше вне класса объявить такую:
C++
1
2
inline
bool operator == ( int a, const Int & b) { return b == a; }
0
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
31.07.2011, 20:52 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.
в стандарте все четко
1
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,113
Записей в блоге: 2
31.07.2011, 20:53 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;
}
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
31.07.2011, 21:14 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;
    }
};
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 21:55 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;
        }
    }
}
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,755
31.07.2011, 22:06 34
Цитата Сообщение от Сыроежка Посмотреть сообщение
Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет.
Что-то я не понял, зачем тогда вообще так изгаляться? Должна быть функция-член класса, которая принимает фамилию и возвращает true/false в зависимости от наличия такого в базе, и функция-член класса, которая по переданной фамилии возвращает номер, или вызывает исключение... Ну и функция, которая по заданному номеру возвращает фамилию, или опять же исключение вызывает... Вы бы толком написали, что Вам нужно. Есть мнение, что просто не в ту сторону роете...
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
31.07.2011, 22:42 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));
}
0
Заблокирован
02.08.2011, 03:22  [ТС] 36
Цитата Сообщение от Kastaneda Посмотреть сообщение

Не по теме:

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

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

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

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

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

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

У меня была лишь одна идея, почему этот алгоритм не включили в стандартную библиотеку С++: его легко реализовать с помощью других алгоритмов. Но оказывается, это не так! То есть никаких веских причин, почему этот алгоритм отсуствует, я не вижу. С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
02.08.2011, 03:43 37
Цитата Сообщение от Сыроежка Посмотреть сообщение
С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
Алгоритм find, в отличие от find_first_not_of, требуется довольно часто. Видимо алгоритм find_first_not_of кроме как для строк некому особо нужен не был, а Сыроежка не являлся членом комиссии по стандартизации. Или есть сведения, что было предложение включить этот алгоритм в стандарт, но оно было отклонено? Стандартная библиотека не может объять необъятное.
Кстати, если верить Джосаттису, даже алгоритм find_first_of не входил в исходную версию STL, чего не скажешь про find.
0
Заблокирован
02.08.2011, 03:46  [ТС] 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 ) )
Но проблема возникает, когда надо написать версию этого алгоритма с предикатом, и, во-вторых, ваща реализация на самом деле не является реализацией на основе других алгоритмов, так как в ней присутствует явный цикл по итераторам.
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
02.08.2011, 03:50 39
Цитата Сообщение от Сыроежка Посмотреть сообщение
хотел бы заметить что этот недостаток легко исправит, заменив
Ну уж нет. У equal_to оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,755
02.08.2011, 04:02 40
Цитата Сообщение от Сыроежка Посмотреть сообщение
Возвращаясь к вашему решению, к которому я уже сделал замечание
Это, конечно, хорошо, что есть, кому мне замечания делать. Проблема в другом. С алгоритмом всё в порядке и никакие костыли ему не нужны. Просто не пытайтесь круглое с красным сравнивать. Ещё раз говорю - проверьте логику своей программы - 99.9 % проще всё можно сделать.

Не по теме:

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

0
02.08.2011, 04:02
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.08.2011, 04:02
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru