CODEWITHSUNDEEP
c++vectorgraph
John
John

Reputation: 468

C++ - How to create a dynamic vector

I am following this example to make an adjacency list. However it seems like the vector size cannot be dynamic.

Visual studio throws an error

expression did not evaluate to a constant

on this line

vector<int> adj[V];

The strange thing is that the same exact code works correctly on codeblocks IDE.

I've tried replacing the above line with vector<int> adj; but then I cannot send the vector as a parameter to addEdge(adj, 0, 1); as it throws another error about pointers which I also don't know how to correct.

What could I do to dynamically create my vector?

Upvotes: 0

Views: 2388

Answers (3)

eerorika
eerorika

Reputation: 238461

C++ - How to create a dynamic vector

You don't need to do that for this example. But if you did need it, you could use std::make_unique.

The linked example program is ill-formed. I recommend to not try to learn from that. The issue that you encountered is that they use a non-const size for an array. But the size of an array must be compile time constant in C++. Simple fix is to declare the variable type as const:

const int V = 5;

I've tried replacing the above line with vector<int> adj;

You can't just replace an array of vectors with a single vector and expect the program to work without making other changes.

I need the size to be dynamic as it will only be known at compile time.

Assuming you meant to say that the size will only be known at runtime, the solution is to use a vector of vectors.

Upvotes: 1

Kerek
Kerek

Reputation: 1110

As written by eerorika, the example code isn't a good one, and you should avoid using raw arrays like that. An array in C/C++ is of static size, each vector in this array is dynamic, but the entire array is not!

There are two approaches for such a question. Either use adjacency lists (which is more common):

#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;
};

or use double vector to represent the edges matrix:

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

But it isn't a real matrix, and you cannot check if (u, v) is in the graph in O(1), which misses the point of having adjacency matrix. Assuming you know the size of Graph on compile time, you should write something like:

#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
    }
}

Then you can use AdjacencyMatrix<5> instead of what they were using on that example, in O(1) time, and although it has static size, it does work as intended.

Upvotes: 1

Kuba hasn&#39;t forgotten Monica
Kuba hasn&#39;t forgotten Monica

Reputation: 98525

There’s no need to use C-style arrays in modern C++. Their equivalent is std::array, taking the size as a template parameter. Obviously that size can’t be a runtime variable: template parameters can be types or constant expressions. The compiler error reflects this: std::array is a zero cost wrapper over an internal, raw “C” array.

If the array is always small, you may wish to use a fixed-maximum-size array, such as provided by boost. You get all performance benefits of fixed size arrays and can still store down to zero items in it.

There are other solutions:

  1. If all vectors have the same size, make a wrapper that takes two indices, and uses N*i1+i2 as the index to an underlying std::vector.

  2. If the vectors have different sizes, use a vector of vectors: std::vector>. If there are lots of vectors and you often add and remove them, you may look into using a std::list of vectors.

Upvotes: 0

Related Questions