4

ヒープを使用する必要があるため、STL について検索しましたが、機能していないようです。意味を説明するコードをいくつか書きました。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

struct data
{
    int indice;
    int tamanho;
};


bool comparator2(const data* a, const data* b)
{
    return (a->tamanho < b->tamanho);
}

int main()
{

        std::vector<data*> mesas;

        data x1, x2, x3, x4, x5;

        x1.indice = 1;
        x1.tamanho = 3;

        x2.indice = 2;
        x2.tamanho = 5;

        x3.indice = 3;
        x3.tamanho = 2;

        x4.indice = 4;
        x4.tamanho = 6;

        x5.indice = 5;
        x5.tamanho = 4;

        mesas.push_back(&x1);

        mesas.push_back(&x2);

        mesas.push_back(&x3);

        mesas.push_back(&x4);

        mesas.push_back(&x5);


        make_heap(mesas.begin(), mesas.end(), comparator2);

        for(int i = 0 ; i < 5 ; i++)
        {
            data* mesa = mesas.front();
            pop_heap(mesas.begin(),mesas.end());
            mesas.pop_back();

            printf("%d, %d\n", mesa->indice, mesa->tamanho);
        }

    return 0;
};

そして、これは私が得るものです:

4, 6
2, 5
1, 3
3, 2
5, 4

したがって、ベクトルの最大要素が正しく返されないため、ヒープとして機能しません。

それとも私は何か間違ったことをしていますか？

4

4 に答える 4

14

それがヒープを作成した方法であるため、comparator2に渡す必要があります。std::pop_heapそれ以外の場合は、ポインタ値を単純に比較するデフォルトの小なり演算子をポインタに使用します。

于 2010-05-11T21:28:44.307 に答える
1

MSN の回答は正しいです。ただし、いくつかのスタイル ガイドラインのいずれかによって、このエラーを防ぐことができます。

  • オブジェクトではなく、参照に対して動作するようにコンパレータを宣言しますoperator<。vectorポインターではなく、オブジェクトの a を使用します。

    bool comparator2(const data& a, const data& b)
{
    return (a.tamanho < b.tamanho);
}

    ポインターのベクトルが本当に必要な場合がありますが、その場合は当てはまりません。

  • std::priority_queue(from <queue>)を使用します。これは、コンパレーターpop_heapをpop_back覚えておいてください。これには、ファンクター コンパレーターが必要です。

    struct comparator2 { bool operator()(const data& a, const data& b)
{
    return (a.tamanho < b.tamanho);
} };
 
std::priority_queue<data, vector<data>, comparator2> mesas;
 // or std::priority_queue<data, vector<data>, comparator2>
mesas.push(x1);

  • 最も洗練された方法は、これを のデフォルトの比較にすることですdata:

    struct data
{
    int indice;
    int tamanho;
     
    friend bool operator<(const data& a, const data& b)
    {
        return (a.tamanho < b.tamanho);
    }
};
std::priority_queue<data> mesas;
mesas.push(x1);

priority_queueまた、事前に入力されたソートされていないコンテナーを受け取ることもできます。これはコピーされます。

于 2010-05-11T22:22:47.257 に答える
0

std::setはどうですか

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <set>

struct data
{
    // Always put constructors on.
    // When the constructor is finished the object is ready to be used.
    data(int i,int t)
        :indice(i)
        ,tamanho(t)
    {}

    int indice;
    int tamanho;

    // Add the comparator to the class.
    // Then you know where to look for it.
    bool operator<(data const& b) const
    {
        return (tamanho < b.tamanho);
    }
};



int main()
{

        std::set<data> mesas;

        // Dont declare all your variables on the same line.
        // One per line otherwise it is hard to read.
        data x1(1,3);
        data x2(2,5);
        data x3(3,2);
        data x4(4,6);
        data x5(5,4);

        mesas.insert(x1);
        mesas.insert(x2);
        mesas.insert(x3);
        mesas.insert(x4);
        mesas.insert(x5);
        // You don't actually need the variables.
        // You could have done it in place.
        mesas.insert(data(6,100));

        // Use iterator to loop over containers.
        for(std::set<data>::iterator loop = mesas.begin(); loop != mesas.end(); ++loop)
        {
            printf("%d, %d\n", loop->indice, loop->tamanho);
        }

    return 0;
};
于 2010-05-11T22:03:10.320 に答える
0

同様の問題があり、次のような方法で解決できました。

struct comparator2 { bool operator()(data const * const a, data const * const b)
{
    return (a->tamanho < b->tamanho);
 } };

std::priority_queue<data*, std::vector<data*>, comparator2> mesas;
于 2013-11-25T05:10:49.517 に答える