KingMace's blog

What is it? Global vector
By KingMace, history, 4 years ago, In English

Sorry for the stupid question, couldn't find anything on stackoverflow, cuz have no idea how to google that.

I was solving one graph problem, and met this declaration of adjacency list 49661413, I am confused, how is it possible that vector of vectors is declared using vector<int> name[], and it is not a simple vector, I don't even realize what's that. Couldn't you please explain to me what's that or give me a link to website with some info? Thanks in advance

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's just an array. Each element of that array is a vector.

It's the same as vector<vector<int>> name(N). but you use vector<int> name[N] instead, replacing vector with a normal array.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The accessing is pretty much the same, but the fundamental representation is quite different, owing mainly to the fact that a std::vector allocates memory on the heap and not the stack.

    Suppose we are not in the global scope. Then std::vector<int> a[N] is an array of $$$N$$$ vector objects stored on the stack, with the contents of each vector being stored on the heap, while std::vector<std::vector<int>> a(N) is an object with $$$O(1)$$$ memory being stored on the stack, with $$$O(N)$$$ vector objects stored on the heap (as pointers to those objects) and those objects themselves being stored on the heap. Using the first one may give an error about not being able to allocate that amount of memory on stack, while a heap usually has much more memory and hence the second one is more preferable.

    If it is declared in the global scope, then a similar thing holds, however instead of the stack, the array resides in the data segment (which gives more memory than the stack), and not in the stack, so that's why it's sometimes advised to use global variables in competitive programming, even though they're generally frowned upon (very rightfully, too) in software development.

    However, note that there is literally zero overhead for using a vector as compared to an array (provided you use std::vector::push_back reasonably to avoid multiple reallocations, possibly using std::vector::reserve), so it's always advisable to use more modern language features, and keeping your code modular to make it compact, easy to reason about and less prone to errors (for instance, forgetting to clear data structures etc). Something more on the performance of std::vector.

    → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

vector< int > name; Here we've only a vector.

vector< int >name [5]; Here we've 5 vectors. name[0] , name[1], name[2], name[3] and name[4].

Google it and learn details.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it 
int a; 
// single integer

int arr[5];
// array of integers of size 5
// we can access each integer by index arr[index] => int

vector<int> v(10);
// vector of integers of size 10
// we can access each integer by index v[index] => int

vector<int> v[10];
// array of vectors of integer of size 10
// we can access each vector by index v[index] => vector of int

vector<vector<int>> v(10);
// vector of vector of integers of size 10
// we can access each vector by index v[index] => vector of int
→ Reply