C++ - How to create a dynamic vector

Question

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?

`vector> adj(V);` is the most direct solution to the problem as asked. This is a `vector` of `V` `vectors`. This will probably set off a ripple of changes through your code where you have to pass `vector>&` to functions in place of `vector*`. — user4581301, Apr 01 '20 at 23:25
`std::vector` is a dynamic vector. Your question needs clarification. Is a dynamic vector something other then an array that can be resized at runtime? — super, Apr 01 '20 at 23:53
`vector adj[V];` defines a **variable-length array** `adj` containing `V` number of elements of type `vector`. Fixed arrays *require* a constant size known at compile-time, but `V` is not a compile-time constant (`int V = 5;` is missing `const`). VLAs are [not supported by standard C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard), but may be supported as a vendor-specific compiler extension. Visual Studio does not support VLAs, but CodeBlocks does. — Remy Lebeau, Apr 02 '20 at 00:20

eerorika · Accepted Answer · 2020-04-01T23:54:05.403

1

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.

edited Apr 01 '20 at 23:54

answered Apr 01 '20 at 23:16

eerorika

232,697
12
197
326

I need the size to be dynamic as it will only be known at compile time. Could you explain how to use std::make_unique to fix my problem? About your last point, I'm aware of that, I just don't know what changes should be done. – John Apr 01 '20 at 23:29
Thank you. It seems like, based also on the other answers, it's not possible to make a dynamic vector in my case. I'll be going with the static approach then. – John Apr 02 '20 at 18:50

score 1 · Answer 2 · answered Apr 01 '20 at 23:39

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.

score 0 · Answer 3 · answered Apr 01 '20 at 23:37

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:

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.
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.

C++ - How to create a dynamic vector

3 Answers3