data_structure/light_forward_list.hpp

• View this file on GitHub
• Last update: 2021-02-26 23:47:50+09:00
• Include: #include "data_structure/light_forward_list.hpp"
• Link: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D>

Required by

• 無向グラフの長さ 2 のパスへの分解 (graph/paths_of_length_two_decomposition.hpp)
• string/aho_corasick.hpp
• string/aho_corasick_online.hpp
• string/incremental_matching.hpp

Verified with

• string/test/aho_corasick_forwardlist.test.cpp
• string/test/aho_corasick_online.test.cpp
• string/test/aho_corasick_unorderedmap.test.cpp
• string/test/aho_corasick_vector.test.cpp
• string/test/incremental_matching.test.cpp

Code

#pragma once
#include <vector>

// CUT begin
// Simple forward_list for MLE-sensitive situations
// Verify: <http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D>
template <typename T> struct light_forward_list {
    static std::vector<unsigned> ptr;
    static std::vector<T> val;
    unsigned head;
    light_forward_list() : head(0) {}
    void push_front(T x) {
        ptr.push_back(head), val.push_back(x);
        head = ptr.size() - 1;
    }
    struct iterator {
        unsigned p;
        iterator operator++() { return {p = ptr[p]}; }
        T &operator*() { return val[p]; }
        bool operator!=(const iterator &rhs) { return p != rhs.p; }
    };
    iterator begin() { return {head}; }
    iterator end() { return {0}; }
};
template <typename T> std::vector<unsigned> light_forward_list<T>::ptr = {0};
template <typename T> std::vector<T> light_forward_list<T>::val = {T()};

#line 2 "data_structure/light_forward_list.hpp"
#include <vector>

// CUT begin
// Simple forward_list for MLE-sensitive situations
// Verify: <http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D>
template <typename T> struct light_forward_list {
    static std::vector<unsigned> ptr;
    static std::vector<T> val;
    unsigned head;
    light_forward_list() : head(0) {}
    void push_front(T x) {
        ptr.push_back(head), val.push_back(x);
        head = ptr.size() - 1;
    }
    struct iterator {
        unsigned p;
        iterator operator++() { return {p = ptr[p]}; }
        T &operator*() { return val[p]; }
        bool operator!=(const iterator &rhs) { return p != rhs.p; }
    };
    iterator begin() { return {head}; }
    iterator end() { return {0}; }
};
template <typename T> std::vector<unsigned> light_forward_list<T>::ptr = {0};
template <typename T> std::vector<T> light_forward_list<T>::val = {T()};

Back to top page