Mark P wrote:[color=blue]
> Some time ago I posted here about inserting into a set with a hint:
>
>
http://groups-beta.google.com/group/...8b8d0eadb38dbf
>
>
> I quoted the SGI STL docs describing a.insert(p, t), where p is the hint
> iterator and t is the inserted object:
>
> "Insert with hint is logarithmic in general, but it is amortized
> constant time if t is inserted immediately before p."
>
> Several knowledgeable people asserted that this is contrary to the
> standard which says that t should be inserted immediately after p.
>
> I wrote a little program to test this out (see below). I then obtained
> the following results, which suggest that the SGI docs are in fact
> correct and that the insert should occur immediately before the hint.
>
> Using gcc 3.2.2 with -O3:
>
> start - no hint
> finish: 14 seconds
> start - insert after hint
> finish: 14 seconds
> start - insert before hint
> finish: 3 seconds
>
> Using Sun CC 7.1 ith -O5:
>
> start - no hint
> finish: 54 seconds
> start - insert after hint
> finish: 43 seconds
> start - insert before hint
> finish: 17 seconds
>
> Was I just confused before and the standard does say that the hint
> should point after the location of the insert? How else can these
> results be explained?
>
> Thanks,
> Mark
>
>
> TEST CODE BELOW:
>
> #include <set>
> #include <iostream>
> #include <ctime>
>
> int main() {
>
> const int MaxVal = 30000000;
> time_t startTime, endTime;
> std::set<int> is;
> std::set<int>::iterator isIter;
>
> // no hint
>
> std::cout << "start - no hint" << std::endl;
> time(&startTime);
>
> for (int i = 0; i < MaxVal; ++i)
> is.insert(i);
>
> time(&endTime);
> std::cout << "finish: " << difftime(endTime,startTime) << " seconds"
> << std::endl;
>
> // insert after hint
>
> is.clear();
> std::cout << "start - insert after hint" << std::endl;
> time(&startTime);
>
> isIter = (is.insert(0)).first;
> for (int i = 1; i < MaxVal; ++i)
> isIter = is.insert(isIter,i);
>
> time(&endTime);
> std::cout << "finish: " << difftime(endTime,startTime) << " seconds"
> << std::endl;
>
> // insert before hint
>
> is.clear();
> std::cout << "start - insert before hint" << std::endl;
> time(&startTime);
>
> isIter = (is.insert(MaxVal)).first;
> for (int i = MaxVal-1; i >= 0; --i)
> isIter = is.insert(isIter,i);
>
> time(&endTime);
> std::cout << "finish: " << difftime(endTime,startTime) << " seconds"
> << std::endl;
>
> }[/color]
Many 'set' implementations are backed by a red-black tree.
The performance of these trees degrades quickly when inserting
pre-sorted data (as you are doing here) due to all of the
tree re-balancing that must occur.
Also, many implementations have special handling for the
'hint' boundary conditions ('end()' and 'begin()').
In your last example (where you inserted data in
high-to-low order) the iterator returned by the 'insert()'
call is actually 'begin()'. Since 'insert()' has special
handling for this 'hint' the performance of the NEXT 'insert()'
call is high.
If you pass an iterator that is neither 'begin()' nor 'end()',
when 'insert()' increments that iterator and it does not
point to a valid item, insert() starts its search with
'begin()' (i.e. your 'hint' iterator is ignored).
If you are inserting data in low-to-high order this
approach will speed things up greatly:
isIter = (is.insert(0)).first;
for (int i = 1; i < MaxVal; ++i)
is.insert(is.end(), i);
Regards,
Larry
--
Anti-spam address, change each 'X' to '.' to reply directly.
