Shifted Array
(utilities/shifted_array.hpp)

• View this file on GitHub
• Last update: 2026-06-13 20:51:48+09:00
• Include: #include "utilities/shifted_array.hpp"

Overview

A convenient wrapper around std::vector that allows arbitrary index ranges, including negative indices or non-zero starting indices. It stores values for the closed interval $[L, R]$ at indices L, L + step, L + 2 * step, and so on.

Template Parameters

• T: The underlying data type. bool is not supported; use char instead if you need a boolean-like array.

Methods

Method	Description	Complexity / Throws
ShiftedArray(long long L, long long R, T init_value = T(), long long step = 1)	Constructs an array for indices L, L + step, ... , R. init_value is used for every stored element.	Throws std::invalid_argument if step <= 0 or L > R.
T& operator[](long long i)	Accesses the element at shifted index i.	$O(1)$; throws std::out_of_range if i is outside the configured bounds or is not aligned to step.
long long index(long long i) const	Returns the internal 0-based vector index for shifted index i.	$O(1)$; throws std::out_of_range if i is outside the configured bounds or is not aligned to step.

Example

#include "utilities/shifted_array.hpp"
#include <iostream>

int main() {
    // Create an array with indices -4, -2, 0, 2, 4.
    m1une::utilities::ShiftedArray<int> arr(-4, 4, 0, 2);

    arr[-4] = 10;
    arr[0] = 50;
    arr[4] = 100;

    std::cout << arr[-4] << " " << arr[4] << "\n"; // Output: 10 100
    return 0;
}

Verified with

• verify/utilities/shifted_array.test.cpp

Code

#ifndef M1UNE_SHIFTED_ARRAY_HPP
#define M1UNE_SHIFTED_ARRAY_HPP 1

#include <stdexcept>
#include <vector>

namespace m1une {
namespace utilities {

// `bool` is not supported; use `char` for boolean-like arrays.
template <typename T>
struct ShiftedArray {
   private:
    long long _offset;
    long long _step;
    long long _size;
    std::vector<T> _data;

    static long long checked_size(long long L, long long R, long long step) {
        if (step <= 0) {
            throw std::invalid_argument("Step must be positive");
        }
        if (L > R) {
            throw std::invalid_argument("Left bound must be less than or equal to right bound");
        }
        return (R - L) / step + 1;
    }

    long long to_index(long long i) const {
        if (i < _offset) {
            throw std::out_of_range("Index out of range");
        }
        long long diff = i - _offset;
        if (diff % _step != 0) {
            throw std::out_of_range("Index is not aligned to the step");
        }
        long long index = diff / _step;
        if (index >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return index;
    }

   public:
    // Creates an array on the closed interval [L, R] using the given step.
    ShiftedArray(long long L, long long R, T init_value = T(), long long step = 1)
        : _offset(L), _step(step), _size(checked_size(L, R, step)), _data(_size, init_value) {}

    T& operator[](long long i) {
        return _data[to_index(i)];
    }

    const T& operator[](long long i) const {
        return _data[to_index(i)];
    }

    long long index(long long i) const {
        return to_index(i);
    }
};

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_SHIFTED_ARRAY_HPP

#line 1 "utilities/shifted_array.hpp"



#include <stdexcept>
#include <vector>

namespace m1une {
namespace utilities {

// `bool` is not supported; use `char` for boolean-like arrays.
template <typename T>
struct ShiftedArray {
   private:
    long long _offset;
    long long _step;
    long long _size;
    std::vector<T> _data;

    static long long checked_size(long long L, long long R, long long step) {
        if (step <= 0) {
            throw std::invalid_argument("Step must be positive");
        }
        if (L > R) {
            throw std::invalid_argument("Left bound must be less than or equal to right bound");
        }
        return (R - L) / step + 1;
    }

    long long to_index(long long i) const {
        if (i < _offset) {
            throw std::out_of_range("Index out of range");
        }
        long long diff = i - _offset;
        if (diff % _step != 0) {
            throw std::out_of_range("Index is not aligned to the step");
        }
        long long index = diff / _step;
        if (index >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return index;
    }

   public:
    // Creates an array on the closed interval [L, R] using the given step.
    ShiftedArray(long long L, long long R, T init_value = T(), long long step = 1)
        : _offset(L), _step(step), _size(checked_size(L, R, step)), _data(_size, init_value) {}

    T& operator[](long long i) {
        return _data[to_index(i)];
    }

    const T& operator[](long long i) const {
        return _data[to_index(i)];
    }

    long long index(long long i) const {
        return to_index(i);
    }
};

}  // namespace utilities
}  // namespace m1une

Back to top page