Почему и когда мы добавляем указатель перед нижней функцией в c ++? - PullRequest
Новая
       98

Почему и когда мы добавляем указатель перед нижней функцией в c ++?

1 голос
/ 02 мая 2020

Итак, я решал вопрос и написал следующий код: 

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

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

1 Ответ

4 голосов
/ 02 мая 2020

Вам нужно взглянуть на std::lower_bound

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

Это возвращает итератор, указывающий на первый элемент в диапазоне [first, last) , которое не меньше (то есть больше или равно) значению, или последнее, если такой элемент не найден.

То есть вы будете разыменовывать итератор (то есть " указатель с начала std::lower_bound ", который называется разыменование , а не указатель ), чтобы получить элемент подчеркивания, и если вам понадобится итератор для дальнейших операций, вы не будете разыменовывать Это.

В вашем случае i.second имеет тип std::vector<int> и выполнение 

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

возвращает std::vector<int>::iterator, указывающее на элемент согласно условию. Если вам нужен доступ к элементу, вам нужно разыменовать его. 

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

, что вкратце означает то, что вы написали 

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

Тем не менее, вы должны быть осторожны перед разыменованием итератор возвращает std::lower_bound, поскольку он также может быть конечным итератором, если такой элемент не найден в диапазоне [первый, последний) (кредиты @ 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 ;

Также обратите внимание на следующее

...