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

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

31.07.2011, 18:44. Показов 6107. Ответов 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
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
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
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
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
12845 / 7594 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
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
Ответ Создать тему
Новые блоги и статьи
Программное добавление префикса в нумерацию документов
Maks 27.10.2026
Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .
После закрытия оутлука продолжает висеть процесс в диспетчере задач
Maks 27.10.2026
С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .
Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный
AmbA 26.10.2026
Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru