Using stls and stuffs like that of C++

[amishera]

Hi,

I have this question. In many of the problems here, some recurring data structures such as stack, queue, hash etc are required. In C++ standard library already contains implementation of them. So I guess it would not be wise to reinvent the wheel. I am curious to know how reliable are they compared to some C implementation. Does a C implementation of these data structures run faster than those implementation in C? Are those data structures (like hash) sophisticated enough (taking into account the product of state-of-the-art research work)? I mean the quicksort implementation in C is very seems to be very sophisticated taking into statistical staffs into account.

Thanks.

[bbi5291]

You asked how reliable they are, then you asked about speed.

The STL that comes with g++ is definitely reliable - that is, you can rely on it to give the right answer. It is the most widely used C++ compiler in academia and furthermore SPOJ uses an older version (4.1) so if there had been a bug it would have been pointed out and fixed long ago.

As for speed, the best way to answer that would be to code your own and run a benchmark.

You will probably not be able to write a function equivalent to sort() which outperforms that found in the algorithm header.

However, in certain cases you can improve performance by coding your own algorithms/data structures. One of the more common examples is the STL priority_queue, which does not allow you to increase the priority of an element. Instead, you have to push on a new element with higher priority, and ignore the lower one once it is popped. This becomes important in Dijkstra's and Prim's algorithms, where the constant factor is reduced if you implement increase-key yourself.