c++ - 如何提高邻接表分配的速度？

Question

在确定 adjacency matrix 不适用于 80513 节点和 5899882 边后，我已经决定应用邻接表。这是我第一次实现邻接表，基本上我决定应用 vector 方法的 vector 。

因此，例如，vectorOfVectors[5] 将包含包括邻居节点5。可以找到我正在使用的数据集 here

目前我已经编写了这段代码并且它可以正常运行，但是在我的电脑上它需要 26 秒(i5 2.4 和 6 GB 内存，运行 Win7)。我想知道是否可以改进我的代码以降低分配速度。

PS:我正在使用 fstream 库并从 .csv 文件中读取数据。

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>

using namespace std;

int main()
{
    ifstream file("edges.csv");
    string word="",data="";
    getline(file,word);
    int arrTemp[3];
    int numberOfNodes=atoi(word.c_str());
    vector<int>temp;
    vector< vector<int> >adjacencyList;

    for(int i=0;i<numberOfNodes;i++)
    {
        adjacencyList.push_back(temp);
    }
    while(file.good() && getline(file,word))
    {
        //cout<<word<<endl;
        if(word.size()>0)
        {
            for(int i=0;i<3;i++)
            {
                int cutFrom=word.find_first_of(',');
                arrTemp[i]=atoi(word.substr(0,cutFrom).c_str());
                word=word.substr(cutFrom+1,word.length());
            }
            //cout<<arrTemp[0]<<" "<<arrTemp[1]<<endl;
            adjacencyList[arrTemp[0]-1].push_back(arrTemp[1]-1);

        }
        else
            break;
    }

    cout<<"Vector size:"<<adjacencyList[1].size()<<endl;
    return 0;
}

Answer 1

更好的方法是节点索引对的unordered_set(其中索引对总是首先列出较小的节点)。