Предварительные условия использования алгоритма lower_bound()/STL

Приведенный ниже код возвращает ошибочные результаты, если он скомпилирован для 32-битных систем Linux, и та же проблема применима к 64-битным системам, учитывая достаточно большие векторы.

Были ли нарушены предварительные условия lower_bound или STL в целом, и если да, то где?

Источники STL сообщили мне, что размер вектора приведен к знаковому типу, что объясняет поведение.

// compile with and without -m32 switch
#include<algorithm>
#include<iostream>
#include<stdexcept>
#include<vector>
using namespace std;
int main() {
 try {
  vector<uint8_t> v((1ULL << 28) * 9, 2); // 2.25 G entries
  v.back() = 3;                           // the last of which is greater
  cout<< "Vector maximal size: "<<v.max_size()<< " and actual size: " << v.size() <<endl;
  uint8_t val=3;
  auto x= lower_bound(v.begin(), v.end(), val );
  if (x!=v.end() && !( val< *x ) ) {
   cout << "Found value " << int(*x) << endl;
  } else {
   cout << "Not Found " << endl;
  }
 } catch (exception const & ex){
  cerr<< ex.what()<<endl;
 }
}

Вывод: (ОС Linux и Clang++ 7.0.0)

Vector maximal size: 4294967295 and actual size: 2415919104
Found value 2

Вывод: (ОС Windows 10 и 32bit-msvc)

vector<T> too long

Обновление: пока идет исправление для std::vector, проблема сохраняется для массивов, выделенных

auto p= new uint8_t[sz]; // 2.25 G entries

и результат зависит от компилятора и stdlib.


c++ linux c++17 stl stl-algorithm
person Heiko Bloch    schedule 18.08.2018    source источник
comment
Есть ли v.size() > v.max_size() в вашей подборке?   -  person Evg    schedule 18.08.2018
comment
Нет, Linux max_size()=4G слишком велик, а Microsoft STL подходит. Выдает bad_alloc?   -  person Heiko Bloch    schedule 18.08.2018
comment
Выдает std::length_error ([vector.capacity], reserve(): Выдает: length_error, если n > max_size()).   -  person Evg    schedule 18.08.2018

Ответы (1)


arrow_upward
4
arrow_downward

В libstdС++ функция lower_bound(...) использует distance(...), она начинается с:

typedef typename iterator_traits<_ForwardIterator>::difference_type  _DistanceType;
_DistanceType __len = std::distance(__first, __last);
...

Согласно Стандарту (23.2, [container.requirements]):

Выражение: a.max_size(); тип возврата: size_type; операционная семантика: distance(begin(), end()) для максимально возможного контейнера

distance(...) возвращает difference_type (24.4.4, [iterator.operations]]

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);

Следовательно, max_size() должно возвращать значение, которое может быть представлено с использованием знакового типа (в данном случае int32_t). Однако max_size() возвращает 4'294'967'295. Я предполагаю, что это ошибка в libstdС++.

Кстати, в реализации Microsoft STL max_size() возвращает 2'147'483'647.

person Evg    schedule 18.08.2018