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?
Answer
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.
Related Questions
- → Comparing two large files are taking over four hours
- → Setting JSON node name to variable value
- → Compiling GLUT using Emscripten
- → Evaluate check box from a scanned image in node.js
- → Find an easy web server framework for mobile game
- → my https C++ code doesn't work on some sites (binance)
- → Error while opening pivx wallet on ubuntu
- → Why sending a POST by AJAX is interpreted by the HTTP Server as OPTIONS and sending by CURL is effectively a PUT?
- → Python reading in one line multiple types for a calculator
- → How do I properly pass an argument to a function
- → Accessing Websql database with Qt
- → Using Mysql C API for c++ codes
- → How do I set constants at run-time in a c++ header file, imported through Cython?