1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include <iostream>
#include <map>
#include <vector>
#include <algorithm>
class Ranker {
int counter;
std::map<int, int> omap;
std::vector<int> historique;
int offset(int rank) {
return std::count_if(historique.begin(), historique.end(), [rank](int modif) { return modif < rank; });
}
public:
Ranker() : counter(0) {}
void insert(int elem) { // O(log N)
omap[elem] = counter++;
}
int getRank(int elem) { // O(log N + length(historique))
int rank = omap[elem];
return rank - offset(rank);
}
void erase(int elem) { // O(log N)
historique.push_back(omap[elem]);
omap.erase(elem);
}
void changeValue(int old, int nov) { // O(log N)
omap[nov] = omap[old];
omap.erase(old);
}
std::map<int, int>::iterator begin() { return omap.begin(); }
std::map<int, int>::iterator end() { return omap.end(); }
};
int main(int argc, char* argv[])
{
Ranker toto;
toto.insert(28); // insertion des éléments dans l'ordre initiale
toto.insert(10);
toto.insert(43);
toto.insert(79);
toto.insert(267);
toto.insert(2);
toto.insert(8);
std::cout << toto.getRank(79) << std::endl; // affiche "3"
toto.erase(79);
toto.changeValue(267, 100);
std::cout << toto.getRank(100) << std::endl; // affiche "3"
for (auto elem : toto) std::cout << elem.first << ' '; // affiche 2 8 10 28 43 100
std::cout << std::endl;
char c;
std::cin >> c;
return 0;
} |
Partager