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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
insideone
Модератор
Автор FAQ
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
24.05.2010, 00:52     Итератор и его контейнер #1
Должен ли итератор содержать в себе указатель на его контейнер? Ведь функции контейнера принимают итератор и работают с ним наверное думая что этот итератор указывает на данные именно этого объекта, но ведь может это не так? Ведь итератор может быть взят от другого контейнера. Как контролировать это... ввести указатель в итератор на его объект-контейнер или есть способы лучше?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2010, 00:52     Итератор и его контейнер
Посмотрите здесь:

C++ Итератор С++
итератор C++
Итератор ? C++
C++ необходимо в шаблонном классе, один из параметров которого контейнер, объявить итератор этого контейнера
C++ Как отсортирвоать контейнер, если его тип определяется по ходу выполнения программы? (динамическая идентификация типов)
Класс-контейнер? Что это такое и с чем его «едят»? C++
C++ STL. Создать объект-контейнер stack и заполнить его данными типа double
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
 Аватар для 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
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
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
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
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
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
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
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
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
 Аватар для insideone
3631 / 909 / 48
Регистрация: 10.01.2010
Сообщений: 2,448
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++
Итератор C++
C++ Контейнер map. Итератор не хочет принимать значение rbegin()
Итератор C++
C++ Как достать объект-контейнер, а не его элемент

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

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

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