shogo-library
競技プログラミング用の C++ ライブラリ
test/unittest/vector-func.test.cpp
- View this file on GitHub
- Last update: 2026-10-13 06:02:01+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
// vector_func.hpp の演算子と関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#include "../../src/base/vector_func.hpp"
bool ok = true;
void check(bool cond, const char* what) {
if (!cond) {
if (ok) std::cerr << "failed: " << what << std::endl;
ok = false;
}
}
int main() {
std::mt19937_64 rng(314);
auto rand_vec = [&](int n) {
std::vector<long long> v(n);
for (auto& x : v) x = (long long)(rng() % 21) - 10;
return v;
};
for (int rep = 0; rep < 2000 && ok; rep++) {
int n = rng() % 8, m = rng() % 8;
std::vector<long long> a = rand_vec(n), b = rand_vec(m);
long long c = (long long)(rng() % 11) - 5;
// ++ / -- (前置は変更後、後置は変更前を返す)
{
std::vector<long long> x = a, inc = a, dec = a;
for (auto& e : inc) e++;
for (auto& e : dec) e--;
check(++x == inc && x == inc, "前置 ++");
check(x-- == inc && x == a, "後置 --");
check(--x == dec && x == dec, "前置 --");
check(x++ == dec && x == a, "後置 ++");
}
// 要素ごとの和 (短い方は 0 で埋める)
{
std::vector<long long> expect(std::max(n, m));
for (int i = 0; i < (int)expect.size(); i++) expect[i] = (i < n ? a[i] : 0) + (i < m ? b[i] : 0);
check(a + b == expect, "v + w");
std::vector<long long> x = a;
x += b;
check(x == expect, "v += w");
}
// 要素ごとの積 (どちらかにない位置は 0)
{
std::vector<long long> expect(std::max(n, m));
for (int i = 0; i < (int)expect.size(); i++) expect[i] = (i < n && i < m) ? a[i] * b[i] : 0;
check(a * b == expect, "v * w");
std::vector<long long> x = a;
x *= b;
check(x == expect, "v *= w");
}
// スカラーとの和・積
{
std::vector<long long> plus = a, times = a;
for (auto& e : plus) e += c;
for (auto& e : times) e *= c;
check(a + c == plus && c + a == plus, "v + c, c + v");
check(a * c == times && c * a == times, "v * c, c * v");
std::vector<long long> x = a;
x += c;
check(x == plus, "v += c");
x = a;
x *= c;
check(x == times, "v *= c");
}
// 連結と繰り返し
{
std::vector<long long> cat = a;
cat.insert(cat.end(), b.begin(), b.end());
std::vector<long long> x = a;
check(&extend(x, b) == &x && x == cat, "extend");
x = a;
x |= b;
check(x == cat, "v |= w");
int k = rng() % 4;
std::vector<long long> rep_k;
for (int i = 0; i < k; i++) rep_k.insert(rep_k.end(), a.begin(), a.end());
check((a | k) == rep_k && (k | a) == rep_k, "v | k, k | v");
x = a;
x |= k;
check(x == rep_k, "v |= k");
}
// assign (型の変換つき)
{
std::vector<int> small(b.begin(), b.end());
std::vector<long long> x = a;
check(&assign(x, small) == &x && x == b, "assign");
}
// abs
{
std::vector<long long> expect = a;
for (auto& e : expect) e = std::llabs(e);
check(abs(a) == expect, "abs");
}
// sorted_idx: 値の昇順 (降順) に並べた添字の並び替え
{
for (bool rev : {false, true}) {
auto idx = sorted_idx(a, rev);
std::vector<std::ptrdiff_t> perm = idx;
std::sort(perm.begin(), perm.end());
bool is_perm = (int)perm.size() == n;
for (int i = 0; i < (int)perm.size() && is_perm; i++) is_perm = perm[i] == i;
bool is_sorted = true;
for (int i = 0; i + 1 < (int)idx.size(); i++) {
if (rev ? a[idx[i]] < a[idx[i + 1]] : a[idx[i]] > a[idx[i + 1]]) is_sorted = false;
}
check(is_perm && is_sorted, "sorted_idx");
}
}
// iota
{
std::vector<int> expect(n);
for (int i = 0; i < n; i++) expect[i] = i;
check(iota(n) == expect, "iota");
}
// radix_convert: 整数 -> 桁 (上位から) -> 整数
{
int base = rng() % 15 + 2;
long long x = rng() % 1000000000000LL;
std::vector<long long> digits;
for (long long y = x; y > 0; y /= base) digits.push_back(y % base);
std::reverse(digits.begin(), digits.end());
check(radix_convert(x, base) == digits, "radix_convert(x, base)");
check(radix_convert(digits, base) == x, "radix_convert(digits, base)");
}
}
// 決まった値
check(radix_convert(123, 10) == std::vector<long long>{1, 2, 3}, "radix_convert(123)");
check(radix_convert(std::vector<long long>{1, 0, 1, 1}, 2) == 11, "radix_convert({1,0,1,1}, 2)");
check(radix_convert(0, 10).empty() && radix_convert(std::vector<long long>{}, 10) == 0, "radix_convert 0");
check(iota(0).empty(), "iota(0)");
check((std::vector<int>{1, 2} | 0).empty(), "v | 0");
if (ok) std::cout << "Hello World" << std::endl;
}#line 1 "test/unittest/vector-func.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
// vector_func.hpp の演算子と関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#line 2 "src/base/vector_func.hpp"
/**
* @file vector_func.hpp
* @brief vector に対する演算子と関数
*/
#line 9 "src/base/vector_func.hpp"
#include <cassert>
#include <cmath>
#include <cstddef>
#include <numeric>
#line 14 "src/base/vector_func.hpp"
#line 2 "src/base/traits.hpp"
/**
* @file traits.hpp
* @brief 型特性
*/
#line 9 "src/base/traits.hpp"
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
namespace detail {
using std::begin, std::end;
template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
} // namespace detail
template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;
#define HAS_METHOD(func_name) \
namespace detail { \
template <class T, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T> \
struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
: std::true_type {}; \
} \
template <class T> \
struct has_##func_name : detail::has_##func_name##_impl<T>::type {}; \
template <class T> \
inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;
#define HAS_METHOD_ARG(func_name) \
namespace detail { \
template <class T, typename U, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T, typename U> \
struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
: std::true_type {}; \
} \
template <class T, typename U> \
struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {}; \
template <class T, typename U> \
inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;
HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)
#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))
template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;
namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
} // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 16 "src/base/vector_func.hpp"
template <typename T>
std::vector<std::ptrdiff_t> sorted_idx(const std::vector<T> &v, bool reverse = false) {
std::vector<std::ptrdiff_t> ret(v.size());
std::iota(ret.begin(), ret.end(), 0);
std::sort(ret.begin(), ret.end(), [&](std::ptrdiff_t i, std::ptrdiff_t j) {
return v[i] < v[j];
});
if (reverse) std::reverse(ret.begin(), ret.end());
return ret;
}
template <typename T>
inline std::vector<T> &operator++(std::vector<T> &v) {
for (auto &e : v) e++;
return v;
}
template <typename T>
inline std::vector<T> operator++(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) e++;
return res;
}
template <typename T>
inline std::vector<T> &operator--(std::vector<T> &v) {
for (auto &e : v) e--;
return v;
}
template <typename T>
inline std::vector<T> operator--(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) e--;
return res;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator+=(std::vector<T> &v1, const std::vector<U> &v2) {
if (v2.size() > v1.size()) {
v1.resize(v2.size());
}
for (size_t i = 0; i < v2.size(); i++) {
v1[i] += v2[i];
}
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const std::vector<T> &v1, const std::vector<U> &v2) {
std::vector<T> res(v1);
return res += v2;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator+=(std::vector<T> &v, const U &u) {
for (T &e : v) {
e += u;
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res += u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res += u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator*=(std::vector<T> &v1, const std::vector<U> &v2) {
if (v2.size() > v1.size()) {
v1.resize(v2.size());
}
for (size_t i = 0; i < v2.size(); i++) {
v1[i] *= v2[i];
}
for (size_t i = v2.size(); i < v1.size(); i++) {
v1[i] *= U(0);
}
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const std::vector<T> &v1, const std::vector<U> &v2) {
std::vector<T> res(v1);
return res *= v2;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator*=(std::vector<T> &v, const U &u) {
for (T &e : v) {
e *= u;
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res *= u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res *= u;
}
template <typename T, typename U>
inline std::vector<T> &assign(std::vector<T> &v1, const std::vector<U> &v2) {
v1.assign(v2.begin(), v2.end());
return v1;
}
template <typename T, typename U>
inline std::vector<T> &extend(std::vector<T> &v1, const std::vector<U> &v2) {
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator|=(std::vector<T> &v1, const std::vector<U> &v2) {
return extend(v1, v2);
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> &operator|=(std::vector<T> &v, const U &u) {
std::vector<T> w(v);
v.clear();
for (int i = 0; i < u; i++) {
extend(v, w);
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> operator|(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res |= u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> operator|(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res |= u;
}
template <typename T>
inline std::vector<T> abs(const std::vector<T> &v) {
std::vector<T> ret;
ret.reserve(v.size());
for (const T &e : v) ret.push_back(std::abs(e));
return ret;
}
template <typename T>
std::vector<T> cumulative_sum(std::vector<T> v) {
v.insert(v.begin(), T{});
std::vector<T> ret(v.size());
std::partial_sum(v.begin(), v.end(), ret.begin());
return ret;
}
template <typename T, ENABLE_IF_T(std::is_integral_v<T>)>
std::vector<T> iota(T n) {
assert(n >= 0);
std::vector<T> ret(n);
std::iota(ret.begin(), ret.end(), 0);
return ret;
}
template <typename T>
std::vector<T> unique(const std::vector<T> &v) {
std::vector<T> res(v);
std::sort(res.begin(), res.end());
res.erase(std::unique(res.begin(), res.end()), res.end());
return res;
}
inline long long radix_convert(const std::vector<long long> &v, int base = 10) {
long long res = 0;
for (long long d : v) {
res = res * base + d;
}
return res;
}
inline std::vector<long long> radix_convert(long long v, int base = 10) {
std::vector<long long> res;
while (v > 0) {
res.push_back(v % base);
v /= base;
}
std::reverse(res.begin(), res.end());
return res;
}
#line 13 "test/unittest/vector-func.test.cpp"
bool ok = true;
void check(bool cond, const char* what) {
if (!cond) {
if (ok) std::cerr << "failed: " << what << std::endl;
ok = false;
}
}
int main() {
std::mt19937_64 rng(314);
auto rand_vec = [&](int n) {
std::vector<long long> v(n);
for (auto& x : v) x = (long long)(rng() % 21) - 10;
return v;
};
for (int rep = 0; rep < 2000 && ok; rep++) {
int n = rng() % 8, m = rng() % 8;
std::vector<long long> a = rand_vec(n), b = rand_vec(m);
long long c = (long long)(rng() % 11) - 5;
// ++ / -- (前置は変更後、後置は変更前を返す)
{
std::vector<long long> x = a, inc = a, dec = a;
for (auto& e : inc) e++;
for (auto& e : dec) e--;
check(++x == inc && x == inc, "前置 ++");
check(x-- == inc && x == a, "後置 --");
check(--x == dec && x == dec, "前置 --");
check(x++ == dec && x == a, "後置 ++");
}
// 要素ごとの和 (短い方は 0 で埋める)
{
std::vector<long long> expect(std::max(n, m));
for (int i = 0; i < (int)expect.size(); i++) expect[i] = (i < n ? a[i] : 0) + (i < m ? b[i] : 0);
check(a + b == expect, "v + w");
std::vector<long long> x = a;
x += b;
check(x == expect, "v += w");
}
// 要素ごとの積 (どちらかにない位置は 0)
{
std::vector<long long> expect(std::max(n, m));
for (int i = 0; i < (int)expect.size(); i++) expect[i] = (i < n && i < m) ? a[i] * b[i] : 0;
check(a * b == expect, "v * w");
std::vector<long long> x = a;
x *= b;
check(x == expect, "v *= w");
}
// スカラーとの和・積
{
std::vector<long long> plus = a, times = a;
for (auto& e : plus) e += c;
for (auto& e : times) e *= c;
check(a + c == plus && c + a == plus, "v + c, c + v");
check(a * c == times && c * a == times, "v * c, c * v");
std::vector<long long> x = a;
x += c;
check(x == plus, "v += c");
x = a;
x *= c;
check(x == times, "v *= c");
}
// 連結と繰り返し
{
std::vector<long long> cat = a;
cat.insert(cat.end(), b.begin(), b.end());
std::vector<long long> x = a;
check(&extend(x, b) == &x && x == cat, "extend");
x = a;
x |= b;
check(x == cat, "v |= w");
int k = rng() % 4;
std::vector<long long> rep_k;
for (int i = 0; i < k; i++) rep_k.insert(rep_k.end(), a.begin(), a.end());
check((a | k) == rep_k && (k | a) == rep_k, "v | k, k | v");
x = a;
x |= k;
check(x == rep_k, "v |= k");
}
// assign (型の変換つき)
{
std::vector<int> small(b.begin(), b.end());
std::vector<long long> x = a;
check(&assign(x, small) == &x && x == b, "assign");
}
// abs
{
std::vector<long long> expect = a;
for (auto& e : expect) e = std::llabs(e);
check(abs(a) == expect, "abs");
}
// sorted_idx: 値の昇順 (降順) に並べた添字の並び替え
{
for (bool rev : {false, true}) {
auto idx = sorted_idx(a, rev);
std::vector<std::ptrdiff_t> perm = idx;
std::sort(perm.begin(), perm.end());
bool is_perm = (int)perm.size() == n;
for (int i = 0; i < (int)perm.size() && is_perm; i++) is_perm = perm[i] == i;
bool is_sorted = true;
for (int i = 0; i + 1 < (int)idx.size(); i++) {
if (rev ? a[idx[i]] < a[idx[i + 1]] : a[idx[i]] > a[idx[i + 1]]) is_sorted = false;
}
check(is_perm && is_sorted, "sorted_idx");
}
}
// iota
{
std::vector<int> expect(n);
for (int i = 0; i < n; i++) expect[i] = i;
check(iota(n) == expect, "iota");
}
// radix_convert: 整数 -> 桁 (上位から) -> 整数
{
int base = rng() % 15 + 2;
long long x = rng() % 1000000000000LL;
std::vector<long long> digits;
for (long long y = x; y > 0; y /= base) digits.push_back(y % base);
std::reverse(digits.begin(), digits.end());
check(radix_convert(x, base) == digits, "radix_convert(x, base)");
check(radix_convert(digits, base) == x, "radix_convert(digits, base)");
}
}
// 決まった値
check(radix_convert(123, 10) == std::vector<long long>{1, 2, 3}, "radix_convert(123)");
check(radix_convert(std::vector<long long>{1, 0, 1, 1}, 2) == 11, "radix_convert({1,0,1,1}, 2)");
check(radix_convert(0, 10).empty() && radix_convert(std::vector<long long>{}, 10) == 0, "radix_convert 0");
check(iota(0).empty(), "iota(0)");
check((std::vector<int>{1, 2} | 0).empty(), "v | 0");
if (ok) std::cout << "Hello World" << std::endl;
}