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;
}