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

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

31.07.2011, 18:44. Показов 4445. Ответов 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
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 18:53 2
Цитата Сообщение от Сыроежка Посмотреть сообщение
Хотел создать эту тему в разделе С/С++ для экспертов, но мне было отказано в виду отсутствия неких прав. Поэтому формулирую тему здесь.

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

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

если коллекция пуста, возвращаем ::npos
ищем "первый один из"
если не нашли, или нашли, и оно непервое, то возвращаем первый элемент
если нашли, и он первый, то повторяем все для всей коллекции, исключая первый элемент.
Я не понял, причем здесь npos?! Алгоритм find_first_not_of должен иметь точно такое же объявление, как и алгоритм find_first_of, И возвращать итератор найденного элемента коллекции или итератор конца интервала.
Вы наверное путаете с алгоритмами для класса std::string. Я же имею в виду стандартный алгоритм, а не алгоритмы какого-нибудь класса.
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 18:58 4
ну не придирайся к мелочам несущественным, возвращай end(), если не нашел. я спутал с прямым углом, а вода кипит не при 90, а 100 градусах, ты был прав.
0
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
31.07.2011, 19:01 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
0
Заблокирован
31.07.2011, 19:02  [ТС] 6
Цитата Сообщение от novi4ok Посмотреть сообщение
ну не придирайся к мелочам несущественным, возвращай end(), если не нашел. я спутал с прямым углом, а вода кипит не при 90, а 100 градусах, ты был прав.
Дело в том, что вы пытаетесь создать оригинальную реализацию алгоритма. Меня же интересует, можно ли как-нибудь исхитриться и получить данный алгоритм на основе существующих алгоритмов. То есть я хочу понять, почему этот алгоритм не включен в список стандартных алгоритмов. Одна из возможных причин, что его, якобы, легко реализовать через другие алгоритмы. Действительно это так или нет?
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
31.07.2011, 19:05 7
Цитата Сообщение от Сыроежка Посмотреть сообщение
Дело в том, что вы пытаетесь создать оригинальную реализацию алгоритма. Меня же интересует, можно ли как-нибудь исхитриться и получить данный алгоритм на основе существующих алгоритмов. То есть я хочу понять, почему этот алгоритм не включен в список стандартных алгоритмов. Одна из возможных причин, что его, якобы, легко реализовать через другие алгоритмы. Действительно это так или нет?
скажем так, я предлагаю создать оригинальную реализацию с использованием уже существующих ("первый один из").
0
Заблокирован
31.07.2011, 19:11  [ТС] 8
alex_x_x

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

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

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

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


Покажите, как это сделать? Уже приведенный один вариант, как мне представляется на глазок, является неверным.
чтоб не голословить, нарисуй пример твоих данных. в чем ищем и что ищем.
0
Заблокирован
31.07.2011, 19:43  [ТС] 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'.
0
Заблокирован
31.07.2011, 19:49 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;
}
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
31.07.2011, 19:50 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;
}
0
Заблокирован
31.07.2011, 19:57  [ТС] 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) не верен, так как операция вычитания для последовательного итератора не определена. Кроме того у вас есть и вторая ошибка: вы вместо оператора равенства используете оператор неравенства для сравнения разыменованных значений.

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

Добавлено через 3 минуты
Цитата Сообщение от Сыроежка Посмотреть сообщение
Векторы, как и массивы, имеют итераторы произвольного доступа. Но если вы, например, имеете дело с односвязным списком, то код не будет компилироваться, так как у односвязных списков лишь последовательный итератор.
мне не надо повторять два раза, мне не надо повторять два раза... Я тебе ещё раз повторяю добавь две строки кода и всё будет в шоколаде в том примере
0
Заблокирован
31.07.2011, 20:19  [ТС] 17
Цитата Сообщение от LosAngeles Посмотреть сообщение
сделай == не членом класса, тогда вроде будет комутативность
Так я специально не хочу этого делать! То есть я не хочу ограничивать множество типов объектов, для которых алгоритм работоспособен. Ситуация становится более понятной, если написать вариант этого алгоритма, который использует не оператор сравнения, а некоторый предикат. Для предикатов очевидно, что совсем не обязательно, что pred( a, b ) выдает тот же самы результат, что и предикат pred( b, a ).
0
Заблокирован
31.07.2011, 20:24 18
Цитата Сообщение от Сыроежка Посмотреть сообщение
Так я специально не хочу этого делать! То есть я не хочу ограничивать множество типов объектов, для которых алгоритм работоспособен
как это множество ограничивается от того что == перестаёт быть членом класса?
0
Заблокирован
31.07.2011, 20:27  [ТС] 19
Цитата Сообщение от LosAngeles Посмотреть сообщение
как это множество ограничивается от того что == перестаёт быть членом класса?
Может быть я не так вас понял. Вопрос же не в том, является оператор членорм класса или нет, а в том, позволяете ли вы коммутативность операции сравнения объектов разного типа : Int и int. Ежели вы просто сделаете оператор не членом класса, то ничего не изменится, так как конструктор имеет спецификатор explicit.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
31.07.2011, 20:30 20
Цитата Сообщение от Сыроежка Посмотреть сообщение
Дело в том, что если у меня, допустим, определен такой класс
По-моему он у Вас не до конца доделан... А стандартные контейнеры/алгоритмы с ним работают? В общем случае если a = b, то b = a. Если это не так - "определённо не всё в порядке"(с)... Да и вариант с предиктатом написать никто не запрещает...
0
31.07.2011, 20:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.07.2011, 20:30
Помогаю со студенческими работами здесь

Реализация алгоритма
помогите пожалуйсто написать программу: 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,...

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


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

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