Suppose I have a list<int> and maintaining it in ordered state. Can I isert new values into it with logarithmic complexity with code like this

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

I would say not, because it is impossible to position iterator in list in O(1) but 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.

i.e. it doesn't recomment to use this function for set which is alterady search tree internally. Which containers this function is inteded to use then? How to insert and maintain sorted then?

CodePudding user response：

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

No. Quote from documentation:

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

Which containers this function is inteded to use then?

std::lower_bound is intended for any container that is - or can be - ordered, and doesn't have faster lower bound algorithm that relies on its internal structure - which excludes std::set and std::multiset as mentioned in the documentation.