How are we accessing this 1D vector as a 2D one

Question

I was looking at the code for Bucket sort:

void bucketSort(float arr[], int n) 
{ 
    // 1) Create n empty buckets 
    vector<float> b[n]; 

    // 2) Put array elements in different buckets 
    for (int i=0; i<n; i++) 
    { 
    int bi = n*arr[i]; // Index in bucket 
    b[bi].push_back(arr[i]); 
    } 

    // 3) Sort individual buckets 
    for (int i=0; i<n; i++) 
    sort(b[i].begin(), b[i].end()); 

    // 4) Concatenate all buckets into arr[] 
    int index = 0; 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < b[i].size(); j++) 
        arr[index++] = b[i][j]; 
}

How does b[n] which is initialised as a 1D vector here:

vector<float> b[n];

get accessed as a 2D array over here in the concatenate function:

arr[index++] = b[i][j];

It's a 1D array of 1D vectors. Add them together and you get... — Weak to Enuma Elish, Aug 13 '19 at 22:19

score 3 · Accepted Answer · answered Aug 13 '19 at 22:20

How does b[n] which is initialised as a 1D vector here:
vector<float> b[n];

This does not initialize a 1D vector.

Instead, it declares a 1D array of vector<float>s.

This means that b[i][j] is accessing the i-th element in the array of vectors, and then in that one is accessing its j-th element.

Blastfurnace · Answer 2 · 2019-08-13T22:30:24.670

3

vector<float> b[n]; is not a 1D vector. It's an array of vectors. It's also a variable-length array and not valid C++ (it's a C extension provided by some compilers).

If you want a 2D vector of vectors the definition would be:

vector<vector<float>> b(n);

Note the type vector<vector<float>> and the parentheses instead of square brackets used to initialize the size of the outer vector when it's constructed.

edited Aug 13 '19 at 22:30

answered Aug 13 '19 at 22:23

Blastfurnace

18,411
56
55
70

score -2 · Answer 3 · answered Aug 13 '19 at 22:20

-2

vector<float> b[n]; creates an std::array of std::vector<float>, so it is an array of n vectors. This example might help:

std::vector<float> b[2];
float i = 1;
std::vector<float> first_vector = b[0];
first_vector.push_back(i);

answered Aug 13 '19 at 22:20

Alexandre Senges

1,474
1
13
22

3

It's a plain old array not a [std::array](https://en.cppreference.com/w/cpp/container/array), that's a container from the standard library. – Blastfurnace Aug 13 '19 at 22:28
1

Correction: There is no `std::array` involved. `vector b[n];` is an ordinary (but non-Standard) Variable Length Array of `vector`s. A note: `std::vector first_vector = b[0];` makes a copy of `b[0]` so `first_vector.push_back(i);` does absolutely nothing to `b[0]` . – user4581301 Aug 13 '19 at 22:29

How are we accessing this 1D vector as a 2D one

3 Answers3