Dynamic initialization of 2 dimensional array of lists in C++

Question

I need to init a 2-dim array of forward_list after I read its sizes from input.

class Foo{

    forward_list<int> * koo;
    int A, B;

    void boo(){
        scanf("%d",&A);
        scanf("%d",&B);

        koo = new forward_list<int>[A][B];

        koo[0][0] = 1;
    }

};

Compiler:

cannot convert ‘std::forward_list<int> (*)[1]’ to ‘std::forward_list<int>*’ in assignment adjList = new forward_list<int>[A][A];

CLion IDE: Subscribed value is not an array (at koo[0])

I don't do much C++ so I don't quite know what's wrong. How can I do this right? I need to access all forward_list in O(1), and would, therefore, prefer arrays or generally something fast.

Btw: not sure if this is called dynamic initialization, let me know if I should change the title.

Thanks.

Why do you need a 2d array of forward lists? That is a pretty strange "container". What are you doing with it? — NathanOliver, Nov 09 '18 at 17:40
Why don't you use [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead? I mean, instead of both your list and your pointer `koo`. — Some programmer dude, Nov 09 '18 at 17:40
`std::vector>` seems to be what you are looking for. But you probably *want* `std::vector>` if you wnt speed. Linked lists are horribly slow on modern processors due to all the pointer chasing they need to do. A plain `vector` usually out performs `list` in all but trivial cases. — Jesper Juhl, Nov 09 '18 at 17:41
It's a graph problem, Nathan. I know the number of graphs and they all have the same number of nodes. I need to represent them in some structure. I chose a list of neighbours - specifically the forward_list is a list of adjacent nodes. — Rehalus, Nov 09 '18 at 17:43
Every time I have to read from the forward_list I have to read all of the ints in order. And that is the only operation I perform of that structure. Except for populating it, but thats just push_forward a couple of times. If vector would be better I would use it, but is it in this case? — Rehalus, Nov 09 '18 at 17:47
@ChristopherParus If you want a dynamic 2d array of anything, the first thing that should come to your mind is `std::vector>` where `whatever` is the type you want to have the 2d array on. Anything else is up for discussion later. — PaulMcKenzie, Nov 09 '18 at 17:49
Ok, people, I get it. Use vectors. vector::push_back is O(1) and array insert is also O(1) and in this particular case I actually don't need to use vector::insert. So I could use vector. But say I need to use insert - so for vector O(n) and for array still constant. I know this doesn't seem that importatnt but the point of my program is speed and optimalisation. So is it possible to do somethink like what I described. With forward_list[ ][ ] of vector[ ][ ] using a 2 dim array that is initialised using program input. — Rehalus, Nov 09 '18 at 18:06
Algorithmic complexity (big O) is not all that matters. Benchmark different solutions. Even though insertion into a list is theoretically faster, in real life a vector is often faster since moving a linear chunk of memory is often faster than chasing pointers (that are unlikely to be in the CPUs cache) to get to the insertion point in a list. — Jesper Juhl, Nov 09 '18 at 18:13
A linked lists's ability to add and remove quickly is nice, but the benefits are quickly lost if have to iterate the list. With a `vector`, the CPU knows exactly where to find the next element and has probably already loaded it and a good number of elements after it by the time you need it. With a linked list, you need to go looking for it (pointer chasing) and since the elements are likely nowhere near one another in storage, you probably can't block-read several at once. This almost always costs more than the savings from quick insert and removal. — user4581301, Nov 09 '18 at 18:47

score 0 · Answer 1 · answered Nov 09 '18 at 19:10

A forward_list is incapable of reaching your performance requirement: "I need to access all forward_list in O(1)" you can see that in a comparision here: https://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays You can see that Indexing for a forward_list and other linked list variants is O(n).

The simplest container type that does provide the O(1) indexing you're looking for is a vector or another of the dynamic array variants. I believe your current needs could be satisfied by doing something like:

vector<vector<int>> koo(A, vector<int>(B));

It should be mentioned that while this will satisfy your performance requirements, a vector of vectors isn't a great solution; but you can look at it as a good stopgap solution.

Dynamic initialization of 2 dimensional array of lists in C++

1 Answers1