Я новичок в С++ STL, и у меня возникают проблемы с пониманием представления графа.
vector<int> adj[N];
Итак, это создает массив векторного типа или создает вектор массивов? Кажется, что код BFS проходит через список значений, присутствующих в каждом экземпляре adj [i], и, следовательно, он работает как массив векторов. Синтаксис для создания вектора:
vector<int> F;
который мог бы эффективно создать одномерный вектор F.
В чем разница между
vector< vector<int> > N;
и
vector<int> F[N]
Так делает ли это (
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 в вашем случае). Этот подход может быть использован для уменьшения использования памяти, когда количество ребер невелико.
†: Если быть точным - не всегда на стеке - он может быть частью сложного объекта в куче. Кроме того, стандарт С++ не определяет никаких требований к стеку или куче, он обеспечивает только требования к длительности хранения, такие как автоматический, статический, потоковый или динамический.
vector<int> arr[N];
Он отображает массив вектора, каждый массив [i] будет иметь в нем вектор, который может проходить через многие значения. Это похоже на массив связанных списков, где головки хранятся только в ячейках [i].
vector<vector<int> > N vs vector<int> F[N]
Разница между двумерным вектором и массивом вектора заключается в том, что 2D-векторы могут иметь размер, в то время как массив векторов имеет размерность, фиксированную для размера массива.
Под капотом вектор все еще использует массив, он специфичен для реализации, но безопасно думать, что:
vector<int>
внутренне создает int [].
Какие векторы дают вам то, что он абстрагирует от вас ту часть, где, если вы хотите изменить размер, вам не нужно перераспределять вручную и т.д., Это делает это для вас (и, конечно же, намного больше).
Когда вы выполните: vector<vector<int>>, вы создадите вектор векторов, что означает двумерную матрицу. Вы можете вложить его столько, сколько хотите.
Вектор принимает тип T и выделяет массив этого типа. поэтому, если вы передадите вектор типа T, он эффективно выполнит то, что вы сделали в своей первой строке, массив vector<int>.
Надеюсь, что это имеет смысл
Короткий ответ:
Это массив 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" - это массив указателей на функции, возвращающие указатели на функции, возвращающие указатели на целые числа.