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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
#1

Итератор и его контейнер - C++

24.05.2010, 00:52. Просмотров 1757. Ответов 14
Метки нет (Все метки)

Должен ли итератор содержать в себе указатель на его контейнер? Ведь функции контейнера принимают итератор и работают с ним наверное думая что этот итератор указывает на данные именно этого объекта, но ведь может это не так? Ведь итератор может быть взят от другого контейнера. Как контролировать это... ввести указатель в итератор на его объект-контейнер или есть способы лучше?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2010, 00:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Итератор и его контейнер (C++):

Контейнер map. Итератор не хочет принимать значение rbegin() - C++
Почему этот кусок кода for(it=m.rbegin(),i=q;it!=m.rend();it--,i--) выбивает ошибку? Приmultimap<int,string> m; ...

В шаблонном классе, один из параметров которого контейнер, объявить итератор этого контейнера - C++
Собсно #include <windows.h> #include <iterator> #include <vector> using namespace std; template <class T, template...

Вектор и его итератор - C++
На сколько мне известно,векторы выполняют вставку и удаление в X позицию контейнера на которую указывает его итератор: т.е. метод вставки...

Реализовать двусвязный список (list), итератор (iterator) и константный итератор (сonst_iterator) для списка - C++
не могу понять что должно быть результатом. может подскажете примеры? пожалуйста. Задание: Реализовать двусвязный список (list),...

Как достать объект-контейнер, а не его элемент - C++
Добрый вечер всем. Возник вопрос. Я читал Страуструпа и на одной из его глав, есть упражнение по созданию класса-контейнера, в...

Класс-контейнер? Что это такое и с чем его «едят»? - C++
Вечер добрый, столкнулся со следующей проблемой, в общем, есть задание: Создать класс-контейнер, который является абстракцией текста и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 09:48 #2
При неправильном подходе итераторы так же опасны как и обычные указатели, например:

здесь стабильное подвисание
C++
1
2
3
    set<int> si;
    set<int>::iterator it = si.find(5);
    si.erase(it);
здесь acces violation
C++
1
2
3
    set<int> si;
    set<int>::iterator it;
    si.erase(it);
а этот кусочек за 10 секунд съел 1 ГБ памяти
C++
1
2
3
    list<int> l1;
    list<int> l2;
    list<int> l3(l1.begin(), l2.begin());
1
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
24.05.2010, 11:30 #3
STL проектировалась с упором на быстродействие, вся ответственность за правильность входных итераторов лежит на вызывающей стороне. Только некоторые функции бросают ексепшены при неверных данных, at, например.
1
SONNY
8 / 8 / 0
Регистрация: 30.05.2009
Сообщений: 47
24.05.2010, 12:34 #4
Паттерн проектирования итератор почитайте.Там все написано.
0
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 15:12  [ТС] #5
Собственно а ответ на мой вопрос? Или я так понял - нет?
Но и ещё вопрос. А как же быть когда допустим я в цикле прохожу по объектам массива (итератором) и мне нужно текущий элемент удалить. Но в этом случае итератор испортится, т.к. указатель на нод содержащийся в нем уже не существует, и следующий ++ вызовет ошибку. Как в этом случае делают?

Цитата Сообщение от Manjak Посмотреть сообщение
STL проектировалась с упором на быстродействие, вся ответственность за правильность входных итераторов лежит на вызывающей стороне
Ну собственно я пишу свой двусвязный список и итератор для него, но код stl очень трудно понять
0
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 15:24 #6
Цитата Сообщение от insideone Посмотреть сообщение
Как в этом случае делают?
например
C++
1
2
3
4
5
6
7
8
9
10
11
12
    tree<Item *>::iterator it = Items.begin();
    while (it != Items.end())
    {
        if (!(*it)->enabled)
        {
            it = Items.erase(it);
        }
        else
        {
            it++;
        }
    }

Цитата Сообщение от insideone Посмотреть сообщение
Собственно а ответ на мой вопрос?
на какой именно
1
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 15:39  [ТС] #7
Цитата Сообщение от SONNY Посмотреть сообщение
Паттерн проектирования итератор почитайте.Там все написано.
Где можно почитать наиболее подробно?

Цитата Сообщение от Roma_F Посмотреть сообщение
на какой именно
Лучше на все ) Про проверку указывает ли итератор на данные именно этого контейнера, хотя впрочем я так понял что нет

Цитата Сообщение от Roma_F Посмотреть сообщение
например
C++
1
2
3
4
5
6
7
8
9
10
11
12
        tree<Item *>::iterator it = Items.begin();
        while (it != Items.end())
        {
                if (!(*it)->enabled)
                {
                        it = Items.erase(it);
                }
                else
                {
                        it++;
                }
        }
Т.е. erase должен возвращать новый итератор который должен был бы идти после текущего? Кроме того не хотелось бы себя ограничивать циклом while)
Я кстати так и не понял принцип возвращения .end() конечного итератора, он же уже не указывает на данные в контейнере, но на что?
0
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 15:56 #8
Цитата Сообщение от insideone Посмотреть сообщение
Я кстати так и не понял принцип возвращения .end() конечного итератора, он же уже не указывает на данные в контейнере, но на что?
можно сделать скрытый (private) элемент, который будет возвращатся ф-цией end() и на который будут переходить итераторы с последнего элемента
0
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 16:17  [ТС] #9
Цитата Сообщение от Roma_F Посмотреть сообщение
можно сделать скрытый (private) элемент, который будет возвращатся ф-цией end() и на который будут переходить итераторы с последнего элемента
Так этот член будет содержаться в контейнере, а итератор то откуда его возьмет? И почему проверка iterator->Node == NULL не может являться проверкой окончания списка?
0
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 17:27 #10
Цитата Сообщение от insideone Посмотреть сообщение
Так этот член будет содержаться в контейнере, а итератор то откуда его возьмет?
так от туда же, откуда и информацию о следующем/предыдущем элементе,
то есть ...->_next = _it_end;

Цитата Сообщение от insideone Посмотреть сообщение
И почему проверка iterator->Node == NULL не может являться проверкой окончания списка?
в простом двухсвязном списке так обычно и делают, но в STL сделали по другому

Добавлено через 2 минуты
я сам не копасля во врутренностях STL
1
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 17:35  [ТС] #11
Цитата Сообщение от Roma_F Посмотреть сообщение
так от туда же, откуда и информацию о следующем/предыдущем элементе,
то есть ...->_next = _it_end;
Вот мой итератор
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
template <class datatype>
class iterator{
friend class List;
    Node* Current;
    Node* getNode()         {   return Current; };
public:
    iterator(Node* newCurrent = NULL):Current(newCurrent) {};
 
    iterator& operator ++()     {   if ( Current != NULL ) Current = Current->Next; return *this;   }
    iterator& operator --()     {   if ( Current != NULL ) Current = Current->Prev; return *this;   }
    iterator& operator ++(int)  {   if ( Current != NULL ) Current = Current->Next; return *this;   }
    iterator& operator --(int)  {   if ( Current != NULL ) Current = Current->Prev; return *this;   }
            
 
    bool ref_swap(iterator& other);
            
    datatype& operator * ();
    datatype* operator -> ();
    operator datatype&();
 
    // Итератор не указывает на данные если empty вернет true
    bool empty() {  return (Current == NULL || Current->Data == NULL);  };
    // Итератор содержит правильный нод если full вернет true
    bool full() { return Current != NULL; };
}; typedef iterator<datatype> it;
Нод:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    class Node{
    public:
        Node    *Prev, *Next;
        void* Data;
    
        Node(void* newData = NULL, Node* newPrev = NULL, Node* newNext = NULL)
            :Data(newData), Prev(newPrev), Next(newNext){};
 
        Node* set(Node* newPrev, Node* newNext){
            Prev = newPrev;
            Next = newNext;
        return this;
        }
    };
Или нод ещё должен указывать на начало списка?
0
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 17:55 #12
Цитата Сообщение от insideone Посмотреть сообщение
Или нод ещё должен указывать на начало списка?
зачем

Добавлено через 2 минуты
а почему void* Data;
может Node тоже сделать шаблоном
0
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 18:00  [ТС] #13
Цитата Сообщение от Roma_F Посмотреть сообщение
зачем
запутался немного, ну ведь из итератора нельзя получить значение конца списка, т.к. конец списка находится в объекте списка. можно лишь если в итератор поместить указатель на контейнер, и из него уже можно все получить...

Цитата Сообщение от Roma_F Посмотреть сообщение
а почему void* Data;
может Node тоже сделать шаблоном
Ну как раз и сделал чтобы избавиться от шаблона, а зачем делать шаблоном?...
0
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 18:05 #14
ну.. для универсальности

может это пригодится: Реализация кольцевого двухсвязного списка

и ещё прикрепил файл с реализацией STL-подобного дерева, может там проще будет разобраться
1
Вложения
Тип файла: rar tree.rar (10.6 Кб, 17 просмотров)
insideone
Модератор
Автор FAQ
3639 / 918 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 18:24  [ТС] #15
Цитата Сообщение от Roma_F Посмотреть сообщение
ну.. для универсальности
Так она есть, конкретные данные уточняет сам итератор - ведь он является шаблоном) К тому же я храню не данные а указатель void* на них, это сделано для того чтобы 2 нода могли обменяться указателями и тем самым можно было быстро сделать перестановку в списке, что важно, т.к. списки будут хранить большие объекты
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2010, 18:24
Привет! Вот еще темы с ответами:

STL. Создать объект-контейнер stack и заполнить его данными типа double - C++
Задание: 1. Создать объект-контейнер и заполнить его данными, тип которых определяется вариантом задания. 2. Посмотреть контейнер. 3....

Как отсортирвоать контейнер, если его тип определяется по ходу выполнения программы? (динамическая идентификация типов) - C++
собсно #include &lt;windows.h&gt; #include &lt;stdio.h&gt; #include &lt;vector&gt; #include &lt;list&gt; #include &lt;algorithm&gt; #include &lt;cxxabi.h&gt; ...

Итератор - C++
Вот задача: Реализовать шаблон упорядоченного массива как двусвязного списка. Операцию доступа по индексу заменить итератором. Вопрос:...

итератор - C++
Привет всем! подскажите пожалуйста литературу где подробно описана реализация итераторов ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.05.2010, 18:24
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru