ベクトルのシーケンスを作成するC++

Question

ベクトルが、私は次をコーディングするフォーム

struct node 
     {string key; 
     int a,b; }; 

の構造のベクトルを意味：ユーザーが指定した数を考えるとはd私はシーケンスを作成したいと言いますdベクターv_1, v_2, ...v_d。

v_1は、ユーザーデータから作成され、v_iからv_(i-1)はi>=2です。 v_iの サイズは別個keyフィールドとv_(i-1)内のノードの数です。 v_iノードの aとbフィールドはv(i-1)

どのように私はC++で効率的にこれをコーディングする必要があるのものの中からいくつかのブラックボックス化アルゴリズムに従って計算されますか？ 私はint型のフィールドが1とdの間で変化し、フォーム map<int, vector<nodes>>のマップを使うべき？

ありがとうございました！

P：S：私は1つの代わりのベクターを使用する、newオペレータといくつかのポインタ体操を使用して、溶液をコーディングすることができることを推測。しかし、私は可能な限りポインタを自由にしたいと思っています。

Answer 1

使用std::vector<std::vector<node> >が、回避するために、インテリジェントvector::reserve()を使用して再配分：

using std::vector; 
vector<vector<node>> v(d); // 0 nodes allocated, no wasted space yet 

using std::copy; 
using std::istream_iterator; 
using std::back_inserter; 
// Wish I could v[0].reserve(), but we don't have that info yet. 
copy(istream_iterator<node>(std::cin), istream_iterator<node>(), back_inserter(v[0])); 

// foreach v[1..d-1], compute v[i] from v[i-1] 
for(int i = 1; i < d; ++i) { 
    int size = ComputeSize(v[i-1]); // how big a list do we need? 
    v[i].reserve(size); // reserve the space for it, and 
    PopulateVectorFromVector(v[i-1], v[i]); // fill it in. 
} 

無駄な空間と時間を持つ唯一のベクトルをv [0]。

---

EDIT：上記 std::copyの呼び出しが

node tmp; 
while(std::cin >> tmp) { 
    v[0].push_back(tmp); 
} 

std::copyとほぼ同等ループレスイディオムである3つの引数を取ります。最初の二つは、第三の宛先を定義output iteratorあるが、我々は、コピー元の範囲を定義input iteratorsです。

具体的には、istream_iterator<node>(std::cin)は、逆参照されると、標準入力ストリームから次のnodeを読み込む入力イテレータです。 back_inserter(v[0])は、参照解除されて割り当てられたときにv[0].push_back()を呼び出す出力イテレータです。

Answer 2

あなたのコンテナ型として範囲0..d、なぜstd::vector<std::vector<node> >を必要と考えますか？