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

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

31.07.2011, 18:44. Показов 5782. Ответов 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
Заблокирован
31.07.2011, 20:33  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от easybudda Посмотреть сообщение
По-моему он у Вас не до конца доделан... А стандартные контейнеры/алгоритмы с ним работают? В общем случае если a = b, то b = a. Если это не так - "определённо не всё в порядке"(с)... Да и вариант с предиктатом написать никто не запрещает...
Это верно, если a и b одного типа! А что делать, если у вас, как в моем примере, происходит сравнение разных типов. Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет. То есть нет коммутативности. И как я уже сказал, а что делать с предикатами?! Ведь для предикатов, которые задаются пользователями, совершенно не обязательно, что pred( a, b ) == pred( b, a )
0
31.07.2011, 20:36

Не по теме:

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

0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 20:36
Монстрик на основе кода 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
31.07.2011, 20:37

Не по теме:

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

Не по теме:

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

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

0
31.07.2011, 20:40

Не по теме:

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

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

Добавлено через 1 минуту
по-моему лучше вне класса объявить такую:
C++
1
2
inline
bool operator == ( int a, const Int & b) { return b == a; }
0
бжни
 Аватар для alex_x_x
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
31.07.2011, 20:52
Цитата Сообщение от 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
 Аватар для Kastaneda
5232 / 3206 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
31.07.2011, 20:53
Может добавить 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
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 21:14
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
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я вам не только пример, но и прототип алгоритма напишу

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Эксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,980
31.07.2011, 22:06
Цитата Сообщение от Сыроежка Посмотреть сообщение
Например, у вас есть база данных сотрудников, и ваш класс позволяет лишь отвечать на вопрос: данный сотрудник имеет заданный номенклатурный номер или нет.
Что-то я не понял, зачем тогда вообще так изгаляться? Должна быть функция-член класса, которая принимает фамилию и возвращает true/false в зависимости от наличия такого в базе, и функция-член класса, которая по переданной фамилии возвращает номер, или вызывает исключение... Ну и функция, которая по заданному номеру возвращает фамилию, или опять же исключение вызывает... Вы бы толком написали, что Вам нужно. Есть мнение, что просто не в ту сторону роете...
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 22:42
Между прочим в 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  [ТС]
Цитата Сообщение от Kastaneda Посмотреть сообщение

Не по теме:

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

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

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

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

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

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

У меня была лишь одна идея, почему этот алгоритм не включили в стандартную библиотеку С++: его легко реализовать с помощью других алгоритмов. Но оказывается, это не так! То есть никаких веских причин, почему этот алгоритм отсуствует, я не вижу. С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 03:43
Цитата Сообщение от Сыроежка Посмотреть сообщение
С таким же успехом можно было бы исключить и другие алгоритмы поиска, как, например, алгоритм std::find, потому что он нисколько не сложнее данного алгоритма.
Алгоритм find, в отличие от find_first_not_of, требуется довольно часто. Видимо алгоритм find_first_not_of кроме как для строк некому особо нужен не был, а Сыроежка не являлся членом комиссии по стандартизации. Или есть сведения, что было предложение включить этот алгоритм в стандарт, но оно было отклонено? Стандартная библиотека не может объять необъятное.
Кстати, если верить Джосаттису, даже алгоритм find_first_of не входил в исходную версию STL, чего не скажешь про find.
0
Заблокирован
02.08.2011, 03: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
#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
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
02.08.2011, 03:50
Цитата Сообщение от Сыроежка Посмотреть сообщение
хотел бы заметить что этот недостаток легко исправит, заменив
Ну уж нет. У equal_to оба параметра имеют одинаковый тип. А кто-то тут говорил о сравнении вообще разнотипных объектов.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,980
02.08.2011, 04:02
Цитата Сообщение от Сыроежка Посмотреть сообщение
Возвращаясь к вашему решению, к которому я уже сделал замечание
Это, конечно, хорошо, что есть, кому мне замечания делать. Проблема в другом. С алгоритмом всё в порядке и никакие костыли ему не нужны. Просто не пытайтесь круглое с красным сравнивать. Ещё раз говорю - проверьте логику своей программы - 99.9 % проще всё можно сделать.

Не по теме:

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
02.08.2011, 04:02

Реализация наложений изображений, масок на другие изображения.
Всем привет:) Суть: изменение графики наложением изображений друг на друга; это можно сделать, отобразив полупрозрачный 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 угол...

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие.
kumehtar 24.07.2026
Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .
сукцессия 41
anaschu 24.07.2026
Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS | Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1.
anaschu 24.07.2026
Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем **Полевые заметки о двухнедельной совместной работе**. . .
Теория всего 12. ВГК на планете в стратегической игре "терра"
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики 1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru