Problem with bin sort

  //element of chain.     
    struct studentRecord 
            {
           int score;
           string* name;

           int operator !=(studentRecord x) const
              {return (score != x.score);}
        };


    // binsort,  theChain is a single linked list of students and its element is student Record

         void binSort(chain<studentRecord>& theChain, int range)
            {// Sort by score.

               // initialize the bins
       开发者_StackOverflow中文版        chain<studentRecord> *bin;
               bin = new chain<studentRecord> [range + 1];

               // distribute student records from theChain to bins
               int numberOfElements = theChain.size();
               for (int i = 1; i <= numberOfElements; i++)
               {
                  studentRecord x = theChain.get(0);
                  theChain.erase(0);
                  bin[x.score].insert(0,x);
               }

               // collect elements from bins
               for (int j = range; j >= 0; j--)
                  while (!bin[j].empty())
                  {
                     studentRecord x = bin[j].get(0);
                     bin[j].erase(0);  ////////// here
                     theChain.insert(0,x);
                  }

               delete [] bin;
            }

chain<studentRecord> is a single linked list; In the bin sort, bin is a pointer to a bin[arrange +1] whose elements are chain<studentRecord> . The code bin[j].erase(i) will delete the node i. bin[j].get(i) will get the element (i.e. studentRecord) of node i. In the code, while (!bin[j].empty()) is used to empty the chain, but bin[j] cannot be empty because it is an element array, is that right?

Thanks.

---

Yes, the bin indeed can be empty. There's a subtle but important difference between the bin being empty and the bin existing. You are correct that the bin is a member of the array, and so there exists a bin in position i for any i that's in bounds in the array. However, that bin doesn't necessarily have to have anything in it; it could have nothing in it at all if none of the elements in the input list happen to fall into that bin.

There's a good physical analogy to this problem if you have a row of glasses set out on a table and start filling some of them with water. All the glasses in a row exist and are well-defined, but they don't all have to be empty, especially if you start pouring them out (as you're doing in this bin sort example above).