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

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

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

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

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

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

Контейнер 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 позицию контейнера на которую указывает его итератор: т.е. метод вставки...

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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());
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
24.05.2010, 11:30     Итератор и его контейнер #3
STL проектировалась с упором на быстродействие, вся ответственность за правильность входных итераторов лежит на вызывающей стороне. Только некоторые функции бросают ексепшены при неверных данных, at, например.
SONNY
8 / 8 / 0
Регистрация: 30.05.2009
Сообщений: 47
24.05.2010, 12:34     Итератор и его контейнер #4
Паттерн проектирования итератор почитайте.Там все написано.
insideone
Модератор
Автор FAQ
3638 / 916 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 15:12  [ТС]     Итератор и его контейнер #5
Собственно а ответ на мой вопрос? Или я так понял - нет?
Но и ещё вопрос. А как же быть когда допустим я в цикле прохожу по объектам массива (итератором) и мне нужно текущий элемент удалить. Но в этом случае итератор испортится, т.к. указатель на нод содержащийся в нем уже не существует, и следующий ++ вызовет ошибку. Как в этом случае делают?

Цитата Сообщение от Manjak Посмотреть сообщение
STL проектировалась с упором на быстродействие, вся ответственность за правильность входных итераторов лежит на вызывающей стороне
Ну собственно я пишу свой двусвязный список и итератор для него, но код stl очень трудно понять
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 Посмотреть сообщение
Собственно а ответ на мой вопрос?
на какой именно
insideone
Модератор
Автор FAQ
3638 / 916 / 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() конечного итератора, он же уже не указывает на данные в контейнере, но на что?
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 15:56     Итератор и его контейнер #8
Цитата Сообщение от insideone Посмотреть сообщение
Я кстати так и не понял принцип возвращения .end() конечного итератора, он же уже не указывает на данные в контейнере, но на что?
можно сделать скрытый (private) элемент, который будет возвращатся ф-цией end() и на который будут переходить итераторы с последнего элемента
insideone
Модератор
Автор FAQ
3638 / 916 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 16:17  [ТС]     Итератор и его контейнер #9
Цитата Сообщение от Roma_F Посмотреть сообщение
можно сделать скрытый (private) элемент, который будет возвращатся ф-цией end() и на который будут переходить итераторы с последнего элемента
Так этот член будет содержаться в контейнере, а итератор то откуда его возьмет? И почему проверка iterator->Node == NULL не может являться проверкой окончания списка?
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
insideone
Модератор
Автор FAQ
3638 / 916 / 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;
        }
    };
Или нод ещё должен указывать на начало списка?
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
24.05.2010, 17:55     Итератор и его контейнер #12
Цитата Сообщение от insideone Посмотреть сообщение
Или нод ещё должен указывать на начало списка?
зачем

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

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

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

и ещё прикрепил файл с реализацией STL-подобного дерева, может там проще будет разобраться
Вложения
Тип файла: rar tree.rar (10.6 Кб, 17 просмотров)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2010, 18:24     Итератор и его контейнер
Еще ссылки по теме:

Итератор - C++
#include &lt;iostream&gt; #include &lt;list&gt; using namespace std; list&lt;int&gt;::iterator pos (list&lt;int&gt; a,list&lt;int&gt;::iterator it) { for (it;...

Итератор ? - C++
Как выглядит итератор на вложеный контейнер? Например осуществить доступ к 1-му символу 3-го элемента в векторе vector&lt; &lt;vecrot&lt;char&gt; &gt;...

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

итератор - C++
скажите как в этой задачи перевести десятичное число в двоичное??? вот условие задачи!!! вот код!! main.h #include &lt;cstdlib&gt; ...

Итератор - C++
Добрый день. Я начинающий. Есть проект пытаюсь сделать построение-отладку выдает ошибку типа: Ошибка 1 error C2061: синтаксическая...


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

Или воспользуйтесь поиском по форуму:
insideone
Модератор
Автор FAQ
3638 / 916 / 49
Регистрация: 10.01.2010
Сообщений: 2,469
24.05.2010, 18:24  [ТС]     Итератор и его контейнер #15
Цитата Сообщение от Roma_F Посмотреть сообщение
ну.. для универсальности
Так она есть, конкретные данные уточняет сам итератор - ведь он является шаблоном) К тому же я храню не данные а указатель void* на них, это сделано для того чтобы 2 нода могли обменяться указателями и тем самым можно было быстро сделать перестановку в списке, что важно, т.к. списки будут хранить большие объекты
Yandex
Объявления
24.05.2010, 18:24     Итератор и его контейнер
Ответ Создать тему
Опции темы

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