Проблема с сортировкой бина

Question

  //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
               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> представляет собой единый связанный список ; В сортировке bin, bin - это указатель на bin[arrange +1], элементы которого chain<studentRecord>. Код bin[j].erase(i) будет delete узлом i. bin[j].get(i) получит элемент (т.е. studentRecord) узла i. В коде while (!bin[j].empty()) используется для очистки цепочки, но bin [j] не может быть пустым, потому что это массив элементов, верно?

Спасибо.

Answer 1

Да, корзина действительно может быть пустой. Существует небольшая, но важная разница между корзиной, являющейся пустой , и корзиной , существующей . Вы правы, что bin является членом массива, и поэтому существует bin в позиции i для любого i, который находится в границах массива Однако в этом мусорном баке не обязательно должно быть что-либо; в нем вообще не может быть ничего, если ни один из элементов в списке ввода не попадет в этот контейнер.

Существует хорошая физическая аналогия с этой проблемой, если вы поставили на стол ряд стаканов и начали заполнять некоторые из них водой. Все стаканы в ряд существуют и четко определены, но они не обязательно должны быть пустыми, особенно если вы начинаете их разливать (как вы делаете в этом примере сортировки бина выше).