C++ 当搜索节点数达到几十万后，搜素速度快速下降，处理1000节点的时间是C#的几十倍
而C#的速度到接近1000万节点，依然很快。

C++的容器这么差？


#ifndef HUARONGDAO_H
#define HUARONGDAO_H

#include <math.h>
#include <queue>
#include <unordered_set>
#include <iostream>

#include <QtCore>

using namespace std;

#define N 4
#define L N*N

int buf[L] = {1,5,8,3,2,6,4,15,10,9,12,7,13,14,11,16};

class Node
{
public:
    Node* Parent;

    int A[L];
    int p;
    int hash,score,gen;

public:

    Node() { }

    // Parse from string
    Node(const int* a)
    {
        Parent = nullptr;
        gen = 0;
        memcpy(A,a,L*sizeof(int));

        for (int i = 0; i < L; i++)
            if (A[i] == L)
            {
                p = i;
                break;
            }
        Hash();
        Score();
    }
    ~Node(){
       // delete A;
    }

    // Move
    Node* Move(int d)
    {
        int p2 = p + d;

        if (d ==-1 && p%N==0 ) return nullptr; //左右移动后没有出界
        if (d == 1 && p % N == N-1) return nullptr; //左右移动后没有出界
        if (p2 < 0 || p2 >=L) return nullptr; //上下移动后没有出界


        Node* child = new Node();
        child->Parent = this;
        child->gen = gen+1;
        child->p = p2;
        memcpy(child->A,A,L*sizeof(int));

        child->A[p2] = A[p];
        child->A[p] = A[p2];

        child->Hash();
        child->Score();
        return child;
    }

    bool OK()
    {
        for (int i = 0; i < L; i++)
            if (A[i] != i + 1)
                return false;
        return true;
    }

    void Score()
    {
        int r = 0;
        for (int i = 0; i < L ; i++)
            r += abs((A[i]-1)%N - i%N) + 3*abs((A[i]-1)/N-i/N);

        //r += SquareSum((A[i] - 1) % N - i % N, (A[i] - 1) / N - i / N);
        //r += (A[i] == i + 1)?0:1;
        score = r;
    }

    void Hash()
    {
        hash=0;
        for(int i=0;i<L;++i)
        {
            hash = ((hash<<31) | (hash>>1) )^A[i];
        }
    }

    bool Equal(const Node * nd)const
    {
        for(int i=0;i<L;++i)
            if (A[i]!=nd->A[i])
                return false;
        return true;

    }


    void Print()
    {
        for (int i = 0; i < L; ++i)
        {
            if (A[i] == L)
                cout << "\t*";
            else
                cout <<"\t"<<(int)A[i];
            if (i % N == N-1) cout<< endl;
        }

    }
};

typedef Node* PNode;

class Comparer
{
public :
    bool operator()(Node * nd1, Node * nd2){ return nd1->score > nd2->score;}
};


class Hasher{
public:
    size_t operator()( PNode const & node)const {return node->hash;}
};

class Equal{
public:
    bool operator()(Node * const& nd1, Node * nd2)const{return nd1->Equal(nd2);}
};

//------------------------------------------------------------

void Print(Node* node)
{
   QList<Node*> nodes;
   while (node != nullptr)
   {
       nodes<<node;
       node = node->Parent;
   }

    int n= nodes.count();
   for (int i =0;i<n; ++i)
   {
       cout<<i  <<"------" <<endl;
       nodes[n-i-1]->Print();
   }

}



void Go(Node* root)
{

   priority_queue<Node*, vector<Node*>, Comparer> q ;

   unordered_set<PNode,Hasher,Equal> hist;

   q.push(root);

   while (!q.empty())
   {
       Node* node = q.top();
       q.pop();
       hist.insert(node);
       if (hist.size() % 1000 == 0)
       {
           cout<< hist.size() <<"," << node->gen <<" , " << node->score << endl;
           node->Print();
       }

       if (node->OK())
       {
           Print(node);
           return;
       }

//       if (node->gen>100)
//           continue;

       char d[] = {-1, 1, - N, N };
       for (int i = 0; i < 4; ++i)
       {
           Node* child = node->Move(d[i]);
           if (child !=nullptr){
               if (hist.count(child)==0)
                    q.push(child);
                else
                   delete child;
           }

        }
   }
}




void Run()
{
    Go(new Node(buf));

}

#endif // HUARONGDAO_H
--
修改:finlab FROM 123.112.70.*
FROM 123.112.70.*