Re: std::set constructor taking a sorted sequence
Rosarin Roy wrote:
On Jun 10, 6:15 pm, Zeppe <z...@remove.all.this.long.comment.email.it>
wrote:
desktop wrote:
In the C++ standard page 472 it says that you can construct a std::set
in linear time if the constructor gets a sorted sequence of elements.
[cut]
Most of the standard libraries make use of red-black trees for
implementing set and map. In such case the insertion cannot be linear
in time, immaterial of input is sorted or not sorted. And the claim
that "you already know where to place the element" is not true across
calls, as the search always begins at root.
as you can see from the quoted message, the OP says that "you can
construct a std::set in linear time if the constructor gets a sorted
sequence of elements." Of course if you make different calls it's not
true any more. The reference constructor is that one accepting iterator
first, iterator last. In that case, the comparison is done on the fly
while inserting. I don't really know the red-black tree behaviour, but I
can expect (correct me if I'm wrong) that, being a balanced binary tree,
the insertion will imply a tree rebalancing which is O(1) (that is, it
does not depend on the number of nodes). So, if I already know where to
put the next value, I just have to do the balancing, that is O(1), and
the total complexity is O(n).
I wrote a test program (which I tested on Solaris running Sun C++ 5.8
compiler) to confirm that sorted elements' insertion doesn't take
linear time.
I am still curious to know if it is possible to construct a set in
linear time.
You have to build the set with the proper constructor. You will see a
nice linear increment in the performance. Use this test:
#include <set>
#include <vector>
#include <boost/date_time/posix_time/posix_time.hpp>
int main()
{
std::vector<long> v(100000);
for(std::size_t i = 0; i < 100000; ++i){
v[i] = i;
}
for(std::size_t i = 0; i < 100; ++i){
std::vector<long>::const_iterator begin = v.begin();
std::vector<long>::const_iterator end = v.begin() + 1000 * i;
boost::posix_time::ptime startTime =
boost::posix_time::microsec_clock::local_time();
std::set<long> s(begin, end);
boost::posix_time::ptime endTime =
boost::posix_time::microsec_clock::local_time();
std::cout << endTime - startTime << std::endl;
}
return 0;
}
and plot the results.
Regards,
Zeppe