CODEWITHSUNDEEP
c++c++11dictionaryiterator
7k7
7k7

Reputation: 11

Confusion in concept of iterator in map in C++

Suppose I have a map named m and an iterator i for the map. Presently I am visualising a map iterator as an array index and I want to implement a code like the one given below:

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--;
  }
}

Now, I have got some questions which has been confusing me a bit.

For the error type 1 stated in the code, incrementing or decrementing the iterator value gives error, but the similar operation done within the loop (I mean to say i++) gives no error.

For error type 2, why does comparing two iterators (l >= m.begin()), straight up give error, but doing the similar operation in a loop does not give error?

And finally, how could I make this code work on the lines of how an array index works using this map? I hope you can understand what I am trying to implement.

Upvotes: 0

Views: 903

Answers (5)

Abhishek Keshri
Abhishek Keshri

Reputation: 3244

Map is an associative container. The following containers are defined in the current revision of the C++ standard with associative container: set, map, multiset, multimap.

Associative Containers support bidirectional iterators. Bidirectional iterators are iterators that can be used to access the sequence of elements in a range in both directions (towards the end and towards the beginning). They are similar to forward iterators, except that they can move in the backward direction also, unlike the forward iterators, which can move only in forward direction.

Bidirectional iterators support following operations:

  • Is default-constructible, copy-constructible, copy-assignable and destructible X a; X b(a); b = a;
  • Can be compared for equivalence using the equality/inequality operators (meaningful when both iterator values iterate over the same underlying sequence). a == b a != b
  • Can be dereferenced as an rvalue (if in a dereferenceable state).
    *a a->m
  • For mutable iterators (non-constant iterators): Can be dereferenced as an lvalue (if in a dereferenceable state). *a = t
  • Can be incremented (if in a dereferenceable state). The result is either also dereferenceable or a past-the-end iterator. Two iterators that compare equal, keep comparing equal after being both increased. ++a a++ *a++
  • Can be decremented (if a dereferenceable iterator value precedes it). --a a-- *a--

So, + and - is not defined for it, which leads to the error1.
And so is >=, <=, >, < not defined for it, which leads to error2.

Upvotes: 3

Gem Taylor
Gem Taylor

Reputation: 5635

Solving the x-y problem: I want to do "this", I wrote code that does "that"

So I presume you really do want to have access to the previous element in the map, and the next element. I presume you only want this when those 2 elements are "good"

You could recast your loop to cascade the knowledge of the 3 neighbouring iterators:

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
    }
}

Upvotes: 1

Yksisarvinen
Yksisarvinen

Reputation: 22394

Iterator for std::map is defined by standard as Bidirectional Iterator. This type of iterators can be incremented(operator ++) and decremented (operator --), but you can't perform mathematical operations on them (mostly because it would take O(n) time rather than O(1))

And again, for error 2, bidirectional iterator does not overload < operator (nor other variations), as it doesn't make sense to have compare operator with O(n) complexity. They are overloaded in random access iterators at the lowest.

To achieve what you wanted, your code can look like this:

#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;
    }

Upvotes: 3

Andrei R.
Andrei R.

Reputation: 2462

there are different iterator categories/concepts: Iterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator and ContiguousIterator. They differ in available operations. Simple iterators only support step forward (operator ++), dereference (operator *) and inequality comparison (operator !=). This is the required minimum for range-based for loop. std::map::iterator is BidirectionalIterator - it doesn't support arithmetic or comparison operators.

Upvotes: 0

Shubham
Shubham

Reputation: 2855

The problem is iterator doesn't work like array indices. The elements of map will be stored at different locations in memory and there is no guarantee that the between elements i and j in map, if i comes before j, then it will be stored in memory just before j. The values are not stored at consecutive locations in memory in case of map.

The ++ operator is overloaded for iterators and it will give the proper location of the next element.

Also, if you consider the points above, then comparing two iterators makes no sense because the fact that one iterator comes after another doesn't give us any important information regarding the corresponding values that will be accessed using these two iterators.

Upvotes: 0

Related Questions