おたまじゃくし配列
(src/data_structures/tadpole-array.hpp)

• View this file on GitHub
• Last update: 2026-10-12 19:23:31+09:00
• Include: #include "src/data_structures/tadpole-array.hpp"

途中からループする無限列を表します (ρ 型、おたまじゃくしの形)。長さ $n$ の配列と、末尾の次に戻る位置 $i$ を与えると、data[0], ..., data[n-1], data[i], ..., data[n-1], data[i], ... という列になります。Functional Graph をたどったときの頂点列などに使えます。

TadpoleArray<int> t(std::vector<int>{1, 2, 3, 4}, 1);  // 1 2 3 4 2 3 4 2 3 4 ...
int a = t[4];                 // 2
int b = t[1000000000000LL];   // 2

メンバ

メンバ	説明	計算量
TadpoleArray<T>(v, i)	配列 v の末尾の次を v[i] にする ($0 \le i < n$)	$O(n)$
t[k] / t.at(k)	列の k 番目 (size_t の添字)	$O(1)$

関連

• 先頭からループする配列は 円環
• ファンクショナルグラフ

Verified with

• test/unittest/tadpole-array.test.cpp

Code

#pragma once

/**
 * @file tadpole-array.hpp
 * @brief おたまじゃくし配列
 */

#include <cassert>
#include <vector>
/**
 * @brief おたまじゃくし配列
 * 特定の位置でループする構造
 * @tparam T
 */
template <typename T>
struct TadpoleArray {
   private:
    std::vector<T> data;
    size_t k;

   public:
    /**
     * @brief 最後の次のインデックスがi
     */
    TadpoleArray(const std::vector<T>& v, int i) : data(v) {
        assert(0 <= i and i < static_cast<int>(data.size()));
        k = static_cast<size_t>(i);
    }
    TadpoleArray() = default;
    TadpoleArray(const TadpoleArray&) = default;
    T at(size_t i) const {
        if (i < k) return data[i];
        return data[(i - k) % (data.size() - k) + k];
    }
    T operator[](size_t i) const {
        return at(i);
    }
};

#line 2 "src/data_structures/tadpole-array.hpp"

/**
 * @file tadpole-array.hpp
 * @brief おたまじゃくし配列
 */

#include <cassert>
#include <vector>
/**
 * @brief おたまじゃくし配列
 * 特定の位置でループする構造
 * @tparam T
 */
template <typename T>
struct TadpoleArray {
   private:
    std::vector<T> data;
    size_t k;

   public:
    /**
     * @brief 最後の次のインデックスがi
     */
    TadpoleArray(const std::vector<T>& v, int i) : data(v) {
        assert(0 <= i and i < static_cast<int>(data.size()));
        k = static_cast<size_t>(i);
    }
    TadpoleArray() = default;
    TadpoleArray(const TadpoleArray&) = default;
    T at(size_t i) const {
        if (i < k) return data[i];
        return data[(i - k) % (data.size() - k) + k];
    }
    T operator[](size_t i) const {
        return at(i);
    }
};

Back to top page