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

Поиск элемента в списке. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.61
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 00:48     Поиск элемента в списке. #1
Есть список, который содержит объекты класа type. Мне нужно найти в этом списке объект, который будет отвечать некоторым условиям. Пробую реализовать это с помощью рекурсии
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
{
    if ((*itr))
    {
        if <условие>
            return itr;
 
        if (itr != List.end())
        {
            ++itr;
            GetUnit(List, itr);
        }
    }
    return NULL;
}
Задача примерно такая - есть 10 объектов. Мне нужно достать 5 объектов, которые будут отвечать условиям. Причем после возвращения объект перестанет отвечать условию. Но не работает. Проблема в том, что ++itr не срабатывает. И получается вечная рекурсия. Как это исправить?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
08.10.2011, 00:57     Поиск элемента в списке. #2
Цитата Сообщение от ZaxarPal Посмотреть сообщение
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
Цитата Сообщение от ZaxarPal Посмотреть сообщение
return NULL;
'это явно не вяжется
rescr1pt
31 / 32 / 1
Регистрация: 03.10.2011
Сообщений: 61
08.10.2011, 00:59     Поиск элемента в списке. #3

Не по теме:

ZaxarPal, какие люди, в Голливуде.



Добавлено через 1 минуту
Цитата Сообщение от Jupiter Посмотреть сообщение
'это явно не вяжется
А то, смысл "Get"у возвращать NULL?
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 08:40  [ТС]     Поиск элемента в списке. #4
rescr1pt, привет
Jupiter, а если все объекты списка не подходят под условие? Тогда ловить краш?
Есть другой способ решить проблему с поиском в списке. Каждый раз проходить с начала списка форчиком и возвращать первый же найденный элемент. Но мне все же интересно, почему не срабатывает вариант с передачей в параметры функции списка и итератора. Ведь если, например, в списке будет миллиард элементов и найти нужно 5 миллионов проход с начала списка будет не самым удачным решением...

P.S. Почему всегда найдется человек, который вместо того, что бы помочь с решением конкретно заданного вопроса, начинает рассказывать что у примера нету смысла, оно не вяжется и вообще глупо? Вопрос ведь был задан как решить проблему с поиском, а не есть ли смысл в отрывке кода. Решили по умничать?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
08.10.2011, 12:28     Поиск элемента в списке. #5
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Jupiter, а если все объекты списка не подходят под условие? Тогда ловить краш?
возвращать end()

Цитата Сообщение от ZaxarPal Посмотреть сообщение
Почему всегда найдется человек, который вместо того, что бы помочь с решением конкретно заданного вопроса, начинает рассказывать что у примера нету смысла, оно не вяжется и вообще глупо? Вопрос ведь был задан как решить проблему с поиском, а не есть ли смысл в отрывке кода. Решили по умничать?
в вашем поиске не вижу условия поиска, чем помочь? я так понимаю вы пришили сюда за готовым кодом, так его не будет потому что
Цитата Сообщение от ZaxarPal Посмотреть сообщение
type GetUnit(std::list<type*> List, std::list<type*>::iterator itr)
{
if ((*itr))
{
if <условие>
return itr;
вы сами не знаете что вам надо
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 13:02  [ТС]     Поиск элемента в списке. #6
Jupiter, если бы не читали через строки, то все поняли бы. Я пришел не за готовым кодом, для этого я и не писал задачу. В первом посте я написал:
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Мне нужно найти в этом списке объект, который будет отвечать некоторым условиям.
Вот в
Цитата Сообщение от Jupiter Посмотреть сообщение
if <условие>
как раз и проверяется, отвечает ли объект условию.
Цитата Сообщение от Jupiter Посмотреть сообщение
возвращать end()
Лолчто? Который вернет последний элемент, который в свою очередь не отвечает условиям = равно краш.
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Проблема в том, что ++itr не срабатывает. И получается вечная рекурсия.
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Но мне все же интересно, почему не срабатывает вариант с передачей в параметры функции списка и итератора.
Был задан вопрос. Причем тут вообще готовый код? Кэп намекает, что если бы был нужен готовый код, то было бы лишь условие задачи, как в соседних темах...

P.S. А вы вообще читать умеете? Ибо начинают закрадываться сомнения.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.10.2011, 14:19     Поиск элемента в списке. #7
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Задача примерно такая - есть 10 объектов. Мне нужно достать 5 объектов, которые будут отвечать условиям
все уже написали за тебя: http://en.cppreference.com/w/cpp/container/list/remove, http://en.cppreference.com/w/cpp/algorithm/remove_copy
тред не читал
Цитата Сообщение от ZaxarPal Посмотреть сообщение
P.S. А вы вообще читать умеете? Ибо начинают закрадываться сомнения.
давай поспокойнее, а?
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 14:34  [ТС]     Поиск элемента в списке. #8
Цитата Сообщение от Nameless One Посмотреть сообщение
все уже написали за тебя
Какое отношение имеет метод remove и remove_if к данному вопросу? Метод remove_copy remove_copy_if тоже не очень подходит. За один раз мне нужно достать один элемент. Первый попавшийся, который удовлетворяет условиям. Объектов в списке может быть 10, может быть и 20. Так же не известно количество объектов, которые удовлетворяют условиям. Проблему с поиском элемента я решил. Мне интересно только почему в параметр функции передается один и тот же итератор, судя по всему.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.10.2011, 14:49     Поиск элемента в списке. #9
Цитата Сообщение от ZaxarPal Посмотреть сообщение
Лолчто? Который вернет последний элемент, который в свою очередь не отвечает условиям = равно краш
метод end(), несмотря на название, возвращает не последний элемент коллекции. И возвращать end() - вполне нормальное решение.

Цитата Сообщение от ZaxarPal Посмотреть сообщение
Какое отношение имеет метод remove и remove_if к данному вопросу?
прямое. С помощью метода remove_if ты можешь получить список, который содержит только те элементы, которые удовлетворяют условию.
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 15:11  [ТС]     Поиск элемента в списке. #10
Цитата Сообщение от Nameless One Посмотреть сообщение
метод end(), несмотря на название, возвращает не последний элемент коллекции. И возвращать end() - вполне нормальное решение.
А что тогда возвращает?
Цитата Сообщение от Nameless One Посмотреть сообщение
С помощью метода remove_if ты можешь получить список, который содержит только те элементы, которые удовлетворяют условию.
Метод ведь удалит элементы, которые не проходят по условию? Но этого делать нельзя.
Даже если и получить список этих элементов, разве это будет рациональное решение данного вопроса? А если элементов очень много. Причем первый элемент будет отвечать требованиям, а последний нет. В таком случае, если использовать методот remove_if, будут обработаны все элементы списка, вместо того, что бы проверить только первый. Или как тогда?
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.10.2011, 15:27     Поиск элемента в списке. #11
Цитата Сообщение от ZaxarPal Посмотреть сообщение
А что тогда возвращает?
http://cplusplus.com/reference/stl/list/end/. Возвращает итератор, указывающий на несуществующий элемент, "расположенный" за последним элементом списка
Цитата Сообщение от ZaxarPal Посмотреть сообщение
разве это будет рациональное решение данного вопроса? А если элементов очень много
у тебя при каждом вызове твоей функции происходит копирование всего списка, так что получится гораздо эффективнее.
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 15:33  [ТС]     Поиск элемента в списке. #12
Nameless One, а если в цикле проверять каждый элемент на выполнение условия и возвращать верный? Удалять элементы списка нельзя.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
08.10.2011, 15:42     Поиск элемента в списке. #13
Цитата Сообщение от ZaxarPal Посмотреть сообщение
а если в цикле проверять каждый элемент на выполнение условия и возвращать верный? Удалять элементы списка нельзя.
тоже можно

Вот пример класса, который возвращает очередной элемент последовательности, удовлетворяющий предикату, при каждом вызове оператора ():
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <functional>
#include <list>
 
template <class T, class Pred, class Cont = std::list<T> >
class filter
{
public:
 
    typedef typename Cont::iterator iterator;
    
    filter(iterator, iterator, Pred);
 
    iterator operator () ();
 
    iterator end();
        
private:
    iterator it;
    iterator last;
    Pred pred;
};
 
template <class T, class Pred, class Cont>
filter<T, Pred, Cont>::filter(iterator f, iterator l, Pred p)
    : it(f), last(l), pred(p)
{
}
 
template <class T, class Pred, class Cont>
typename filter<T, Pred, Cont>::iterator filter<T, Pred, Cont>::end()
{
    return last;
}
 
template <class T, class Pred, class Cont>
typename filter<T, Pred, Cont>::iterator filter<T, Pred, Cont>::operator () ()
{
    iterator result = it;
    
    if(it != last)
    {
    while((result = it) != last)
    {
        if(pred(*it))
        {
        ++it;
        break;
        }
        
        ++it;
    }
    }
 
    return result;
}
 
bool even(int i)
{
    return !(i & 1);
}
 
typedef bool (*PRED)(int);
 
int main()
{
    std::list<int> l = {1,2,3,4,5,6,7,8,9,10};
 
    filter<int, PRED> evens(l.begin(), l.end(), even);
 
    filter<int, PRED>::iterator it;
 
    while((it = evens()) != evens.end())
    std::cout << *it << std::endl;
    
    
    return 0;
}
Чтобы не указывать тип предиката при объявлении объекта-фильтра, можно сделать оператор шаблоном, принимающим предикат в качестве параметра
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
08.10.2011, 23:11     Поиск элемента в списке. #14
Задание интересно, единственное, что я не мог понять- что должна возвращать рекурсивная функция,
объект или указатель на объект, решил возвернуть объект

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <string>
#include <list>
using namespace std;
 
 
//Это вот будет описание типа
class type {
 public:
  type (int);
  ~type () {};
 
 int f () {return x;};
 
 private:
  int  x;
};
 
type::type (int nomer) {
 x= nomer;
};
 
 
//Это вот прототип функции
type GetUnit(list<type*> , list<type*>::iterator );
 
int main() {
 
 //Кропаем список из 10-ти указателей.
 type** p= new type* [10];
 
 
 //Теперь каждый указатель проинициализируем конкретным объектом типа type
 for (int i= 0; i< 10; i++) {
  p[i]= new type (i);
 }
 
 //собсно список
 list<type*> List (p, p + 10);
 
 list<type*>::iterator itr= List.begin();
 
 //Вызываем функцию, которая вернёт нам переменную типа type
 type rez= GetUnit (List, List.begin());
 
 
 printf ("%d\n", rez.f());
 
 getchar ();
 return 0;
}
 
 
type GetUnit(std::list<type*> List, list<type*>::iterator itr) {
 
    if (itr!=List.end()) {
     printf ("(**itr).f()%3= %d\n", (**itr).f()%3);
     //Так, а здесь проверяем условие. Я придумал условие такое:
     //член x обхекта при делении по модулю на 3 должен давать 2
     if (((**itr).f()%3)== 2)
      return **itr;
     else
      return GetUnit (List, ++itr);
    }
    return type (-1);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 23:43     Поиск элемента в списке.
Еще ссылки по теме:

C++ Удаление элемента в списке
C++ Ошибка в удалении элемента в списке
Поиск элемента в двусвязном списке C++

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

Или воспользуйтесь поиском по форуму:
ZaxarPal
1 / 1 / 0
Регистрация: 18.01.2011
Сообщений: 83
08.10.2011, 23:43  [ТС]     Поиск элемента в списке. #15
kravam, да, абсолютно верно поняли задачу Большое спасибо!
Yandex
Объявления
08.10.2011, 23:43     Поиск элемента в списке.
Ответ Создать тему
Опции темы

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