I was looking at the bucket sort problem at geeks for geeks, in which they were storing multiple elements at the same index of vector.

My question is how is this possible that we can store multiple elements at the same index in vector.

The code is here

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

CodePudding user response：

vector<float> b[n] => it's a 2D vector. So when you're writing b[bi].push_back(), it means you're inserting an element at bi th vector, or you can say bith row.

In bucket sort, there can be multiple buckets. So this 2D vector represents all those buckets. That means, b[i] represents i th bucket.

So the answer to your question is, they're not storing multiple elements at the same index in vector. They're inserting the element arr[i] into bucket[n*array[i]], which itself is a vector.

CodePudding user response：

To answer your question right off the bat, they are NOT storing multiple elements in a single index of the vector. Here is what is happening:
vector<float> tells the compiler that each element of the vector is strictly a single float value. However, the b[n] part that follows is the notation you use to declare an array.
Ultimately, you end up with vector<float> b[n] which is basically an array but each element of the array is a vector. The vector itself stores only float values as you've instructed the compiler.
b[bi].push_back(arr[i]) is translated into:
To the vector stored in the biᵗʰ index of my array named b, append the float value which is arr[i]