Advertisement
JadonChan

student_list.h

Mar 21st, 2025
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. //
  2. // Created by Jadon Chan on 2025/3/21.
  3. //
  4.  
  5. #ifndef STUDENT_SCORE_SCORE_LIST_H
  6. #define STUDENT_SCORE_SCORE_LIST_H
  7.  
  8. #include <string>
  9. #include <unordered_map>
  10. #include <list>
  11.  
  12. #define MAX_SCORE 1000
  13. #define SENTINEL_NAME "0SENTINEL0"
  14.  
  15. struct Item {
  16.     std::string name;
  17.     int score;
  18. };
  19.  
  20. // It's users' responsibility to ensure that score is in [0, MAX_SCORE]
  21. // It's users' responsibility to ensure only remove/update names that already exist
  22. // It's users' responsibility to ensure only check score/rank of names that already exist
  23. class score_list {
  24. public:
  25.     score_list(){
  26.         // sentinel node
  27.         item_list.emplace_back(SENTINEL_NAME, MAX_SCORE + 1); // Use emplace_back to avoid an additional move
  28.         rank_map[SENTINEL_NAME] = 0;
  29.     }
  30.     int getRank(const std::string& name) { // O(1)
  31.         // pass by reference: No cost is needed for copy/move.
  32.         // pass by value: Take a copy or a move
  33.         return rank_map[name];
  34.     }
  35.     int getScore(const std::string& name) { // O(1)
  36.         // pass by reference: No cost is needed for copy/move.
  37.         // pass by value: Take a copy or a move
  38.         return score_map[name];
  39.     }
  40.     void insert(std::string name, int score) { // O(n)
  41.         // pass by reference: lvalue will take a copy, rvalue will take a move. But two functions are needed.
  42.         // pass by value: lvalue will take a copy and a move, rvalue will take two moves. But only need one function. Because string is cheap to move, so I choose to pass by value.
  43.         auto it = item_list.begin();
  44.         while (it->score < score) {
  45.             rank_map[it->name]++;
  46.             ++it;
  47.         }
  48.         while (it->score == score) ++it;
  49.         rank_map[name] = rank_map[it->name] + 1;
  50.         score_map[name] = score;
  51.         item_list.emplace(it, std::move(name), score); // Use emplace to avoid an additional move
  52.     }
  53.     void remove(const std::string& name) { // O(n)
  54.         // pass by reference: no copy/move is needed.
  55.         int score = score_map[name];
  56.         auto it = item_list.begin();
  57.         while (it->score < score) {
  58.             rank_map[it->name]--;
  59.             ++it;
  60.         }
  61.         while (it->name != name) ++it;
  62.         rank_map.erase(name);
  63.         score_map.erase(name);
  64.         item_list.erase(it);
  65.     }
  66.     void update(std::string name, int score) { // O(n)
  67.         // pass by reference: lvalue will have a copy, rvalue has no copy, but two functions are needed.
  68.         // pass by value: lvalue will have a copy, rvalue has no copy, so I choose to pass by value.
  69.         remove(name);
  70.         insert(std::move(name), score);
  71.     }
  72. private:
  73.     std::list<Item> item_list;
  74.     std::unordered_map<std::string, int> rank_map;
  75.     std::unordered_map<std::string, int> score_map;
  76. };
  77.  
  78. #endif //STUDENT_SCORE_SCORE_LIST_H
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement