0

So, I was solving a question and wrote this code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
   int t;
   cin >> t;

   while (t--)
   {
      int n, x;
      cin >> n;
      map <int, vector<int> > m;

      for (int i = 0; i < n; i++)
      {
         cin >> x;
         m[x].push_back(i);
      }
      int prev_ind = n;
      int ans = 0;

      for (auto i : m)
      {
         if (i.second.back() < prev_ind)
         {
            ans++;
            prev_ind = i.second[0];
         }
         else
            prev_ind = *lower_bound(i.second.begin(), i.second.end(), prev_ind);
      }
      cout << ans << endl;
   }
}

So, when I remove the pointer from the front of lower_bound function, the code shows compilation error, can anybody tell me why this happens?

JeJo
  • 30,635
  • 6
  • 49
  • 88
as617
  • 25
  • 1
  • 5
  • Please read [Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) – Jesper Juhl May 02 '20 at 14:56
  • 2
    Adding `*` in front of `lower_bound` is not "adding pointer" to anything. It's *dereferencing* the iterator returned by the function. C++ is a context sensitive language and various symbols mean different things in different contexts. `*` doesn't always mean "pointer". – Jesper Juhl May 02 '20 at 15:03

1 Answers1

4

You need to have a look at the std::lower_bound

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
//^^^^^^^^ --> iterator

It returns the iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

Meaning, you will dereference the iterator (i.e. "pointer from the front of std::lower_bound" which is called dereferencing not pointer) to get the underline element and if you need the iterator for further operations, you will not dereference it.

In your case i.second has type std::vector<int> and doing

std::lower_bound(i.second.begin(),i.second.end(), prev_ind);

returns the std::vector<int>::iterator pointing to the element as per the condition. If you need to access the element, you need to dereference it.

std::vector<int>::iterator iter_prev_ind = std::lower_bound(i.second.begin(),i.second.end(), prev_ind);
prev_ind = *iter_prev_ind ;

which in short what you have written

prev_ind = *std::lower_bound(i.second.begin(),i.second.end(),prev_ind);

However, you should be careful before dereferencing the iterator return by the std::lower_bound, as it could also be the end iterator if no such element is found in the range [first, last) (credits @eerorika).

if(auto iter_prev_ind = std::lower_bound(i.second.begin(),i.second.end(),prev_ind);
   iter_prev_ind != i.second.end()) // if not iterator end
   prev_ind = *iter_prev_ind ;

Also, have a look into the followings

JeJo
  • 30,635
  • 6
  • 49
  • 88
  • 1
    Note that generally one should check whether the search found an element before indirecting through the pointer. – eerorika May 02 '20 at 15:01