Создание последовательности векторов 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 - это количество узлов в v_(i-1) с различными полями key.Поля a и b узлов v_i вычисляются в соответствии с некоторым алгоритмом черного ящика из полей v(i-1)

Как мне эффективно кодировать это в C ++?Должен ли я использовать карту вида map<int, vector<nodes>>, где поле int варьируется от 1 до d ??

Спасибо!

P: S: Полагаю, можно было бы закодировать решение, используя оператор new и некоторую гимнастику указателей вместо векторов.Но я бы хотел иметь как можно более свободное решение по указателю.

Answer 1

Если вам нужен диапазон 0..d, почему бы не std::vector<std::vector<node> > в качестве типа вашего контейнера?

Answer 2

Используйте 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, принимает три аргумента.Первые два - входные итераторы , которые определяют диапазон, из которого мы копируем, а третьи - выходной итератор , определяющий место назначения.

В частности, istream_iterator<node>(std::cin) - итератор ввода, который при разыменовании считывает следующий node из стандартного потока ввода.back_inserter(v[0]) - это выходной итератор, который при разыменовании и назначении вызывает v[0].push_back().