lower_bound() 算法/STL 使用前提条件

Question

如果为 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 OS & Clang++ 7.0.0(

矢量最大大小：4294967295和实际大小：2415919104 找到值 2

输出：(Windows 10 OS & 32bit-msvc(

vector太长

---

更新：虽然 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。