c++ - 通过STL库定义dijkstra算法

Question

这里是使用宏和STL库的dijkstra算法代码

#include<iostream>
#include<vector>
#include<set>
#include<list>
#include<map>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
vector<vector<pair<int,int> > >G;
/*
  definitions:
  G.size-number of vertices
  G[i].size() is number of vertices directly reachable from vertex with index i
  G[i][j].first  is index of j-th vertex reachable from vertex i
  G[i][j].second  is length of edge heading  from vertex to vertex G[i][j].first
*/

#define N 6
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii>vvii;
#define size(a) int ((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,it) for(typeof((c).begin() it=(c).begin();it!=(c).end();it++));
#define present(c,x) ( (c).find(x)!=(c).end())
#define cpresent(c,x) (find(all(c),x)! =(c).end())
typedef vector<int>vi;
priority_queue<ii,vector<ii>,greater<ii> >Q;
vi D(N,987654321);

void dijkastra(){
    D[0]=0;
    Q.push(ii(0,0));
    while(!Q.empty()){
        ii top=Q.top();
        Q.pop();
        int v=top.second,d=top.first;
        /*
         // this check is very important
        // we analyze each vertex only once
        // the other occurrences of it on queue (added earlier) 
        // will have greater distance
                            */
        if(d<=D[v]){
            //iterate through all outcoming edge from v
            tr(G[v],it){
            }
        }
    }
}

int main(){
    return 0;
}

当我编译它时，它给我以下错误:

macros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2146: syntax error : missing ')' before identifier 'it'
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C3861: 'typeof': identifier not found
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2065: 'it' : undeclared identifier
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2065: 'it' : undeclared identifier
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2143: syntax error : missing ';' before ')'
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2143: syntax error : missing ';' before ')'
>c:\users\dato\documents\visual studio 2010\projects\allmacros_disktra\allmacros_disktra\allmacros_disktra.cpp(49): error C2059: syntax error : ')'
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

我不明白错误在哪里。

Answer 1

问题在:

#define tr(c,it) for(typeof((c).begin() it=(c).begin();it!=(c).end();it++));

typeof( 没有匹配的)

您可能还想考虑将 typedef 用于迭代器和复杂的 STL 类型，即

typedef vector<pair<int,int> > vpairs;
typedef vector<vpairs > vvpairs;
typedef vpairs::iterator vp_iter;
typedef vvpairs::iterator vvp_iter;
vvpairs G;

如果你真的想使用宏，那么:

#define tr_vp(c,it) for(vp_iter it=(c).begin();it!=(c).end();it++)
#define tr_vvp(c,it) for(vvp_iter it=(c).begin();it!=(c).end();it++)