New to STL

general
,
1

I’ve started using STL in C++ but am not much comfortable with it.Could somebody tell me some good source for STL. I wanted to implement a min heap in STL C++ for Dijkstra Algorithm.Could somebody provide me with some code.Since by default the implementation is a max heap when you call make_heap()
on a vector.How should I change the compare function so that make_heap creates a min_heap?
How does the use of STL features impact the time and memory of the program from the point of view of programming competitions?

2

Definitely read this book, C++ Templates: The Complete Guide. You can download ebook from internet free of cost, just google it.

Hope it helps, Best Luck :slight_smile:

1 Like
3

In Short:

#include<functional>
std::priority_queue<T, std::vector<T> , greater<T> > a;

priority_queue has 2 different syntactic structures

  1. priority_queue a; // max heap
  2. priority_queue<Type, Container , Comparator Function / Functor> b;

To make a min priority_queue, you’ll need to pass the appropriate comparator function, which would be:

bool comp(const T& a, const T& b){
   return a > b; // Notice the greater than sign
}

or a functor:

class comp{
public:
    bool operator()(T a, T b){
        return a > b;
    }
}

So your min priority_queue would be defined as

std::priority_queue<T, std::vector<T> , comp > a;

But you can also skip all of this and simply use a standard comparator functor from #include

std::priority_queue<T, std::vector<T> , greater<T> > a;

As a thumb rule for priority_queues, make the comparison function do exactly the opposite. (For a min priority queue use greater<>, for a max priority queue use lesser<>)

4

Dont worry. Here is a very good and neat explanation some powerful stl features from topcoder…

Hope it helps…

5

Hi, try these. They should get you started.