-3

我希望能够使用类创建比较函数，例如： 

bool someClassLess(const someClass &a1, const someClass &a2) {
    return (a1.variable1 < a2.variable1 && a1.variable2 < a2.variable2);
}

然后声明someClass的优先级队列并传递我的比较函数以在推送元素时使用，例如：

PriorityQueue<someClass> arr(someClassLess());

如果在声明优先级队列时没有传递比较函数，则推送时应该自动使用函数库中的less函数。

如何将比较函数传递给类？

您可以在下面找到我自己编写的 PriorityQueue 的代码。该代码包括尝试传递比较函数失败。

#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::less;

template<typename T>
class PriorityQueue {
public:

    template<typename PRED>
    PriorityQueue(PRED compare);
    ~PriorityQueue();

    T pop();
    void push(const T &e);
    size_t getSize() const;
    bool isEmpty() const;
    void print() const;

private:

    T *end;
    T *queue;
    PRED compare;

};

template<typename T>
PriorityQueue<T>::PriorityQueue(PRED compare = less<T>()) : queue(0), end(0), compare(compare) {
}


template<typename T>
PriorityQueue<T>::~PriorityQueue() {
    delete [] queue;
}

template<typename T>
T PriorityQueue<T>::pop() {
    if(isEmpty()) {
        throw "Queue is empty";
    } else if(getSize() == 1) {
        T removed = *queue;
        delete [] queue;
        queue = end = 0;
        return removed;
    }

    T *newQueue = new T[getSize() - 1];
    // Iteratorer
    T *it = queue, *itNew = newQueue;

    T removed = *(it++);
    for( ; it != end; it++, itNew++) {
        *itNew = *it;
    }

    int oldSize = getSize();

    T *tmp = queue;
    queue = newQueue;
    delete [] tmp;

    end = queue + oldSize - 1;

    return removed;
}

template<typename T>
void PriorityQueue<T>::push(const T &e) {
    if (isEmpty()) {
        queue = new T[1];
        *queue = e;
        end = queue + 1;
        return;
    }

    T *newQueue = new T[getSize() + 1];
    // Iterators
    T *it = queue, *itNew = newQueue;

    // Find where element e should be inserted, whilst inserting elements
    // compare(*it, e) used to look like *it < e when I was initially creating the class
    for( ; compare(*it, e) && it != end; it++, itNew++) {
        *itNew = *it; 
    }

    // Insert e
    *(itNew++) = e;

    // Insert the remaining elements
    for ( ; it != end; it++, itNew++) {
        *itNew = *it;
    }

    int oldSize = getSize();

    T *tmp = queue;
    queue = newQueue;
    delete [] tmp;

    end = queue + oldSize + 1;
}

template<typename T>
size_t PriorityQueue<T>::getSize() const {
    return (end - queue);
}

template<typename T>
bool PriorityQueue<T>::isEmpty() const {
    return (getSize() <= 0);
}

template<typename T>
void PriorityQueue<T>::print() const {
    for(int *i = queue; i != end; i++) {
        cout << *i << endl;
    }
}

#endif
4

1 回答 1

3

为什么不只是无耻地复制std::priority_queue. 只需使用这个：

template <typename T, typename Compare = std::less< T > >
class PriorityQueue {
  public:
    PriorityQueue(Compare comp = Compare()) : end(0), queue(0), compare(comp) { };

    // ...

  private:

    T *end;
    T *queue;
    Compare compare;

};
于 2012-12-19T00:42:23.080 回答