Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Created by Jadon Chan on 2025/3/21.
- //
- #ifndef STUDENT_SCORE_SCORE_LIST_H
- #define STUDENT_SCORE_SCORE_LIST_H
- #include <string>
- #include <unordered_map>
- #include <list>
- #define MAX_SCORE 1000
- #define SENTINEL_NAME "0SENTINEL0"
- struct Item {
- std::string name;
- int score;
- };
- // It's users' responsibility to ensure that score is in [0, MAX_SCORE]
- // It's users' responsibility to ensure only remove/update names that already exist
- // It's users' responsibility to ensure only check score/rank of names that already exist
- class score_list {
- public:
- score_list(){
- // sentinel node
- item_list.emplace_back(SENTINEL_NAME, MAX_SCORE + 1); // Use emplace_back to avoid an additional move
- rank_map[SENTINEL_NAME] = 0;
- }
- int getRank(const std::string& name) { // O(1)
- // pass by reference: No cost is needed for copy/move.
- // pass by value: Take a copy or a move
- return rank_map[name];
- }
- int getScore(const std::string& name) { // O(1)
- // pass by reference: No cost is needed for copy/move.
- // pass by value: Take a copy or a move
- return score_map[name];
- }
- void insert(std::string name, int score) { // O(n)
- // pass by reference: lvalue will take a copy, rvalue will take a move. But two functions are needed.
- // 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.
- auto it = item_list.begin();
- while (it->score < score) {
- rank_map[it->name]++;
- ++it;
- }
- while (it->score == score) ++it;
- rank_map[name] = rank_map[it->name] + 1;
- score_map[name] = score;
- item_list.emplace(it, std::move(name), score); // Use emplace to avoid an additional move
- }
- void remove(const std::string& name) { // O(n)
- // pass by reference: no copy/move is needed.
- int score = score_map[name];
- auto it = item_list.begin();
- while (it->score < score) {
- rank_map[it->name]--;
- ++it;
- }
- while (it->name != name) ++it;
- rank_map.erase(name);
- score_map.erase(name);
- item_list.erase(it);
- }
- void update(std::string name, int score) { // O(n)
- // pass by reference: lvalue will have a copy, rvalue has no copy, but two functions are needed.
- // pass by value: lvalue will have a copy, rvalue has no copy, so I choose to pass by value.
- remove(name);
- insert(std::move(name), score);
- }
- private:
- std::list<Item> item_list;
- std::unordered_map<std::string, int> rank_map;
- std::unordered_map<std::string, int> score_map;
- };
- #endif //STUDENT_SCORE_SCORE_LIST_H
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement