動的リスト
ユニークな要素を扱うリストで要素の相対位置をO(1)で取得できる
リストという名前を付けたけど、内部で使ってるデータ構造は unorderd_map
注意点: イテレータは存在しないので全要素を出力するときは下記のようにする
DS_DynamicList<long long> dlist(LLONG_MAX); for (auto x = dlist.begin_val(); x != dlist.end_val(); x = dlist.next_val(x)) std::cout << x << std::endl;
- 計算量
clear と init はO(N)、それ以外は全てO(1)
- constructor
DS_DynamicList(inf): 要素数ゼロのリストを生成(infは番兵)
DS_DynamicList(c, inf): コンテナcでリストを生成(infは番兵)
- list interface
void clear(): 全ての要素を削除
bool push_back(T x): 末尾に要素xを追加
bool push_front(T x): 先頭に要素xを追加
ll size(): 全体サイズを取得
- original interface
T back(): 末尾要素( end の1つ前)を取得(要素数ゼロならinfを返す)
T begin_val(): 先頭要素を取得(要素数ゼロならinfを返す)
it end_val(): 末尾要素( end の1つ前)を取得(要素数ゼロならinfを返す)
bool find(x): 要素xが存在するかどうか
T front(): 先頭要素を取得(要素数ゼロならinfを返す)
T next_val(x): 要素xの次の要素を取得(存在しない要素のとき引数をそのまま返し、番兵のときinfを返す)
T prev_val(x): 要素xの前の要素を取得(存在しない要素のとき引数をそのまま返し、番兵のときinfを返す)
bool change(x, y): 要素xを要素yに変更(無効な引数のとき何もせずfalseを返す)
bool erase(x): 要素xを削除(無効な引数のとき何もせずfalseを返す)
void init(c): コンテナcで初期化
bool next_insert(x, y): 要素xの次の位置にyを挿入(無効な引数のとき何もせずfalseを返す)
bool prev_insert(x, y): 要素xの前の位置にyを挿入(無効な引数のとき何もせずfalseを返す)
void swap(x, y): 要素xとyをswapする(無効な引数のとき何もせずfalseを返す)
#include <bits/stdc++.h> namespace NyaaLIB { /** * @brief 動的リスト * @note * ユニークな要素を扱うリスト * 要素の相対位置を取得できる **/ template <class T> struct DS_DynamicList { using ll = long long; ll n = 0; ll inf = LLONG_MAX; std::unordered_map<T, ll> next, prev; DS_DynamicList(ll inf) : inf(inf) { clear(); } template <class C> DS_DynamicList(C& c, ll inf) : n((ll)c.size()), inf(inf) { init(c); } // list interface void clear(void) { n = 0, next.clear(), prev.clear(), next[-inf] = inf, prev[-inf] = -inf, next[inf] = inf, prev[inf] = -inf; } bool push_back(T x) { return next_insert(back(), x); } bool push_front(T x) { return prev_insert(front(), x); } ll size(void) { return n; } // original interface T back(void) { return prev[inf]; } T begin_val(void) { return next[-inf]; } T end_val(void) { return inf; } bool find(T x) { return (next.find(x) != next.end()); } T front(void) { return next[-inf]; } T next_val(T x) { return (next.find(x) == next.end()) ? x : next[x]; } T prev_val(T x) { return (prev.find(x) == prev.end()) ? x : prev[x]; } bool change(T x, T y) { if (!find_val(x) || !find_val(y)) return false; prev[y] = prev[x], next[y] = next[x], prev.erase(x), next.erase(x); return true; } bool erase(T x) { if (!find(x)) return false; ll y = prev[x]; ll z = next[x]; n--; next[y] = z, prev[z] = y, next.erase(x), prev.erase(x); return true; } template <class C> void init(C& c) { next.clear(), prev.clear(); next[-inf] = c[0], prev[-inf] = inf, next[inf] = inf, prev[inf] = c[n - 1]; next[c[0]] = c[1], prev[c[0]] = -inf, next[c[n - 1]] = inf, prev[c[n - 1]] = c[n - 2]; for (ll i = 1; i < n - 1; i++) prev[c[i]] = c[i - 1], next[c[i]] = c[i + 1]; if (next.size() != n - 2) next.clear(), prev.clear(), n = 0; } bool next_insert(T x, T y) { if (!(find(x)) || find(y)) return false; ll temp = next[x]; n++; next[x] = y, prev[y] = x, next[y] = temp, prev[temp] = y; return true; } bool prev_insert(T x, T y) { if (!(find(x)) || find(y)) return false; ll temp = prev[x]; n++; prev[x] = y, prev[y] = temp, next[y] = x, next[temp] = y; return true; } bool swap(T x, T y) { if (!find(x) || !find(y) || abs(x) == inf || abs(y) == inf) return false; ll a = prev[x]; ll b = next[x]; ll c = prev[y]; ll d = next[y]; if (c == x) next[a] = y, next[y] = x, next[x] = d, prev[y] = a, prev[x] = y, prev[d] = x; else if (d == x) next[c] = x, next[x] = y, next[y] = b, prev[x] = c, prev[y] = x, prev[b] = y; else next[a] = y, next[y] = b, next[c] = x, next[x] = d, prev[y] = a, prev[b] = y, prev[x] = c, prev[d] = x; return true; } }; }