Re: set constructor performance on Visual Studio 2003
"Hans Bos" <hans.bos@xelion.nl> wrote in message
news:475c8fc8$0$240$e4fe514c@news.xs4all.nl...
"Marco Manfredini" <ok_nospam_ok@phoyd.net> wrote in message
news:fj740l$cbl$1@aioe.org...
gast128@hotmail.com wrote:
Dear all,
from Austern's 'Generic Programming and the STL' (9.3.6), one can read
that the set range constructor perfroms NlogN, while if sorted it can
become N. However doing a test the opposite seems true: using sorted
input is always slower:
Set1 insert unsorted 3.297000
Set2 insert sorted 3.500000 //uses a sorted vector a sinput
Set3 insert sorted 1.765000 //uses insert hint
Set4 insert sorted 3.625000 //uses a sorted vector a sinput, but
...
You may consider varying n in your example and observe how the run times
for sorted and unsorted construction *change*. Also:
I created a small test program where the size of the sets varies.
For visual express 2005 in release mode (and _HAS_ITERATOR_DEBUGGING set
to 0),
I get the following results:
filling 10000 sets of 1000 elements ... done in 5.031
filling 1000 sets of 10000 elements ... done in 6.078
filling 100 sets of 100000 elements ... done in 13.451
filling 10 sets of 1000000 elements ... done in 26.965
filling 1 set of 10000000 elements ... done in 36.917
This suggests that insertion of n sorted elements is not lineair with this
implementation.
When I modify the program to insert the values one by one, I get the same
timing.
So it seems that this implementation does not conform to the standard.
Yep, you're right. I missed that requirement, for both construction and
insert from an ordered range. For a quick fix, you can change the last
line of the set constructor:
template<class _Iter>
set(_Iter _First, _Iter _Last,
const key_compare& _Pred)
: _Mybase(_Pred, allocator_type())
{ // construct set from [_First, _Last), comparator
_DEBUG_RANGE(_First, _Last);
for (; _First != _Last; ++_First)
// this->insert(*_First);
this->insert(this->end(), *_First);
}
Of course the proper fix is to have all such constructors call the range
inserts, then change those to use insert with hint.
Thanks for pointing out the oversight.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]