Thread: vector shenanigans

Hi.

I had to implement a bucket sort algorithm for my class and am running into trouble with vectors.
I've already implemented the program (so I'm not asking for others to do it for me) and have tracked down the bug to my use of the STL vector container.

Code:

Stuct Supplier{...};
...
vector<Supplier> * bucketSort(vector<Supplier> * v, int n, int d){
       vector< vector< Supplier > > buckets (N_BUCKETS vector< Supplier > (N_DATA));
...
       Supplier tmpS = v->at(i);
       buckets.at(str.at(d)).push_back(tmpS);

...
}

Running the program gives me

Code:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check

Program received signal SIGABRT, Aborted.

and asking "where" in gdb gives

Code:

Program received signal SIGABRT, Aborted.
0x9003d66c in kill ()
(gdb) where
#0  0x9003d66c in kill ()
#1  0x9010e8cf in raise ()
#2  0x9010d422 in abort ()
#3  0x90b4539c in __gnu_cxx::__verbose_terminate_handler ()
#4  0x90b43602 in __gxx_personality_v0 ()
#5  0x90b43640 in std::terminate ()
#6  0x90b43754 in __cxa_throw ()
#7  0x90b05483 in std::__throw_out_of_range ()
#8  0x000033a7 in std::vector<std::vector<Supplier, std::allocator<Supplier> >, std::allocator<std::vector<Supplier, std::allocator<Supplier> > > >::_M_range_check (this=0xbffff528, __n=57) at /usr/include/c++/4.0.0/bits/stl_vector.h:518
#9  0x000036d0 in std::vector<std::vector<Supplier, std::allocator<Supplier> >, std::allocator<std::vector<Supplier, std::allocator<Supplier> > > >::at (this=0xbffff528, __n=57) at /usr/include/c++/4.0.0/bits/stl_vector.h:536
#10 0x000024db in bucketSort (v=0xbffff810, n=1000, d=3) at bucket.cpp:101
#11 0x00002969 in main (argc=1, argv=0xbffff89c ",???") at bucket.cpp:54

So it seems that I'm getting an out of bounds error on the "push_back" part of

Code:

buckets.at(str.at(d)).push_back(tmpS);

Any ideas?

FYI:
gcc version 4.0.1 (Apple Computer, Inc. build 5367)
GNU gdb 6.3.50-20050815 (Apple version gdb-573)

>> vector< vector< Supplier > > buckets (N_BUCKETS vector< Supplier > (N_DATA));
What is N_BUCKETS and what is N_DATA? Note that you're missing a comma there also, make sure that the posted code accurately reflects the code you're using.

>> buckets.at(str.at(d)).push_back(tmpS);
What is d? Is it greater than the size of str? What is str for that matter? I would think it would be a string, but you are using a value in it as the index for the buckets vector which wouldn't make sense if it was a string.

I would write that statement out to find more information about the problem:

Code:

       size_t bucket_index = str.at(d);
       std::cout << "d: " << d << ", ";
       std::cout << "bucket_index: " << bucket_index << '\n';

       vector< Supplier >& temp_vec = buckets.at(bucket_index);
       temp_vec.push_back(tmpS);

Originally Posted by Daved

>> vector< vector< Supplier > > buckets (N_BUCKETS vector< Supplier > (N_DATA));
What is N_BUCKETS and what is N_DATA?

N_BUCKETS and N_DATA are globally defined variables. They have 10 and 1000 assigned to them (respectively).

Originally Posted by Daved

>> buckets.at(str.at(d)).push_back(tmpS);
What is d? Is it greater than the size of str? What is str for that matter? I would think it would be a string, but you are using a value in it as the index for the buckets vector which wouldn't make sense if it was a string.

d is decremented from 3 to 0 and I've made sure that str.at(d) is a valid index.
As for str, this may help:

Code:

stringstream ss;
string str;
ss << v->at(i).price;
ss >> str;

Price is an integer. It's digits are used as buckets for the sorting algorithm.

I tried

Code:

std::cout << "buckets.size(): " << buckets.size() << endl;
std::cout << "buckets.at(str.at(d))size(): " << buckets.at(str.at(d)).size() << endl;

The former prints out "10" but the latter still results in an out-of-bounds error.

But when you use str.at(d) you are getting a character. A character, when used as an index to a vector, is different than the digit it represents. So if you're using ASCII and str is "1234" and d is 0, then str.at(d) will be '1' which is 49 in ASCII. That means you are trying to use buckets.at(49). I doubt that's what you want (and of course it is more than 10).

You might consider a vector of ints instead of a string to hold those digits. A simple change to get the actual int from the digit is to subtract '0', since the digits '0' - '9' are guaranteed to be in order:

Code:

buckets.at(str.at(d) - '0')

Originally Posted by Daved

A simple change to get the actual int from the digit is to subtract '0', since the digits '0' - '9' are guaranteed to be in order:

Code:

buckets.at(str.at(d) - '0')

Thanks, that worked.