Как я могу получить общее количество элементов между двумя итераторами?

Я написал функцию для проверки уникальности всех элементов в контейнере.

template<class InputIt>
bool all_elements_unique(InputIt first, InputIt last){
  std::set<typename std::iterator_traits<InputIt>::value_type> s(first,last);
  return s.size() == std::distance(first,last);
}

Оно работает. Однако size_t, возвращенное из size(), и difference_type, возвращенное из distance(), имеют разные знаки.

 warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

std::distance может возвращать отрицательные числа в зависимости от направления итераторов.

Если это так, как я могу надежно получить общее количество элементов между двумя итераторами, когда количество элементов превышает максимальное значение со знаком? Я искал что-то вроде std::size, но он занимает целый контейнер .


c++ containers iterator stl iterator-traits
person Trevor Hickey    schedule 17.05.2016    source источник
comment
когда количество элементов превышает максимальное значение со знаком? Я еще не видел, чтобы это происходило в реальном мире. В 64-битных системах этого не будет.   -  person Baum mit Augen    schedule 17.05.2016
comment
Кроме того, входной итератор здесь недостаточно силен, увеличение на единицу делает недействительными все копии. Вам нужен как минимум прямой итератор.   -  person Baum mit Augen    schedule 17.05.2016
comment
А так как расстояние считает элементы, а не байты. Это также не произойдет в 32-битной системе.   -  person MikeMB    schedule 17.05.2016
comment
@MikeMB: в некотором коде используется vector<char> (или даже пресловутый vector<bool>).   -  person Tony Delroy    schedule 17.05.2016
comment
@MikeMB vector<bool>::iterator передает привет :)   -  person T.C.    schedule 17.05.2016
comment
@MikeMB Технически может быть vector<char>, который потребляет более половины всей оперативной памяти. Но да, когда это было в последний раз? (vector<bool> может даже переполнить size_t! В каком страшном мире мы живем.)   -  person Baum mit Augen    schedule 17.05.2016
comment
Итак, я должен просто static_cast получить то, что я получаю от std::distance, и двигаться дальше?   -  person Trevor Hickey    schedule 17.05.2016
comment
@TrevorHickey Если вы не знаете, что у вас есть это особое требование, я бы сказал «да».   -  person Baum mit Augen    schedule 17.05.2016
comment
Кстати, вот что некоторые члены комитета думают о беззнаковых целых числах: channel9.msdn.com/Events/GoingNative/2013/ 9:50, 42:40, 1:02:50 Думаю, они более авторитетны, чем я.   -  person Baum mit Augen    schedule 17.05.2016
comment
static_cast<> и двигаться дальше звучит разумно, или вы циклически выполняете и подсчитываете наборы вставок. Если вы хотите пофантазировать, вы можете создать вспомогательный тип оболочки, который подсчитывает количество инкрементов содержащегося/управляемого итератора, поэтому конструктор set случайно вычисляет расстояние. (Вам также нужно будет обернуть итератор last при его предоставлении, чтобы они были одного типа, но не было бы итераций с использованием дополнительного счетчика).   -  person Tony Delroy    schedule 17.05.2016
comment
На самом деле, если sizeof(T) == 1, вы можете сделать вывод, что не все элементы уникальны, если исходный размер больше 256, поэтому вы можете проверить это перед вызовом вышеуказанной функции, если вы супер параноик.   -  person Baum mit Augen    schedule 17.05.2016
comment
@TC: А сколько там уникальных символов и логических значений? Я надеюсь, что никто не попытается поместить 2 ^ 31 элемент в набор символов, чтобы определить, все ли они уникальны. ;)   -  person MikeMB    schedule 17.05.2016
comment
@Tony D и другие. И да, вероятно, существует 32-битная система с CHAR_BIT › 8, которая может адресовать более 2 ^ 32 байт памяти, что не учитывалось в моем утверждении.   -  person MikeMB    schedule 17.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

Если это так, как я могу надежно получить общее количество элементов между двумя итераторами, когда количество элементов превышает максимальное значение со знаком?

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

Я бы либо передал ваш контейнер в качестве ссылки, либо заменил бы ваш исходный метод:

template<class Container>
bool all_elements_unique(Container& c) {
  std::set<typename Container::value_type> s(std::begin(c), std::end(c));
  return s.size() == c.size();
}

Или сделать сортировку и adjacent_find:

template<class Container>
bool all_elements_unique(Container& c) {
  std::sort(c.begin(), c.end());
  return std::adjacent_find(c.begin(), c.end()) == c.end();
}
person uh oh somebody needs a pupper    schedule 17.05.2016