CSR 表現を用いた二次元配列
ソースコード
主な機能
const std::vector<std::vector<Elem>> を std::vector の入れ子を用いずに表現する。特に、グラフの隣接リスト表現に使うときに便利である。
テンプレート CsrArray
template<class Elem>
class CsrArray
const std::vector<std::vector<Elem>> の代替。
構築用メンバ
CsrArray();
static CsrArray Construct(int n, const std::vector<std::pair<int, Elem>>& items); // (1)
static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos); // (2)
コンストラクタで要素をもたないリストを構築できるが、要素をもつものは別の static メンバ関数で構築する。
(1)
std::vector<std::vector<Elem>> Construct(int n, const std::vector<std::pair<int, Elem>>& items){
std::vector<std::vector<Elem>> res(n);
for(auto item : items) res[item.first].push_back(item.second);
return res;
}
(2)
std::vector<std::vector<Elem>> FromRaw(std::vector<Elem> list, std::vector<int> pos){
std::vector<std::vector<Elem>> res(pos.size()-1);
for(int i=0; i<(int)res.size(); i++) res[i] = std::vector<Elem>(
list.begin() + pos[i],
list.begin() + pos[i+1]
);
return res;
}
アクセス
ListRange operator[](int u);
ConstListRange operator[](int u) const;
int size() const;
ListRangeやConstListRangeは(const) std::vector<int>&を部分的に代替するためのインターフェースをもつ。
fullSize
int fullSize() const;
全体の要素数を取得する。