iterator operations not working

Question

For some reason in this function where it counts "clumps" of two or more of the same value:

#include <iostream>
#include <iterator> 
#include <set>

int countClumps(multiset<int> set)
{
    int clumps = 0;

    for (multiset<int>::const_iterator iter(set.begin()), end(set.end()); iter != end; ++iter)
    {
        if (iter == iter[1] && iter != iter[-1])
        {
            clumps += 1;
        }
    }
    return clumps;
}

I get the error "no operator '[]' matches these operands". Why would this happen? I thought stuff like iter[i] and *(iter + i) were standard operations? I did try *(iter + 1) but that gave me the same operand error but with +. Was there something that I've forgotten to include?

Answer 1

std::multiset has a bidirectional iterator. You may not use operator [] and operator + with this iterator. Use standard functions std::next and std::prev instead to get a previous or next iterator..

Also you should compare values pointed to by iterators instead of the iterators themselves.

Take into account that it would be much better if the parameter is declared like reference.

The function can look the following way

#include <iostream>
#include <set>

size_t countClumps( std::multiset<int> &set )
{
    size_t clumps = 0;

    for ( auto first = set.begin(), last = set.end(); first != last; )
    {
        auto value = *first;
        size_t i = 0;

        while ( ++first != last && *first == value ) ++i;

        if ( i ) ++clumps;
    }

    return clumps;
}

int main() 
{
    std::multiset<int> set { 1, 1, 2, 3, 3, 3, 5, 5 };

    std::cout << countClumps( set ) << std::endl;

    return 0;
}

The program output is

3

Answer 2

I get the error "no operator '[]' matches these operands". Why would this happen?

That's because operator[] is not supported on multiset<int>::const_iterator.

I thought stuff like iter[i] and *(iter + i) were standard operations?

You thought wrong.

I did try *(iter + 1) but that gave me the same operand error but with +. Was there something that I've forgotten to include?

operator+ is not supported between a multiset<int>::const_iterator and an int. Hence, iter + 1 is not a valid expression.

You haven't forgotten to include anything. You are trying operations that are not supported on the type of the object.

You will have to rethink your code.

---

Something along the lines of the following implementation should work.

int countClumps(multiset<int> set)
{
   int clumps = 0;
   int previousNumber = 0;

   multiset<int>::const_iterator iter(set.begin());
   multiset<int>::const_iterator end(set.end());

   // Account for empty input.
   if ( iter != end )
   {
      previousNumber = *iter;

      for (++iter; iter != end; )
      {
         if ( previousNumber == *iter )
         {
            ++clumps;

            // Skip the rest of the clump
            for ( ++iter; iter != end && previousNumber == *iter ; ++iter );
         }
         else
         {
            ++iter;
         }

         if ( iter != end )
         {
            previousNumber = *iter;
         }

      }
   }
   return clumps;
}

Answer 3

The problem is that an std::multiset<>::const_iterator is a bidirectional_iterator, which does not support the dereference operator, unlike the random_access_iterator.

You could do something like this:

if (set.length() > 2)
    for (multiset<int>::const_iterator iter(std::next(set.begin())), end(std::prev(set.end())); iter != end; ++iter)
    {
        if (*iter == *std::next(iter) && *iter != *std::prev(iter))
        {
            clumps += 1;
        }
    }

But your algorithm is still wrong... I'd do (not tested):

bool first_time = true;
bool in_clump = false;
int prev_val;
for (auto element: set)
{
    if (first_time)
    {
        prev = element;
        first_time = false;
    }
    else if (element == prev)
    {
        if (!in_clump)
        {
            ++clumps;
            in_clump = true;
        }
    }
    else
    {
        in_clump = false;
    }
}