在大型数组上使用 std::lower_bound()

Question

如果针对 32 位 Linux 系统编译，下面的代码将返回错误结果，并且如果向量足够大，同样的问题也适用于 64 位系统。

是否违反了

lower_bound

或STL的先决条件，如果违反，在哪里？

STL 来源告知我，

vector

的大小被转换为有符号类型，这解释了这种行为。

// 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）

矢量最大尺寸：4294967295，实际尺寸：2415919104
发现值2

输出：（Windows 10 操作系统和 32 位-msvc）

矢量太长

---

更新：虽然

std::vector

的修复正在进行中，但对于由

分配的数组，问题仍然存在

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

结果取决于编译器和 stdlib。

Answer 1

在 libstdc++ 中，函数

lower_bound(...)

使用

distance(...)

，它以：

开头

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

根据标准（23.2，[容器.要求]）：

表达：

a.max_size()

；返回类型：

size_type

；操作语义：

distance(begin(), end())

表示最大可能的容器

distance(...)

返回

difference_type

（24.4.4，[迭代器.操作]]

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

因此，

max_size()

应该返回一个可以使用有符号类型表示的值（在本例中是

int32_t

）。然而，

max_size()

返回

4'294'967'295

。我猜这是 libstdc++ 中的一个错误。

顺便说一下，在 Microsoft STL 实现中

max_size()

返回

2'147'483'647

。