Préconditions d'utilisation de l'algorithme/STL lower_bound()

Question

Le code ci-dessous renvoie des résultats erronés s'il est compilé pour des systèmes Linux 32 bits, et le même problème s'applique aux systèmes 64 bits, si les vecteurs sont suffisamment grands.

Les conditions préalables de lower_bound ou de la STL en général ont-elles été violées, et si oui, où ?

Des sources STL m'ont informé que la taille du vecteur est convertie en un type signé, ce qui explique ce comportement.

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

Sortie : (Linux OS & Clang++ 7.0.0)

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

Sortie : (Windows 10 OS & 32bit-msvc)

vector<T> too long

---

Mise à jour : Alors qu'une correction pour std::vector est en cours, le problème persiste pour les tableaux alloués par

auto p= new uint8\_t\[sz\]; // 2.25 G entries 

et le résultat dépend du compilateur et de la stdlib.

Answer 1

Dans libstdc++, la fonction lower_bound(...) utilise distance(...) ça commence par :

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

Selon la norme (23.2, [exigences relatives aux conteneurs]) :

Expression : a.max_size() ; type de retour : size_type ; sémantique opérationnelle : distance(begin(), end()) pour le plus grand conteneur possible

distance(...) renvoie à difference_type (24.4.4, [iterator.operations])

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

D'où, max_size() doit retourner une valeur qui peut être représentée par un type signé ( int32_t en l'espèce). Cependant, max_size() renvoie à 4'294'967'295 . Je suppose que c'est un bogue dans libstdc++.

Au fait, dans l'implémentation STL de Microsoft max_size() renvoie à 2'147'483'647 .