C ++ - Как создать динамический вектор c

Question

Я следую этому примеру , чтобы составить список смежности. Однако кажется, что размер вектора не может быть динамическим c.

Visual Studio выдает ошибку

выражение не оценивается как константа

в этой строке

vector<int> adj[V];

Странно то, что тот же самый точный код работает правильно в IDE кодоблоков.

Я попытался заменить вышеуказанную строку на vector<int> adj;, но затем я не могу отправить вектор как параметр для addEdge(adj, 0, 1);, поскольку он выдает еще одну ошибку об указателях, которую я также не знаю, как исправить.

Что я могу сделать, чтобы динамически создать мой вектор?

Answer 1

Как написано eerorika , пример кода не очень хороший, и вам следует избегать использования таких сырых массивов. Массив в C / C ++ имеет размер c, каждый вектор в этом массиве является динамическим c, но не весь массив!

Существует два подхода к такому вопросу. Либо используйте списки смежности (что более распространено):

#include <vector>
#include <stdint.h>

class Vertix
{
public:
    Vertix(uint64_t id_) : id(id_) {}
    uint64_t get_id() const { return id; }
    void add_adj_vertix(uint64_t id) { adj_vertices.push_back(id); }
    const std::vector<uint64_t>& get_adj_vertices() const { return adj_vertices; }
private:
    uint64_t id;
    std::vector<uint64_t> adj_vertices;
};

class Graph
{
public:
    void add_vertix(uint64_t id) 
    { 
        vertices[id] = Vertix(id); 
    }
    void add_edge(uint64_t v_id, uint64_t u_id)
    {
        edges.emplace_back(u_id, v_id);

        vertices[u_id].add_adj_vertix(v_id);
    }

private:
    std::vector<Vertix> vertices;
    std::vector<std::pair<uint64_t, uint64_t>> edges;
};

или используйте двойной вектор для представления матрицы ребер:

std::vector<std::vector<uint64_t>> edges;

Но это не настоящая матрица, и вы не может проверить, есть ли (u, v) в графе в O (1), который пропускает точку наличия матрицы смежности. Предполагая, что вы знаете размер Graph во время компиляции, вы должны написать что-то вроде:

#include <array>
#include <stdint.h>

template <size_t V>
using AdjacencyMatrix = std::array<std::array<bool, V>, V>;

template <size_t V>
void add_edge(AdjacencyMatrix<V>& adj_matrix, uint64_t u, uint64_t v)
{
    if (u < V && v < V)
    {
        adj_matrix[u][v] = true;
    }
    else
    {
        // error handling
    }
}

Тогда вы можете использовать AdjacencyMatrix<5> вместо того, что они использовали в этом примере, во время O (1), и хотя он имеет размер stati c, он работает как задумано.

Answer 2

C ++ - Как создать динамический c вектор

Вам не нужно делать это в этом примере. Но если вам это нужно, вы можете использовать std::make_unique.

Программа-пример связана с ошибками. Я рекомендую не пытаться учиться на этом. Проблема, с которой вы столкнулись, заключается в том, что они используют неконстантный размер для массива. Но размер массива должен быть постоянным времени компиляции в C ++. Простое решение - объявить тип переменной как const:

const int V = 5;

Я пытался заменить вышеуказанную строку на vector<int> adj;

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

---

Мне нужно, чтобы размер был Dynami c, поскольку он будет известен только при время компиляции.

Предполагая, что вы хотели сказать, что размер будет известен только во время выполнения, решение состоит в том, чтобы использовать вектор векторов.

Answer 3

Нет необходимости использовать массивы C в современном C ++. Их эквивалентом является std :: array, принимающий размер в качестве параметра шаблона. Очевидно, что размер не может быть переменной времени выполнения: параметры шаблона могут быть типами или константными выражениями. Ошибка компилятора отражает это: std :: array является оболочкой с нулевой стоимостью над внутренним необработанным массивом «C».

Если массив всегда маленький, вы можете использовать sh для использования фиксированного максимума массив, например, предоставленный boost. Вы получаете все преимущества производительности массивов фиксированного размера и можете хранить в нем до нуля элементов.

Существуют и другие решения:

1. Если все векторы имеют одинаковый размер, создайте оболочку, которая принимает два индекса и использует N * i1 + i2 в качестве индекса для базовый std :: vector.

2. Если векторы имеют разные размеры, используйте вектор векторов: std :: vector>. Если имеется много векторов, и вы часто добавляете и удаляете их, вы можете использовать список векторов std ::.