std::equal_range for vector of pairs throws < operator error

Question

I'm trying to write a Priority Queue/Heap implementation which allows for iteration, deletion of elements, changes to the keys and values during iteration, and finding all elements with a certain key. std::priority_queue does not support iteration and boost::heap does not support changes to keys and values during iteration. I also tried using std::multimap, but it also has problems with changing values during iteration.

My queue is stored as a std::vector of std::pairs<double, T>. I thought I could use std::sort and std::equal_range functions without defining my own comparator because std::pair automatically overloads the < operator. Also, this question suggests that using std::equal_range with containers of pairs is possible, but I'm getting the following compiler errors for std::equal_range.

'bool std::operator <(const std::vector<_Ty,_Ax> &,const std::vector<_Ty,_Ax> &)' : could not deduce template argument for 'const std::vector<_Ty,_Ax> &' from 'const double'

and

binary '<' : no global operator found which takes type 'std::pair<_Ty1,_Ty2>' (or there is no acceptable conversion)

My guess is that this has something to do with using a template, but in that case, I would also expect std::sort to fail.

To summarize

Why is the automatic overloading of std::pair < not working for std::equal_range?
Do I need to define a comparator for my priority queue?

My implementation is as follows

Test

int main()
{
    PriorityQueue<double> queue;
    queue.push(1, 1);
    queue.remove(0);
    queue.cleanup(); //This call throws the error when it calls std::equal_range
}

Header

#include <vector>
#include <utility>
#include <algorithm>

template<typename T>
class PriorityQueue
{
    T item;
    typedef typename std::vector<std::pair<double, T>>::iterator It;

    private:
        std::vector<std::pair<double, T>> queue;
        bool isSorted;
        bool hasRemoved;

        void sort(){
            std::sort(queue.begin(), queue.end());
        };

    public:

        PriorityQueue():isSorted(true), hasRemoved(false){};

        void push(double cost, T val)
        {
            isSorted = false;
            queue.push_back(std::make_pair(cost, val));
        };

        void remove(int i)
        {
            hasRemoved = true;
            isSorted = false;
            queue[i].first = DBL_MAX; //Pushes element to end of list
        };

        void cleanup()
        {
            if(!isSorted) sort();
            if(hasRemoved)
            {
                std::pair<It, It> remove = std::equal_range(queue.begin(), queue.end(), DBL_MAX); // This line throws the error
                queue.erase(remove.first, remove.second);
            }
        };
};

`std::equal_range(queue.begin(), queue.end(), DBL_MAX);` tries to compare a `pair` with a `double`. `pair` only provides an `operator<` that compares to another `pair`, lexicographically comparing the two members of each object. — dyp, Jul 08 '14 at 19:40
You can iterate over the contents of a `priority_queue` by inheriting from it and accessing the underlying container. However, it is likely to be ordered as a heap, not sorted. — juanchopanza, Jul 08 '14 at 19:43

score 1 · Accepted Answer · answered Jul 08 '14 at 19:41

1

The error is that you are giving a list of pairs , say {{0,1},{1,2},{2,3}...} and are asking to find the range of values equal to (for example) 2. The compiler has no idea how to compare a pair<double,double> and a double.

answered Jul 08 '14 at 19:41

SirGuy

10,660
2
36
66

@dyp yeah, I realized that after rechecking the question. – SirGuy Jul 08 '14 at 19:46
Yep, that was what I was going for. Missing the type mismatch was definitely a case of tunnel vision. Given the source of the error, I would guess that I will need a custom comparator to only match the first member. – Cecilia Jul 08 '14 at 19:47
Just a link for future seekers about how to go about overloading the comparison operator http://stackoverflow.com/questions/24308993/stdequal-range-not-working-with-strucutre-having-operator-defined – Cecilia Jul 09 '14 at 11:59

std::equal_range for vector of pairs throws < operator error

To summarize

My implementation is as follows

1 Answers1