I'm implementing a simple radix sort for a school report and using a std::deque in my implementation of the intermediate bucket sort. The problem is that when I perform a pop_front(), the front element is not removed. I tired to work around this with clear() and empty(itr) operation, but the data in the queue is not removed in both cases. I've verified that the data is not being removed from the queue in all 3 cases with GDB. This messed up the entire sort because the elements from each digit sort end up in queue's, then into the sorted list.
The way I've gotten around this is to reallocate all ten queue's each iteration of the digitCount for loop. But that adds overhead that should not have to be there.
The Integer class is just a wrapper over a list of digits in each number and numerical representation of that number.
What am I doing wrong that's causing the elements to not pop off of the queue?
void SerialRadix::radixSort(){
//todo: add support for numbers of varying lengths
std::vector<std::deque<Integer> > buckets;
//populate m_buckets with queues
for (int j = 0; j < 10; j++){
std::deque<Integer> bucket;
buckets.push_back(bucket);
}
const int digitCount = m_integers[0].getDigitCount();
int digitValue; //used in loop
// look at all digits in each number. 'i' is the digit location. digits in ascending order, loop in reverse
for (int i = digitCount - 1; i >= 0; i--){
// loop over all numbers in list
for (Integer numToSort : m_integers){
digitValue = numToSort.m_digits[i];
//place number in bucket based on digit value
buckets[digitValue].push_back(numToSort);
}
int index = 0;
// empty buckets back into sorted list
for (std::deque<Integer> bucket : buckets){
while (!bucket.empty()){
m_integers[index] = bucket.front();
bucket.pop_front(); //!problem is here! not removing from queue
// if this is last digit to sort, place into sorted list when pulled from bucket
if (!i){
m_sortedList[index] = m_integers[index].getNumber();
}
index++;
}
}
}
}
for (std::deque<Integer> bucket : buckets){
Your bucket of type std::deque<Integer> is being passed by value in the for loop.
for (std::deque<Integer>& bucket : buckets){
Just pass a reference to the bucket deque instead.
When we pass an object by value, a copy of the object is created and any changes made to that copy will not affect the original object. To actually change or affect the original object we pass an object by reference.
In your code, object of type std::deque<Integer> is being passed by value in the for loop. It creates a copy in your bucket variable, and any changes made to bucket will only reflect in the copy only not the original in your buckets vector.
Using the & operator you can pass the std::deque<Integer> object by reference. This will create a reference to your original deque in the buckets vector and any changes made to bucket will be reflected in the original deque.