std::lower_bound 是 list<> 的对数吗？

Question

假设我有一个 list<int> 并将其保持在有序状态。我可以使用这样的代码以对数复杂度向其中插入新值吗

#include <iostream>
#include <random>
#include <list>
#include <algorithm>

using namespace std;

ostream& operator<<(ostream& out, const list<int> data) {
    for(auto it=data.begin(); it!=data.end(); ++it) {
        if(it!=data.begin()) {
            out << ", ";
        }
        out << (*it);
    }
    return out;
}

int main() {

    const int max = 100;
    mt19937 gen;
    uniform_int_distribution<int> dist(0, max);
    list<int> data;

    for(int i=0; i<max; ++i) {
        int val = dist(gen);

        auto it = lower_bound(data.begin(), data.end(), val);
        data.insert(it, val);

    }

    cout << data << endl;
}

我会说不是，因为不可能将迭代器定位在 list 中 O(1) 但 documentation says strange:

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::lower_bound (resp. std::multiset::lower_bound) should be preferred.

即它不建议将此功能用于 set，它是内部的替代搜索树。那么这个函数打算使用哪些容器呢？那么如何插入和维护排序呢？

Answer 1

Will std::lower_bound be logarithmic for list<>?

没有。引用文档：

for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

Which containers this function is inteded to use then?

std::lower_bound 适用于任何已订购或可以订购的容器，并且没有依赖于其内部结构的更快的下限算法 - 不包括 std::set 和 std::multiset 如文档中所述。

std::lower_bound 是 list<> 的对数吗？

Will std::lower_bound be logarithmic for list<>?

c++

binary-search

lower-bound