core/MappedList.h
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef _AVS_MAPPED_LIST | ||
| 2 | #define _AVS_MAPPED_LIST | ||
| 3 | |||
| 4 | #include <list> | ||
| 5 | #include <unordered_map> | ||
| 6 | |||
| 7 | template <typename T> | ||
| 8 | class mapped_list | ||
| 9 | { | ||
| 10 | private: | ||
| 11 | |||
| 12 | typedef std::list<T> ListType; | ||
| 13 | std::list<T> list; | ||
| 14 | std::unordered_map<T, typename ListType::iterator> map; | ||
| 15 | |||
| 16 | public: | ||
| 17 | |||
| 18 | typedef typename ListType::iterator iterator; | ||
| 19 | |||
| 20 | ✗ | void push_back(const T& elem) | |
| 21 | { | ||
| 22 | ✗ | iterator it = list.insert(list.end(), elem); | |
| 23 | ✗ | map.emplace(elem, it); | |
| 24 | ✗ | } | |
| 25 | |||
| 26 | void push_front(const T& elem) | ||
| 27 | { | ||
| 28 | iterator it = list.insert(list.begin(), elem); | ||
| 29 | map.emplace(elem, it); | ||
| 30 | } | ||
| 31 | |||
| 32 | bool empty() const | ||
| 33 | { | ||
| 34 | return list.empty(); | ||
| 35 | } | ||
| 36 | |||
| 37 | size_t size() const | ||
| 38 | { | ||
| 39 | return list.size(); | ||
| 40 | } | ||
| 41 | |||
| 42 | ✗ | void remove(const T& elem) | |
| 43 | { | ||
| 44 | ✗ | auto map_it = map.find(elem); | |
| 45 | ✗ | assert(map_it != map.end()); | |
| 46 | |||
| 47 | ✗ | iterator list_it = map_it->second; | |
| 48 | ✗ | map.erase(map_it); | |
| 49 | ✗ | list.erase(list_it); | |
| 50 | ✗ | } | |
| 51 | |||
| 52 | ✗ | void move_to_back(const T& elem) | |
| 53 | { | ||
| 54 | ✗ | auto map_it = map.find(elem); | |
| 55 | ✗ | assert(map_it != map.end()); | |
| 56 | |||
| 57 | ✗ | iterator list_it = map_it->second; | |
| 58 | ✗ | list.splice(list.end(), list, list_it); | |
| 59 | ✗ | } | |
| 60 | |||
| 61 | ✗ | iterator begin() | |
| 62 | { | ||
| 63 | ✗ | return list.begin(); | |
| 64 | } | ||
| 65 | |||
| 66 | ✗ | iterator end() | |
| 67 | { | ||
| 68 | ✗ | return list.end(); | |
| 69 | } | ||
| 70 | }; | ||
| 71 | |||
| 72 | #endif // _AVS_MAPPED_LIST | ||
| 73 |