'Will std::lower_bound be logarithmic for list<>?
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?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
