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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
Сыроежка
Заблокирован
31.07.2011, 18:44     Реализация алгоритма find_firdt_not_of через другие алгоритмы #1
Хотел создать эту тему в разделе С/С++ для экспертов, но мне было отказано в виду отсутствия неких прав. Поэтому формулирую тему здесь.

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2011, 18:44     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Посмотрите здесь:

Реализация алгоритма C++
C++ реализация алгоритма кодирования
Реализация алгоритма Йена на С++ C++
Алгоритмы поиска. Подскажите, в чем суть алгоритма? C++
Реализация алгоритма FOREL C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 18:53     Реализация алгоритма find_firdt_not_of через другие алгоритмы #2
Цитата Сообщение от Сыроежка Посмотреть сообщение
Хотел создать эту тему в разделе С/С++ для экспертов, но мне было отказано в виду отсутствия неких прав. Поэтому формулирую тему здесь.

Есть стандартный алгоритм std::find_first_of. Но нет стандартного алгоритма std::find_first_not_of. Надо предполагать, что авторы стандарта его не включили по тем соображениям, что его легко реализовать с помощью других алгоритмов.
Поэтому меня интересует, как реализовать данный алгоритм с помощью других алгоритмов? Есть какие-нибудь соображения? Или же на самом деле все сводится к тому, что надо писать собственную оригинальную реализацию этого алгоритма.
один из вариантов:

если коллекция пуста, возвращаем ::npos
ищем "первый один из"
если не нашли, или нашли, и оно непервое, то возвращаем первый элемент
если нашли, и он первый, то повторяем все для всей коллекции, исключая первый элемент.
Сыроежка
Заблокирован
31.07.2011, 18:56  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #3
Цитата Сообщение от novi4ok Посмотреть сообщение
один из вариантов:

если коллекция пуста, возвращаем ::npos
ищем "первый один из"
если не нашли, или нашли, и оно непервое, то возвращаем первый элемент
если нашли, и он первый, то повторяем все для всей коллекции, исключая первый элемент.
Я не понял, причем здесь npos?! Алгоритм find_first_not_of должен иметь точно такое же объявление, как и алгоритм find_first_of, И возвращать итератор найденного элемента коллекции или итератор конца интервала.
Вы наверное путаете с алгоритмами для класса std::string. Я же имею в виду стандартный алгоритм, а не алгоритмы какого-нибудь класса.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 18:58     Реализация алгоритма find_firdt_not_of через другие алгоритмы #4
ну не придирайся к мелочам несущественным, возвращай end(), если не нашел. я спутал с прямым углом, а вода кипит не при 90, а 100 градусах, ты был прав.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
31.07.2011, 19:01     Реализация алгоритма find_firdt_not_of через другие алгоритмы #5
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
#include <iostream>
#include <algorithm>
#include <functional>
#include <cctype>
#include <vector>
using namespace std;
 
bool comp_case_insensitive (char c1, char c2) {
  return (tolower(c1)==tolower(c2));
}
 
int main () {
  int mychars[] = {'a','b','c','A','B','C'};
  vector<char> myvector (mychars,mychars+6);
  vector<char>::iterator it;
 
  int match[] = {'A','B','C'};
 
  it = find_first_of (myvector.begin(), myvector.end(),
                      match, match+3, comp_case_insensitive);
 
  if (it!=myvector.end())
    cout << "first match is: " << *it << endl;
    
  it = find_first_of (myvector.begin(), myvector.end(),
                      match, match+3, not2(ptr_fun(comp_case_insensitive)) );
 
  if (it!=myvector.end())
    cout << "first match is: " << *it << endl;
  
  return 0;
}
Добавлено через 39 секунд
перефразируя пример с cplusplus.com
Сыроежка
Заблокирован
31.07.2011, 19:02  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #6
Цитата Сообщение от novi4ok Посмотреть сообщение
ну не придирайся к мелочам несущественным, возвращай end(), если не нашел. я спутал с прямым углом, а вода кипит не при 90, а 100 градусах, ты был прав.
Дело в том, что вы пытаетесь создать оригинальную реализацию алгоритма. Меня же интересует, можно ли как-нибудь исхитриться и получить данный алгоритм на основе существующих алгоритмов. То есть я хочу понять, почему этот алгоритм не включен в список стандартных алгоритмов. Одна из возможных причин, что его, якобы, легко реализовать через другие алгоритмы. Действительно это так или нет?
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 19:05     Реализация алгоритма find_firdt_not_of через другие алгоритмы #7
Цитата Сообщение от Сыроежка Посмотреть сообщение
Дело в том, что вы пытаетесь создать оригинальную реализацию алгоритма. Меня же интересует, можно ли как-нибудь исхитриться и получить данный алгоритм на основе существующих алгоритмов. То есть я хочу понять, почему этот алгоритм не включен в список стандартных алгоритмов. Одна из возможных причин, что его, якобы, легко реализовать через другие алгоритмы. Действительно это так или нет?
скажем так, я предлагаю создать оригинальную реализацию с использованием уже существующих ("первый один из").
Сыроежка
Заблокирован
31.07.2011, 19:11  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #8
alex_x_x

Если я не ошибаюсь, то ваш алгоритм не работает, так как он сравнивает элемент коллекции не со всеми элементами заданного набора. То есть если у вас первый элемент коллекции 'a', а заданный набор не совпадений равен "ABCa", то у вас уже при сравнении 'a' с 'A" ваш предикат вернет значение true, хотя на самом деле 'a' совпадает с 'a' из набора несовпадений.

Добавлено через 1 минуту
Цитата Сообщение от novi4ok Посмотреть сообщение
скажем так, я предлагаю создать оригинальную реализацию с использованием уже существующих ("первый один из").
Покажите, как это сделать? Уже приведенный один вариант, как мне представляется на глазок, является неверным.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 19:21     Реализация алгоритма find_firdt_not_of через другие алгоритмы #9
Цитата Сообщение от Сыроежка Посмотреть сообщение
alex_x_x

Если я не ошибаюсь, то ваш алгоритм не работает, так как он сравнивает элемент коллекции не со всеми элементами заданного набора. То есть если у вас первый элемент коллекции 'a', а заданный набор не совпадений равен "ABCa", то у вас уже при сравнении 'a' с 'A" ваш предикат вернет значение true, хотя на самом деле 'a' совпадает с 'a' из набора несовпадений.

Добавлено через 1 минуту


Покажите, как это сделать? Уже приведенный один вариант, как мне представляется на глазок, является неверным.
чтоб не голословить, нарисуй пример твоих данных. в чем ищем и что ищем.
Сыроежка
Заблокирован
31.07.2011, 19:43  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #10
Цитата Сообщение от novi4ok Посмотреть сообщение
чтоб не голословить, нарисуй пример твоих данных. в чем ищем и что ищем.
Я вам не только пример, но и прототип алгоритма напишу

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'.
LosAngeles
Заблокирован
31.07.2011, 19:49     Реализация алгоритма find_firdt_not_of через другие алгоритмы #11
без помощи других алгоритмов
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_not_of ( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2 )
{
    for ( ; first1 != last1; ++first1 )
        for (ForwardIterator2 it = first2; it != last2; ++it)
            if (*it != *first1) 
            {
                if (it == last2-1)
                    return first1;
            }
            else
                break;  
 
    return last1;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
31.07.2011, 19:50     Реализация алгоритма find_firdt_not_of через другие алгоритмы #12
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;
}
Сыроежка
Заблокирован
31.07.2011, 19:57  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #13
Цитата Сообщение от LosAngeles Посмотреть сообщение
без помощи других алгоритмов
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_not_of ( ForwardIterator1 first1, ForwardIterator1 last1,
                                    ForwardIterator2 first2, ForwardIterator2 last2 )
{
    for ( ; first1 != last1; ++first1 )
        for (ForwardIterator2 it = first2; it != last2; ++it)
            if (*it != *first1) 
            {
                if (it == last2-1)
                    return first1;
            }
            else
                break;  
 
    return last1;
}

Это конечно хорошо, что вы написали этот алгоритм. Правда он содержит серьезную ошибку, так как у у функции должны быть последовательные итераторы, а не итераторы произвольного доступа. То есть ваш код if (it == last2-1) не верен, так как операция вычитания для последовательного итератора не определена. Кроме того у вас есть и вторая ошибка: вы вместо оператора равенства используете оператор неравенства для сравнения разыменованных значений.

Но дело не в этом. Меня интересует: все же можно создать данный алгоритм через использование других алгоритмов, или же это серьезное упущение комитета по стандартизации, что он не включил этот алгоритм в набор стандартных алгоритмов.
LosAngeles
Заблокирован
31.07.2011, 20:03     Реализация алгоритма find_firdt_not_of через другие алгоритмы #14
Цитата Сообщение от Сыроежка Посмотреть сообщение
То есть ваш код if (it == last2-1) не верен, так как операция вычитания для последовательного итератора не определена
я проверял на веторе, думаю не надо показывать, что исправить чтобы работало для других контейнеров?
а насчёт второго я хз, но результат она выдаёт правильный
Сыроежка
Заблокирован
31.07.2011, 20:13  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #15
Цитата Сообщение от 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;
}
Вот это то, что надо! Правда вы включили лишнее определение дополнительного итератора 'i', который совершенно не требуется. То есть можно было написать проще

C++
1
2
    for ( ; start1 != stop1; ++start1 )
        if ( std::find(start2, stop2, *start1) == stop2 )
Но здесь есть один существенный нюанс. В исходной постановке задачи предполагается, что происходит сравнение

*start1 == *it2 ( где it2 - это некоторый итератор из диапазона [start2, stop2). В вашем же алгоритме происходит перестановка операндов сравнения, то есть вы сравниваете

*it2 == *start1

Дело в том, что если у меня, допустим, определен такой класс, как

C++
1
2
3
4
5
6
7
8
9
10
11
12
class Int
{
public:
   Int() : x( 0 ) {}
   explicit Int( int i ) : x( i ) {}
   bool operator ==( int i ) const
   {
      return ( x == i );
   }
private:
   int x;
};
то ваш алгоритм работать не будет!

То есть я имею в виду, что сравнение Int == int определено, а сравнение int == Int не определено.

Добавлено через 4 минуты
Цитата Сообщение от LosAngeles Посмотреть сообщение
я проверял на веторе, думаю не надо показывать, что исправить чтобы работало для других контейнеров?
а насчёт второго я хз, но результат она выдаёт правильный
Векторы, как и массивы, имеют итераторы произвольного доступа. Но если вы, например, имеете дело с односвязным списком, то код не будет компилироваться, так как у односвязных списков лишь последовательный итератор.
LosAngeles
Заблокирован
31.07.2011, 20:18     Реализация алгоритма find_firdt_not_of через другие алгоритмы #16
сделай == не членом класса, тогда вроде будет комутативность

Добавлено через 3 минуты
Цитата Сообщение от Сыроежка Посмотреть сообщение
Векторы, как и массивы, имеют итераторы произвольного доступа. Но если вы, например, имеете дело с односвязным списком, то код не будет компилироваться, так как у односвязных списков лишь последовательный итератор.
мне не надо повторять два раза, мне не надо повторять два раза... Я тебе ещё раз повторяю добавь две строки кода и всё будет в шоколаде в том примере
Сыроежка
Заблокирован
31.07.2011, 20:19  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #17
Цитата Сообщение от LosAngeles Посмотреть сообщение
сделай == не членом класса, тогда вроде будет комутативность
Так я специально не хочу этого делать! То есть я не хочу ограничивать множество типов объектов, для которых алгоритм работоспособен. Ситуация становится более понятной, если написать вариант этого алгоритма, который использует не оператор сравнения, а некоторый предикат. Для предикатов очевидно, что совсем не обязательно, что pred( a, b ) выдает тот же самы результат, что и предикат pred( b, a ).
LosAngeles
Заблокирован
31.07.2011, 20:24     Реализация алгоритма find_firdt_not_of через другие алгоритмы #18
Цитата Сообщение от Сыроежка Посмотреть сообщение
Так я специально не хочу этого делать! То есть я не хочу ограничивать множество типов объектов, для которых алгоритм работоспособен
как это множество ограничивается от того что == перестаёт быть членом класса?
Сыроежка
Заблокирован
31.07.2011, 20:27  [ТС]     Реализация алгоритма find_firdt_not_of через другие алгоритмы #19
Цитата Сообщение от LosAngeles Посмотреть сообщение
как это множество ограничивается от того что == перестаёт быть членом класса?
Может быть я не так вас понял. Вопрос же не в том, является оператор членорм класса или нет, а в том, позволяете ли вы коммутативность операции сравнения объектов разного типа : Int и int. Ежели вы просто сделаете оператор не членом класса, то ничего не изменится, так как конструктор имеет спецификатор explicit.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2011, 20:30     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
31.07.2011, 20:30     Реализация алгоритма find_firdt_not_of через другие алгоритмы #20
Цитата Сообщение от Сыроежка Посмотреть сообщение
Дело в том, что если у меня, допустим, определен такой класс
По-моему он у Вас не до конца доделан... А стандартные контейнеры/алгоритмы с ним работают? В общем случае если a = b, то b = a. Если это не так - "определённо не всё в порядке"(с)... Да и вариант с предиктатом написать никто не запрещает...
Yandex
Объявления
31.07.2011, 20:30     Реализация алгоритма find_firdt_not_of через другие алгоритмы
Ответ Создать тему
Опции темы

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