-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 に答える