Путаница в концепции итератора на карте в c++

Предположим, у меня есть карта с именем m и итератор i для карты. В настоящее время я визуализирую итератор карты как индекс массива и хочу реализовать код, подобный приведенному ниже:

for(auto i = m.begin(); i != m.end(); i++)  { 
  auto l = i - 1;  // error type 1
  auto r = i + 1;  // error type 1
  while(l >= m.begin() && r < m.end()) { // error type 2
    // ...
    r++;
    l--;
  }
}

Теперь у меня есть несколько вопросов, которые меня немного сбивают с толку.

Для типа ошибки 1, указанного в коде, увеличение или уменьшение значения итератора дает ошибку, но аналогичная операция, выполняемая в цикле (я имею в виду i++), не дает ошибки.

Для типа ошибки 2, почему прямое сравнение двух итераторов (l >= m.begin()) дает ошибку, но выполнение аналогичной операции в цикле не приводит к ошибке?

И, наконец, как я могу заставить этот код работать над тем, как работает индекс массива, используя эту карту? Надеюсь, вы понимаете, что я пытаюсь реализовать.

Возможный дубликат Вычитание итераторов карты

halfelf 11.04.2018 11:46

Итератор похож на указатель на элемент, но на самом деле это объект, он имеет перегруженные операторы ++ и -, но не + или -. И, пожалуйста, по возможности задавайте вопросы по очереди.

rustyx 11.04.2018 11:48
std::map (если это то, что вы используете) использует двунаправленный итератор. Это итератор, поддерживающий приращение it++ и декремент it--, но не произвольное смещение it + n. Для этого вам понадобится итератор с произвольным доступом.
Emerald Weapon 11.04.2018 11:53

если вам нужны индексы, иногда лучше использовать индекс, а не итераторы. Однако, если вы хотите использовать индекс массива, почему бы вам не использовать массив в первую очередь?

463035818_is_not_a_number 11.04.2018 11:53

На самом деле мне нужна помощь по частоте каждого элемента в массиве, и я проделываю с ними кучу вещей. Итак, я решил продолжить с картой.

7k7 11.04.2018 11:57

Меня больше всего беспокоит то, что вы приписываете какой-либо смысл begin () - 1. Что вы ожидаете от этого?

Gem Taylor 11.04.2018 12:04

@EmeraldWeapon Если я перебираю карту, используя декремент it--, есть ли способ проверить граничное условие?

7k7 11.04.2018 12:12

@ 7k7 да, ты тестируешь на равенство с m.begin()

Caleth 11.04.2018 12:50

@ 7k7 Если вы перебираете std::map в обратном порядке, рекомендуется использовать reverse_iterator. И вы можете проверить граничное условие с помощью m.rbegin().

Shubham 11.04.2018 13:07
0
9
127
5

Ответы 5

Проблема в том, что итератор не работает как индексы массива. Элементы map будут храниться в разных местах в памяти, и нет гарантии, что между элементами i и j на карте, если i идет до j, то он будет храниться в памяти непосредственно перед j. В случае карты значения не сохраняются в последовательных ячейках памяти..

Оператор ++ перегружен для итераторов, и он даст правильное расположение следующего элемента.

Кроме того, если учесть приведенные выше моменты, то сравнение двух итераторов не имеет смысла, потому что тот факт, что один итератор идет за другим, не дает нам никакой важной информации о соответствующих значениях, к которым будет осуществляться доступ с помощью этих двух итераторов.

существуют разные категории / концепции итераторов: Итератор, ForwardIterator, BidirectionalIterator, RandomAccessIterator и ContiguousIterator. Они различаются доступными операциями. Простые итераторы поддерживают только шаг вперед (operator ++), разыменование (operator *) и сравнение неравенств (operator !=). Это необходимый минимум для шлейфа range-based for. std::map::iterator - это BidirectionalIterator - он не поддерживает арифметические операции и операторы сравнения.

Хорошо, я понял, что оператор ++ дает только следующий итератор на карте. Но есть ли способ найти предыдущий итератор и проверить граничное условие при повторении в обратном направлении?

7k7 11.04.2018 12:07

@ 7k7, есть два подхода: 1. (простой) использовать -- и проверять по begin() и 2. (элегантно) использовать std::make_reverse_iterator.

Andrei R. 11.04.2018 12:10

Итератор для std::map определен стандартом как Двунаправленный итератор. Этот тип итераторов можно увеличивать (оператор ++) и уменьшать (оператор --), но вы не можете выполнять с ними математические операции (в основном потому, что это займет время O (n), а не O (1)).

И снова для ошибки 2 двунаправленный итератор не перегружает оператор < (или другие варианты), поскольку нет смысла иметь оператор сравнения со сложностью O (n). Они перегружены в итераторах произвольного доступа как минимум.

Чтобы добиться желаемого, ваш код может выглядеть так:

#include <iterator> /for std::next() and std::prev()
for(auto i = m.begin; i != m.end(); ++i)
{
    auto l = i;
    auto r = i;
    if (i != m.begin())
        l = std::prev(i);
    if (i != m.end())
        r = std::next(i);
    while (l != m.begin() && r != m.end())
    {
        //make sure you don't use r if it's equal to m.end()
        --l;
        ++r;
    }

Решение проблемы x-y: я хочу сделать "это", я написал код, который делает "то"

Поэтому я предполагаю, что вы действительно хотите иметь доступ к предыдущему элементу на карте и к следующему элементу. Я полагаю, вам нужно это только тогда, когда эти 2 элемента "хороши"

Вы можете переделать свой цикл, чтобы каскадировать знание трех соседних итераторов:

for(auto r = m.begin(), e= m.end(), i= e,  l= e; r != e; l =i, i =r, r++)  
{ 
    if (l != e)
    {
         // All 3 iterators are good here
    }
}

Карта - это associative container. Следующие контейнеры определены в текущей версии стандарта C++ с associative container: set, map, multiset, multimap.

Associative Containers поддерживает bidirectional iterators. Bidirectional iterators - это итераторы, которые можно использовать для доступа к последовательности элементов в диапазоне в обоих направлениях (к концу и к началу). Они похожи на forward iterators, за исключением того, что они могут двигаться и в обратном направлении, в отличие от forward iterators, который может двигаться только в прямом направлении.

Bidirectional iterators поддерживает следующие операции:

  • Конструируется по умолчанию, может быть скопировано, присваивается копированием и разрушаемый X a;X b(a);b = a;
  • Можно сравнить на эквивалентность, используя равенство / неравенство операторы (имеет смысл, когда оба значения итератора повторяются по одному и тому же лежащая в основе последовательность). a == ba != b
  • Может быть разыменован как rvalue (если в состоянии разыменования) .
    *aa->m
  • Для изменяемых итераторов (непостоянные итераторы): можно разыменовать как lvalue (если в состоянии разыменования). *a = t
  • Может быть увеличен (если в состоянии разыменования). Результат либо также разыменованный, либо итератор прошедшего конца. Два итератора которые сравнивают равные, продолжайте сравнивать равные после того, как оба увеличиваются. ++aa++*a++
  • Может быть уменьшено (если ему предшествует разыменуемое значение итератора). --aa--*a--

Значит, для него не определены + и -, что приводит к ошибке 1.
И поэтому> =, <=,>, <не определены для него, что приводит к ошибке2.

Другие вопросы по теме