student_list.h

JadonChan

Mar 21st, 2025

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.54 KB | None | 0 0

raw download clone embed print report

//
// 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

Add Comment

Please, Sign In to add comment