Thread: 2 STL questions

  1. #1
    ... arjunajay's Avatar
    Join Date
    May 2005
    Posts
    203

    Question 2 STL questions

    1)Is there some way I can make a std:riority_queue which pops in ascending order ?
    I know that it uses the '<' operator to sort while poping. So if overload '<' operator do '>' , it might work. But it is wrong to do that.

    2) is there an STL search tree or do I have make one?
    If there is no search tree, how do I search in a queue sine i dont see any mem-function or iterators access other elements in between 'front' and 'back'.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    The standard definition of priority_queue is of the form;
    Code:
    template<class T, class Container = vector<T>, class Compare = less<typename Container<T>::value_type> >
    priority_queue
    {
        // etc etc.
    }
    In response to your first question, create an object of type;
    Code:
    std::priority_queue<T, std::vector<T>, greater<typename std::vector<T>::value_type> >;
    A few typedefs would probably be helpful in achieving this

    A protected member of priority_queue is the underlying container (which is a vector<T> by default) used by the priority_queue (it's name is c). So create a class that is derived from your priority_queue<> and provide that derived classes with public member functions that provide controlled access to the underlying container. Keep in mind that, as priority_queue<> provides no virtual member functions, there are some constraints on how you can use the derived type.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    1)
    Code:
    #include <iostream>
    #include <queue>
    #include <functional> //greater<>()
    
    using namespace std;
    
    int main()
    {
    	priority_queue<int, vector<int>, greater<int> > q;
    
    	q.push(1);
    	q.push(4);
    	q.push(3);
    
    	while(!q.empty())
    	{
    		cout<<q.top()<<" ";
    		q.pop();
    	}
    	
    	cout<<endl;
    	
    	return 0;
    }
    Last edited by 7stud; 03-12-2006 at 03:25 AM.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    2) Have you considered a set<>?

  5. #5
    ... arjunajay's Avatar
    Join Date
    May 2005
    Posts
    203
    2) Have you considered a set<>
    Yes I read about those in older posts. but they where reagrding searching in Log(n) time or so.
    the thing is that I don't just want to search, but also, given the address of a leaf, I want to back track it to the root. ie, I want all the elements in sequence, lying in the path connecting root and given leaf.

    I will try the thing with the priority queue. But i didn't notice the third template argument in my header file in the morning. I saw only the first two. But Iwill check again.
    Thanks grumpy, and 7stud.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A very long list of questions... maybe to long...
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-16-2007, 05:36 AM
  2. Array of Vectors amd other STL questions
    By kolistivra in forum C++ Programming
    Replies: 16
    Last Post: 04-12-2007, 09:11 AM
  3. Some STL questions
    By g4j31a5 in forum C++ Programming
    Replies: 13
    Last Post: 07-19-2006, 11:35 PM
  4. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  5. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM