vector shenanigans

This is a discussion on vector shenanigans within the C++ Programming forums, part of the General Programming Boards category; Hi. I had to implement a bucket sort algorithm for my class and am running into trouble with vectors. I've ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    8

    Question 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)

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    So either d is an invalid index into container str or whatever value str.at(d) returns is an invalid index into your buckets container. Maybe print out the size of these containers before you try to use them and make sure the indexes you use are within the correct range.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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);

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Or split the line up into two parts [which of course involves adding more local variables]. This is often helpful when developing code, and most of the time, the compiler will figure out what you want to do and optimize it just the same either way - but if you need to debug it, you can look at the intermediate values.

    Edit: Must type faster, Daved beat me to it [with a piece of code to show too]

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Quote Originally Posted by Daved View Post
    >> 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).

    Quote Originally Posted by Daved View Post
    >> 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.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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')

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    Quote Originally Posted by Daved View Post
    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.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21