Массив векторов или вектор массивов?

Ответ 1

Так делает ли это (vector<int> adj[N];) создание массива векторного типа или создает вектор массивов?

Он создает массив векторов

В чем разница между

vector< vector<int> > N; 

и

vector<int> F[N]

В первом случае вы создаете динамический массив динамических массивов (вектор векторов). Размер каждого вектора можно было бы изменить во время выполнения, и все объекты будут выделены в куче.

Во втором случае вы создаете массив векторов фиксированного размера. Вы должны определить N во время компиляции, и все векторы будут помещены в стек ^† однако каждый вектор будет выделять элементы в куче.

Я всегда предпочитаю вектор вектора векторов (или матрицу, если вы можете использовать сторонние библиотеки) или std::array of std::array в случае размеров времени компиляции.

Я новичок в С++ STL, и у меня проблемы с пониманием графика представление.

Вы также можете представлять график как std::unordered_map<vertex_type,std::unordered_set<vertex_type>>, где vertex_type - тип вершины (int в вашем случае). Этот подход может быть использован для уменьшения использования памяти, когда количество ребер невелико.

^†: Если быть точным - не всегда на стеке - он может быть частью сложного объекта в куче. Кроме того, стандарт С++ не определяет никаких требований к стеку или куче, он обеспечивает только требования к длительности хранения, такие как автоматический, статический, потоковый или динамический.

Ответ 2

vector<int> arr[N];

Он отображает массив вектора, каждый массив [i] будет иметь в нем вектор, который может проходить через многие значения. Это похоже на массив связанных списков, где головки хранятся только в ячейках [i].

vector<vector<int> > N vs vector<int> F[N]

Разница между двумерным вектором и массивом вектора заключается в том, что 2D-векторы могут иметь размер, в то время как массив векторов имеет размерность, фиксированную для размера массива.

Ответ 3

Под капотом вектор все еще использует массив, он специфичен для реализации, но безопасно думать, что:

vector<int>

внутренне создает int []. Какие векторы дают вам то, что он абстрагирует от вас ту часть, где, если вы хотите изменить размер, вам не нужно перераспределять вручную и т.д., Это делает это для вас (и, конечно же, намного больше). Когда вы выполните: vector<vector<int>>, вы создадите вектор векторов, что означает двумерную матрицу. Вы можете вложить его столько, сколько хотите. Вектор принимает тип T и выделяет массив этого типа. поэтому, если вы передадите вектор типа T, он эффективно выполнит то, что вы сделали в своей первой строке, массив vector<int>. Надеюсь, что это имеет смысл

Ответ 4

Короткий ответ:
Это массив vector <int> s.

Длинный ответ:
При чтении объявления, например

vector<int> adj[N];

Компилятор использует метод, известный как "спиральное" или "правило по часовой стрелке", чтобы интерпретировать его. Идея спирального правила заключается в том, что вы начинаете с имени переменной и перемещаетесь наружу по часовой стрелке, чтобы выяснить, какой тип переменной она есть. Например:

char* str [10];

Можно интерпретировать следующим образом:

        ____
       |    |
char* str [10];
  |_________|

Создание str массива из 10 char* s.

Следовательно, vector<int> adj[N]; представляет собой массив векторов, а не вектор массивов

Практика делает совершенным:

1: Что означает int * foo [ ];?

Ответ:

"foo" - это массив указателей на целые числа

2: Что означает int * (*foo [ ] )();?

Ответ:

"foo" - это массив указателей на функции, возвращающие указатели на целые числа

3: Что означает int * (*(*foo [ ] )())();?

Ответ:

"foo" - это массив указателей на функции, возвращающие указатели на функции, возвращающие указатели на целые числа.