課程名稱：資料結構 CS203 A
授課教師：林基成
發放時間：2020-09-16
截止時間：2020-09-22

題目說明

完成 Unordered_set 的部分函式。

解題思路

下面是依照我寫的順序來排序的。

  1. void assignGrow(const size_type cells, const value_type val)

    • 函式功能： 將動態陣列的大小擴張為 cells，並且將值都設為 val。
    • 參考作法： 先判斷原本的動態陣列是否存在，若存在則先刪除，接著重新宣告一個 cells 大小的動態陣列，再將值一一放入，最後將 pointer 的位置更新即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      // set the elements stored here to cells copies of val
      void assignGrow( const size_type cells, const value_type val )
      {
          if (myData.myFirst) delete[] myData.myFirst;
          myData.myLast = myData.myEnd = myData.myFirst = new value_type[cells];
          do *myData.myLast++ = val; while (++myData.myEnd != myData.myFirst + cells);
      }

  2. size_type bucket_size(size_type n) const

    • 函式功能： 回傳第 n 個 bucket 的元素個數。
    • 參考作法： 先找出第 n 個 bucket 的頭部的 iterator，即為 *(myVec.myData.myFirst + n * 2)，因為 myVec 會儲存每個 bucket 的頭部及尾端的 iterator，所以 n 需要乘以 2。接著使用迴圈直到 iter 到了第 n 個 bucket 的尾端，最後判斷 iter 是否等於 myList.end() 若是相等代表這個 bucket 是空的，否則回傳 ++tmp，因為迴圈到了尾巴就退出了，會少算一個元素。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      // Returns the number of elements in bucket n.
      size_type bucket_size( size_type n ) const
      {
          auto head = &myVec.myData.myFirst[n * 2];
          return *head == myList.end() ? 0 : std::distance(*head, *(head + 1)) + 1;
          //int cnt{};
          //auto iter = myVec.myData.myFirst[n * 2];
          //while (iter != myVec.myData.myFirst[n * 2 + 1]) ++cnt, ++iter;
          //return iter == myList.end() ? 0 : ++cnt;
          // also be fine
      }

  3. iterator find(const key_type &keyVal)

    • 函式功能： 若是 keyVal 存在則回傳該值位於的 node 的 iterator，否則回傳 myList.end()。
    • 參考作法： 先找出 keyVal 的 hashCode，代表位於第幾個 bucket，接著遍歷這個 bucket 直到尾端或是找到值與 keyVal 相同的 node，最後判斷 iter 是否與 myList.end() 相等，若相等代表這個 bucket 是空的，則值也不會存在。否則判斷 *iter 是否與 keyVal 相等，若相等回傳 iter，否則回傳 myList.end()。這樣寫的同時確保了 bucket 的尾巴也會判斷到。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      // Searches the unordered_set for an element with keyVal as value and
      // returns an iterator to it if found, otherwise it returns myList.end()
      iterator find( const key_type &keyVal )
      {
          int hash = bucket(keyVal);
          auto iter = myVec.myData.myFirst[hash * 2];
          while (iter != myVec.myData.myFirst[hash * 2 + 1] && *iter != keyVal) ++iter;
          return iter == myList.end() ? myList.end() : *iter == keyVal ? iter : myList.end();
      }

  4. void putIn(const value_type &val)

    • 函式功能： 將 val 放入 myList，同時位於 myVec 的 iterator 也需更新。
    • 參考作法： 先找出 val 應該放入的 bucket，接著將 val 放入 bucket 的最前面，最後判斷 *head 是否等於 myList.end()，若相等代表這個 bucket 還是空的，此時值會被放在 myList 的尾端，將頭部跟尾端的 iterator 往前移恰好會指到該值。否則將頭部的 iterator 往前移即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      // put a new element in the unordered_set when myVec is large enough
      void putIn( const value_type &val )
      {
          auto head = &myVec.myData.myFirst[bucket(val) * 2];
          myList.insert(*head, val);
          if ((*head)-- == myList.end())--* ++head;
          //*head == myList.end() ? -- * head, --* ++head : --* head; // also be fine
      }

  5. void insert(const value_type &val)

    • 函式功能： 將 val 放入 unordered_set，若是大小超過需要擴張大小 ( 當元素個數等於 maxidx 時)。
    • 參考作法： 先判斷 val 是否已經存在，若存在則直接回傳避免重複插入。接著判斷大小是否已經超過，若超過則需要更新 maxidx ( 初始值為 8，前兩次擴張都乘以 8，後面擴張則都乘以 2 ) 及 mask ( 永遠為 maxidx - 1)，接著將 myList 備份並清除 myList，接著擴張 myVec ( 呼叫 assignGrow() )，再遍歷剛剛備份的 myList 將原本存在的 key 放入新的 List ( 呼叫 putIn() )，最後將 val 放入即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      // Inserts a new element in the unordered_set.
      // The element is inserted only if it is not equivalent to any other element
      // already in the container ( elements in an unordered_set have unique values ).
      // This effectively increases the container size by one.
      void insert( const value_type &val )
      {
          if (find(val) != myList.end()) return;

          if (size() == maxidx && (mask = (maxidx *= maxidx < 512 ? 8 : 2) - 1))
          {
              auto tmp = myList;
              myList.clear();
              myVec.assignGrow(maxidx * 2, myList.end());
              for (const auto& key : tmp) putIn(key);
          }

          putIn(val);
      }

  6. void erase(const key_type &keyVal)

    • 函式功能： 將 keyVal 從 unordered_set 中刪除。
    • 參考作法： 先判斷 keyVal 是否存在，接著取得 keyVal 位於的 node 的 iterator。判斷此 bucket 的大小是否為 1，若為 1 代表刪除後此 bucket 會為空，需要將 myVec 中的 iterator 更新 ( 將頭部跟尾端的 iterator 都設為 myList.end() 即可 )。否則判斷這個 node 是否在 bucket 的頭部或尾端，若在頭部則頭部的 itertor 需要往後移，若在尾端則尾端的 iterator 需要往前移。最後從 myList 中刪除即可。
    • 參考解法：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      // Removes from the unordered_set a single element.
      // This effectively reduces the container size by one.
      void erase( const key_type &keyVal )
      {
          auto iter = find(keyVal);
          if (iter == myList.end()) return;

          auto head = &myVec.myData.myFirst[bucket(keyVal) * 2];
          if (*head == *(head + 1)) *head = *head++ = myList.end();
          else if (*head == iter || *(head + 1) == iter) *head == iter ? ++ * head : -- * ++head;

          myList.erase(iter);
      }