Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Qt Общие вопросы _ Непонятки с QMap

Автор: trdm 8.10.2009, 18:20

Непонятки с QMap....

struct uoCell
{
    uoCell():m_nomber(0){};
    int m_nomber;
};

int main(int argc, char *argv[])
{
    QApplication app(argc, argv);
    QDialog dlg;
    QMap<int,uoCell*> map;
    for (int i = 1; i<10; i++)
    {
        if (!map.contains(i)){
            uoCell* cell = new uoCell;
            cell->m_nomber = i;
            cout << "insert" << i;
            map.insert(i,cell);
        }
    }
    uoCell* cell2 = NULL;

    QMap<int,uoCell*>::iterator it = map.find(5);

    while(it != map.begin()){
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "find" << cell2->m_nomber;
        --it;
    }


    dlg.show();


    return app.exec();
}


Казалось бы
while(it != map.begin()){
гарантирует, что найдется пара с m_nomber == 1
Ан нет, нефига....

Автор: igor_bogomolov 8.10.2009, 18:41

Не понимаю вопроса.

Цитата(trdm @ 8.10.2009, 19:20) *
Казалось бы
while(it != map.begin()){
гарантирует, что найдётся пара с m_nomber == 1


В цикле for нулевой элемент map-а инициализируется единицей. Цикл while - это цикл с пред условием. Поэтому как только доходите до нулевого элемента, выходите из цикла while. Поэтому и сообщения вида find 1 вы не увидете.

Я правильно вопрос понимаю?

Автор: trdm 8.10.2009, 19:22

Думаю правильно, однако я привык, что с бегина по энд и с энда по бегин выведется все.
А тут нужны какие-то извраты.
Путем "тыка" нашел нужные мне "нормальные" проходные алгоритмы:

Раскрывающийся текст

    QMap<int,uoCell*> map;
    for (int i = 1; i<=10; i++)
    {
        if (!map.contains(i)){
            uoCell* cell = new uoCell;
            cell->m_nomber = i;
            cout << "\n insert: \t" << i;
            map.insert(i,cell);
        }
    }
    uoCell* cell2 = NULL;

    QMap<int,uoCell*>::iterator it;
    it = map.find(5);

    cout << "\n\n test1 5->1 \n";
    while(it != map.begin()){
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "\n find \t" << cell2->m_nomber << " key: " << it.key();
        --it;
    }

    cout << "\n\n test2 1->10 \n";
    it = map.begin();
    while(it != map.end()){
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "\n find \t" << cell2->m_nomber << " key: " << it.key();
        ++it;
    }

    cout << "\n\n test3 10-1 \n";

    it = map.end();
    do {
        --it;
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "\n find \t" << cell2->m_nomber << " key: " << it.key();

    }while(it != map.begin());


    cout << "\n\n test4 5->10 \n";

    it = map.find(5);
    while(it != map.end()){
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "\n find \t" << cell2->m_nomber << " key: " << it.key();
        ++it;
    }

    cout << "\n\n test5 5->1 \n";

    it = map.find(5);
    bool last = false;
    do {
        if (last)
            --it;
        last = true;
        cell2 = it.value();
        cell2->m_nomber += 0;
        cout << "\n find \t" << cell2->m_nomber << " key: " << it.key();

    }while(it != map.begin());



Вывод:
Раскрывающийся текст


insert: 1
insert: 2
insert: 3
insert: 4
insert: 5
insert: 6
insert: 7
insert: 8
insert: 9
insert: 10

test1 5->1

find 5 key: 5
find 4 key: 4
find 3 key: 3
find 2 key: 2

test2 1->10

find 1 key: 1
find 2 key: 2
find 3 key: 3
find 4 key: 4
find 5 key: 5
find 6 key: 6
find 7 key: 7
find 8 key: 8
find 9 key: 9
find 10 key: 10

test3 10-1

find 10 key: 10
find 9 key: 9
find 8 key: 8
find 7 key: 7
find 6 key: 6
find 5 key: 5
find 4 key: 4
find 3 key: 3
find 2 key: 2
find 1 key: 1

test4 5->10

find 5 key: 5
find 6 key: 6
find 7 key: 7
find 8 key: 8
find 9 key: 9
find 10 key: 10

test5 5->1

find 5 key: 5
find 4 key: 4
find 3 key: 3
find 2 key: 2
find 1 key: 1
Process returned 0 (0x0) execution time : 1.890 s
Press any key to continue.


Автор: rnd 8.10.2009, 19:58

Тут нет никаких извратов, просто не забывайте, что begin() - это указатель на первый элемент, а end() - на следующий за последним.
Так принято в stl и Qt тоже
Именно поэтому мы пишем

for(...it = cont.begin(); it != cont.end(); ++it)
{}

т.е. реально при последнем ++it мы уже выходим за границу контейнера, и итератор указывает за последний элемент.
Если представлять себе итераторы как указатели - то все еще понятнее.

Естественно, когда вы пишете
while(it != cont.begin())
{
...
--it;
}


Вы просто-напросто пропустите первый элемент.

Автор: trdm 8.10.2009, 20:45

Ок.
С QMap пока ПЛОТНО не работал. По этому и хм...
Но восновном меня интересовали сейчас направления с
- энд до бегина,
- c find to end;
- c find to begin;

Автор: Влад 8.10.2009, 21:50

В общем, все уже объяснили. В stl для этого есть reverse_iterator, rbegin() и rend(). К сожалению, в QMap они, насколько я понимаю, отсутствуют напрочь....

Автор: DIMEDROLL 8.10.2009, 22:19

Цитата(trdm @ 8.10.2009, 18:20) *
Непонятки с QMap....

При работе с мапом нужно понимать, что элементы находятся не в том порядке в котором их туда добавляют, так как внутренняя структура мапа - бинарное дерево(в стл по крайней мере)

Автор: SABROG 8.10.2009, 23:02

Итераторы для меня тема тёмная и чем больше пытаюсь вникнуть в них, тем больше меня тянет к index-based вариантам реализациям перебора.

Автор: trdm 8.10.2009, 23:23

Цитата(Влад @ 8.10.2009, 22:50) *
В общем, все уже объяснили. В stl для этого есть reverse_iterator, rbegin() и rend(). К сожалению, в QMap они, насколько я понимаю, отсутствуют напрочь....

угу, отсутствуют.

Автор: SABROG 8.10.2009, 23:52

Если только так:

void QMapIterator::toBack ()
bool QMapIterator::hasPrevious () const
Item QMapIterator::previous()

http://www.crossplatform.ru/node/272

Автор: Litkevich Yuriy 9.10.2009, 6:52

Qt предоставляет http://www.doc.crossplatform.ru/qt/4.5.0/containers.html#the-iterator-classes

Автор: rnd 9.10.2009, 10:11

Нужно помнить, что map (QMap) сортирует элементы по ключу, именно поэтому к ключу предъявляется требование less-then comparable(т.е. определена операция <).
Поэтому при обычном переборе он и будет отдавать элементы в порядке возрастания ключей. А как он устроен внутри - дело второе.
Если порядок элементов не важен (или для ключа недоступна операция <) - можно пользоваться QHash

to SABROG, все-таки итераторы гораздо более универсальны, чем индексы. Индексы - это по сути только последовательные контейнеры, которые предоставляют произвольный доступ (vector, deque, в Qt QList).
А вот когда существует не один вариант обхода контейнера - итераторы рулят, например дерево:
post_order_iterator - узел после детей
pre_order_iterator - узел перед детьми
breadth_first_iterator - все узлы по уровням и т.п.

Кстати, rbegin(), rend() - простейшие примеры нестандартного обхода

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)