很有意思但不知道实际有啥用的东西
链表
#include <iostream>
#include <type_traits>
/*
功能：
- 获取 size
- 将 List 从指定位置拆分成两个
- 合并两个 List
- 读取/删除某位置的元素
- 在头部/末尾/任意位置插入元素
- 查询某元素第一次出现的位置
（修改指定位置的值，可以通过删除+插入实现，懒得再封装了）
可以支持任意类型而不是 int，再加一个模板参数 T 即可。
*/
template <int... values>
struct List;
template <>
struct List<> {
static constexpr size_t size = 0;
};
using EmptyList = List<>;
template <int head, int... values>
struct List<head, values...> {
static constexpr int front = head;
static constexpr size_t size = 1 + sizeof...(values);
using PopFrontT = std::conditional_t<size == 1, EmptyList, List<values...>>;
};
// template <int head>
// struct List<head> { // 长度为 1 的情况
// static constexpr int front = head;
// static constexpr size_t size = 1;
// using PopFrontT = EmptyList;
// };
// --- insert
template <typename T, int value>
struct PushFront;
template <int... values, int x>
struct PushFront<List<values...>, x> {
using type = List<x, values...>;
};
template <typename T, int value>
struct PushBack;
template <int... values, int x>
struct PushBack<List<values...>, x> {
using type = List<values..., x>;
};
// --- split：将 List 从指定位置拆分成两个
template <size_t pos, typename L, typename R>
struct SplitImpl;
template <size_t now, int... L, int... R>
struct SplitImpl<now, List<L...>, List<R...>> { // 每次取出 R 中的一个放入 L
using next = SplitImpl<now - 1, List<L..., List<R...>::front>, typename List<R...>::PopFrontT>;
using newL = typename next::newL;
using newR = typename next::newR;
};
template <int... L, int... R>
struct SplitImpl<0, List<L...>, List<R...>> {
using newL = List<L...>;
using newR = List<R...>;
};
template <size_t pos, typename T>
struct Split;
template <size_t pos, int... values>
struct Split<pos, List<values...>> {
using L = typename SplitImpl<pos, EmptyList, List<values...>>::newL;
using R = typename SplitImpl<pos, EmptyList, List<values...>>::newR;
};
// --- merge：合并两个 List
template <typename L, typename R>
struct Merge;
template <int... L, int... R>
struct Merge<List<L...>, List<R...>> {
using type = List<L..., R...>;
};
// --- get：读取某位置的元素
template <size_t pos, typename T>
struct Get;
template <size_t pos, int... values>
struct Get<pos, List<values...>> {
static constexpr int value = Get<pos - 1, typename List<values...>::PopFrontT>::value;
};
template <int... values>
struct Get<0, List<values...>> {
static constexpr int value = List<values...>::front;
};
// --- delete：删除某位置的元素
template <size_t pos, typename T>
struct Delete;
template <size_t pos, int... values>
struct Delete<pos, List<values...>> {
using temp = Split<pos, List<values...>>;
using type = typename Merge<typename temp::L, typename temp::R::PopFrontT>::type;
};
// --- insert：在某位置插入元素
template <size_t pos, int x, typename T>
struct Insert;
template <size_t pos, int x, int... values>
struct Insert<pos, x, List<values...>> {
using temp = Split<pos, List<values...>>;
using type = typename Merge<typename PushBack<typename temp::L, x>::type, typename temp::R>::type;
};
// --- find：查询某元素第一次出现的位置
template <typename T, int v, int now>
struct FindImpl;
template <int v, int front, int... values, int now>
struct FindImpl<List<front, values...>, v, now> {
static constexpr int pos = v == front ? now : FindImpl<List<values...>, v, now + 1>::pos;
};
template <int v, int now>
struct FindImpl<List<>, v, now> {
static constexpr int pos = -1;
};
template <typename T, auto value>
struct Find;
template <int v, int... values>
struct Find<List<values...>, v>: FindImpl<List<values...>, v, 0> {};
// ---
int main() {
using L1 = List<1, 2, 3, 4>;
using L1l = Split<2, L1>::L;
using L2 = List<3, 4, 5>;
using L1l2 = Merge<L1l, L2>::type;
using L2pf = PushFront<L2, 2>::type;
using L2pfpb = PushBack<L2pf, 6>::type;
using L2d1 = Delete<0, L2pfpb>::type;
using L2d2 = Delete<2, L2pfpb>::type;
using L2d3 = Delete<4, L2pfpb>::type;
using L3i1 = Insert<0, 0, L1>::type;
using L3i2 = Insert<2, 0, L1>::type;
using L3i3 = Insert<4, 0, L1>::type;
[](...) {} (
EmptyList::size,
L1::size,
Get<0, L1>::value,
Get<3, L1>::value,
// Get<4, L1>::value, // 可以在编译期检查越界（因为没有该模板的定义）
Find<L1, 1>::pos,
Find<L1, 3>::pos,
Find<L1, 4>::pos,
Find<L1, 5>::pos
);
}
数组
#include <cstdio>
#include <vector>
#include <iostream>
#include <type_traits>
/*
功能：
- 获取 size
- 拆分一个数组
- 合并两个数组
- 读写某位置的元素
- 在任意位置插入元素
支持任意类型（只能有一种）。
实现与链表类似，只是有数组后可直接获取某位置的元素。
*/
template<typename T, T... values>
struct Array;
template<typename T, T head, T... values>
struct Array<T, head, values...> {
using ValueType = T;
static constexpr size_t size = 1 + sizeof...(values);
static constexpr T front = head;
static constexpr T data[] = {head, values...};
using PopFrontT = Array<T, values...>;
static_assert(size > 0);
};
template<typename T>
struct Array<T> {
using ValueType = T;
static constexpr size_t size = 0;
};
template<typename T>
using EmptyArray = Array<T>;
// split
template <size_t pos, typename L, typename R>
struct SplitImpl;
template <size_t now, typename T, T... L, T... R>
struct SplitImpl<now, Array<T, L...>, Array<T, R...>> {
using next = SplitImpl<now - 1, Array<T, L..., Array<T, R...>::front>, typename Array<T, R...>::PopFrontT>;
using newL = typename next::newL;
using newR = typename next::newR;
};
template <typename T, T... L, T... R>
struct SplitImpl<0, Array<T, L...>, Array<T, R...>> {
using newL = Array<T, L...>;
using newR = Array<T, R...>;
};
template <size_t pos, typename T>
struct Split;
template <size_t pos, typename T, int... values>
struct Split<pos, Array<T, values...>> {
using L = typename SplitImpl<pos, EmptyArray<T>, Array<T, values...>>::newL;
using R = typename SplitImpl<pos, EmptyArray<T>, Array<T, values...>>::newR;
};
// merge：合并两个 Array
template <typename L, typename R>
struct Merge;
template <typename T, T... L, T... R>
struct Merge<Array<T, L...>, Array<T, R...>> {
using type = Array<T, L..., R...>;
};
// get：读取某位置的元素
template <size_t pos, typename T>
struct Get;
template <size_t pos, typename T, T... values>
struct Get<pos, Array<T, values...>> {
static constexpr T value = Array<T, values...>::data[pos];
};
// 其它同链表
int main() {
using A1 = Array<int, 1, 2, 3, 4>;
using A1l = Split<2, A1>::L;
using A2 = Array<int, 3, 4, 5>;
using A1l2 = Merge<A1l, A2>::type;
[](...) {} (
EmptyArray<int>::size,
A1::size,
Get<0, A1>::value,
Get<3, A1>::value
// Get<4, L1>::value // 可以在编译期检查越界（因为没有该模板的定义）
);
}
归并排序
#include <iostream>
#include <type_traits>
template <int... values>
struct List;
template <>
struct List<> {
static constexpr size_t size = 0;
};
using EmptyList = List<>;
template <int head, int... values>
struct List<head, values...> {
static constexpr int front = head;
static constexpr size_t size = 1 + sizeof...(values);
using PopFrontT = std::conditional_t<size == 1, EmptyList, List<values...>>;
};
// --- insert
template <typename T, int value>
struct PushFront;
template <int... values, int x>
struct PushFront<List<values...>, x> {
using type = List<x, values...>;
};
// --- split：将 List 从指定位置拆分成两个
template <size_t pos, typename L, typename R>
struct SplitImpl;
template <size_t now, int... L, int... R>
struct SplitImpl<now, List<L...>, List<R...>> { // 每次取出 R 中的一个放入 L
using next = SplitImpl<now - 1, List<L..., List<R...>::front>, typename List<R...>::PopFrontT>;
using newL = typename next::newL;
using newR = typename next::newR;
};
template <int... L, int... R>
struct SplitImpl<0, List<L...>, List<R...>> {
using newL = List<L...>;
using newR = List<R...>;
};
template <size_t pos, typename T>
struct Split;
template <size_t pos, int... values>
struct Split<pos, List<values...>> {
using L = typename SplitImpl<pos, EmptyList, List<values...>>::newL;
using R = typename SplitImpl<pos, EmptyList, List<values...>>::newR;
};
// --- merge：合并两个 List
// template <typename L, typename R>
// struct Merge;
// template <int... L, int... R>
// struct Merge<List<L...>, List<R...>> {
// using type = List<L..., R...>;
// };
// --- merge：合并两个有序链表
template <typename L, typename R>
struct Merge;
template <int... L, int... R>
struct Merge<List<L...>, List<R...>> {
using l = List<L...>;
using r = List<R...>;
static constexpr int min = l::front < r::front ? l::front : r::front;
using temp = std::conditional_t<
l::front < r::front,
typename Merge<typename l::PopFrontT, r>::type,
typename Merge<l, typename r::PopFrontT>::type
>;
using type = typename PushFront<temp, min>::type; // 每次取出较小值，然后递归处理后面的序列
};
// 递归边界
template <int... R>
struct Merge<EmptyList, List<R...>> {
using type = List<R...>;
};
template <int... L>
struct Merge<List<L...>, EmptyList> {
using type = List<L...>;
};
// --- mergeSort：归并排序：每次将链表拆分，递归排序，然后合并
template <typename L>
struct MergeSort;
template <int... values>
struct MergeSort<List<values...>> {
using list = List<values...>;
using l = Split<list::size / 2, list>::L;
using r = Split<list::size / 2, list>::R;
using sl = MergeSort<l>::type;
using sr = MergeSort<r>::type;
using type = Merge<sl, sr>::type;
};
// 模板递归需要定义边界！否则 MergeSort<List<values...>> 定义完之前无法递归使用 MergeSort<List<>> 和 MergeSort<List<v>>
template <int v>
struct MergeSort<List<v>> {
using type = List<v>;
};
template <>
struct MergeSort<List<>> {
using type = EmptyList;
};
// ---
int main() {
using L1 = List<1, 4, 2, 3>;
using L1l = Split<2, L1>::L;
using L2 = List<2, 3, 4, 5>;
using L1l2 = Merge<L1l, L2>::type;
using L2pf = PushFront<L2, 2>::type;
using S1 = Split<0, EmptyList>::L;
using S2 = Split<0, EmptyList>::R;
using R1 = MergeSort<EmptyList>::type;
using R2 = MergeSort<List<3>>::type;
using L3 = List<5, 2, 1, 9, 4, 2, 3, 0, 6>;
using L3r = MergeSort<L3>::type;
[](...) {} (
EmptyList::size,
L1::size,
L3::size,
L3r::size
);
}
std::variant
#include <vector>
#include <cstring>
#include <cassert>
#include <variant>
#include <iostream>
#include <type_traits>
using std::cout;
/*
[variant](https://zh.cppreference.com/w/cpp/utility/variant)
- 切换类型时析构旧对象、创建新对象。
- 接口：get、emplace、swap。错误时抛出异常。
- 辅助类/函数：get、get_if、holds_alternative、variant_alternative、visit。
- 同一类型可以出现多次，但此时只能用下标访问。
基本实现就是利用 char 数组作为存储，其大小为各类型大小的最大值。在每次切换类型时析构并重新创建对象。
需要维护当前的类型 type，来验证读取的有效性（不能读取非上次写入的类型）。因为不能将类型作为变量，所以 type 是 int 下标。
析构时，需要根据 type 确定当前类型 T，以便将 data 转为 T* 然后调用 ~T()。可以用将每种类型的 Destroy 函数保存在一个函数指针数组里，用下标调用。
注意，下标到类型的转换、类型到下标的转换，都是只能在编译期进行的。type 是运行期变量，所以无法用于这些转换，必须手动指定或根据参数值推导出 T 或下标。
注意：
- data 要对齐。
- reinterpret_cast 本身不会隐式创建对象。切换时需要使用 placement new 构造。
- 由于指针可互转换的要求，即使 data 位置有新的对象，直接 reinterpret_cast 转换 data 访问也是 UB？需要 launder 或使用 placement new 返回的指针。
- 使用 T 初始化时应用 decay(T) 匹配。否则 "abc" *只会*直接匹配 const char&[4]，然后才尝试隐式转换到 string 与 const char*（且按顺序选择），无法匹配 const char[4]。但是不需要支持保存数组，只存指针即可。
- 构造时应使用 T(...) 而非 T{...}，对于有初始化列表构造函数的类（如 string、vector）会导致不同的结果。
未完善：
- Variant 在多种异常情况下会变得无值，通过 valueless_by_exception 检测。会影响多种函数的执行。
- Variant<float, long, double> z = 0; 应匹配 long。但我不知道怎么实现哪个更匹配，所以目前隐式转换会匹配第一个合适的类型，即使有多个或更合适的。
*/
// --- 获取类型最大大小与对齐
template <typename T, typename... Ts>
struct MaxSize {
static constexpr size_t value = sizeof(T) >= MaxSize<Ts...>::value ? sizeof(T) : MaxSize<Ts...>::value;
};
template <typename T>
struct MaxSize<T> {
static constexpr size_t value = sizeof(T);
};
// 其实不需要，alignas(T...) 也可展开。对象会取最大的对齐值
template <typename T, typename... Ts>
struct MaxAlign {
static constexpr size_t value = alignof(T) >= MaxAlign<Ts...>::value ? alignof(T) : MaxAlign<Ts...>::value;
};
template <typename T>
struct MaxAlign<T> {
static constexpr size_t value = alignof(T);
};
// --- 下标到类型的转换
template <size_t pos, typename T, typename... Ts>
struct IdToType {
static_assert(pos < 1 + sizeof...(Ts));
using type = typename IdToType<pos - 1, Ts...>::type;
};
template <typename T, typename... Ts>
struct IdToType<0, T, Ts...> {
using type = T;
};
// --- 类型到下标的转换
template <size_t pos, typename X, typename T, typename... Ts>
struct TypeToIdImpl {
static constexpr size_t value = std::is_same_v<X, T> ? pos : TypeToIdImpl<pos + 1, X, Ts...>::value;
};
template <size_t pos, typename X, typename T>
struct TypeToIdImpl<pos, X, T> {
static constexpr size_t value = std::is_same_v<X, T> ? pos : (size_t)-1;
};
template <typename X, typename... Ts>
struct TypeToId {
static constexpr size_t value = TypeToIdImpl<0, X, Ts...>::value;
};
// --- 类型到下标的转换，但允许隐式转换，类型不必完全相同
template <size_t pos, typename X, typename T, typename... Ts>
struct ConvertTypeToIdImpl {
static constexpr size_t value = std::is_convertible_v<X, T> ? pos : ConvertTypeToIdImpl<pos + 1, X, Ts...>::value;
};
template <size_t pos, typename X, typename T>
struct ConvertTypeToIdImpl<pos, X, T> {
static constexpr size_t value = std::is_convertible_v<X, T> ? pos : (size_t)-1;
};
template <typename X, typename... Ts>
struct ConvertTypeToId {
static constexpr size_t value = ConvertTypeToIdImpl<0, X, Ts...>::value;
};
// --- utility
// 计算类型出现数量
template <typename X, typename T, typename... Ts>
struct CountType {
static constexpr size_t value = (std::is_same_v<X, T> ? 1 : 0) + CountType<X, Ts...>::value;
};
template <typename X, typename T>
struct CountType<X, T> {
static constexpr size_t value = (std::is_same_v<X, T> ? 1 : 0);
};
template <typename T, typename... Ts>
struct FirstType {
using type = T;
};
// 判断 V 是否是模板 T 的实例化
template <template<typename...> class T, typename V> // T 拥有模板参数 typename...
struct T_is_instantiation_of: std::false_type {};
template <template<typename...> class T, typename... Ts>
struct T_is_instantiation_of<T, T<Ts...>>: std::true_type {};
template <template<size_t...> class T, typename V> // T 拥有模板参数 size_t...
struct V_is_instantiation_of: std::false_type {};
template <template<size_t...> class T, size_t... Ts>
struct V_is_instantiation_of<T, T<Ts...>>: std::true_type {};
// --- [消歧义标签](https://zh.cppreference.com/w/cpp/utility/in_place)
// 构造 Variant 时，需传递 std::in_place_type<T> 和 T 的构造参数，指明要使用的类型是 T（也可指明下标）
template <class T>
struct in_place_type_t {
explicit in_place_type_t() = default;
};
template <class T>
inline constexpr in_place_type_t<T> in_place_type{};
template <std::size_t I>
struct in_place_index_t {
explicit in_place_index_t() = default;
};
template <std::size_t I>
inline constexpr in_place_index_t<I> in_place_index{};
// --- 其它
template <typename... Ts>
struct Variant;
template <class T>
void DestroyImpl(unsigned char* data) {
if constexpr (!std::is_trivially_destructible_v<T>) {
std::launder(reinterpret_cast<T*>(data))->~T();
}
}
// --- variant_alternative：将下标转为类型（获取当前选项）。如果 variant 有 const 限定则传给类型。
template <size_t I, class T>
struct variant_alternative;
template <std::size_t I, class... Ts>
struct variant_alternative<I, Variant<Ts...>> {
static_assert(I < sizeof...(Ts));
using type = IdToType<I, Ts...>::type;
};
template <std::size_t I, class... Ts>
class variant_alternative<I, const Variant<Ts...>> {
static_assert(I < sizeof...(Ts));
using type = std::add_const_t<typename IdToType<I, Ts...>::type>;
};
template <size_t I, class T>
using variant_alternative_t = variant_alternative<I, T>::type;
template <class T, class... Ts>
constexpr bool holds_alternative(const Variant<Ts...>& v) noexcept {
try {
v.template get<T>();
} catch (const std::bad_variant_access&) {
return false;
}
return true;
}
// --- variant
static constexpr size_t variant_npos = -1;
template <typename... Ts>
struct Variant {
static_assert(sizeof...(Ts) > 0,
"variant must have at least one alternative");
static_assert(!(std::is_reference_v<Ts> || ...),
"variant must have no reference alternative");
static_assert(!(std::is_void_v<Ts> || ...),
"variant must have no void alternative");
using T0 = FirstType<Ts...>::type;
constexpr Variant()
noexcept(std::is_nothrow_default_constructible_v<T0>)
requires std::is_default_constructible_v<T0>
{
type = 0;
new (data) T0{};
}
/*
没有办法在运行时得知当前 Variant 保存的类型，所以无法实现这两个构造函数。
只有像下面的函数一样，将参数写为模板参数（编译期常量）才可以。
将 Ts... 和当前的 type_info::name 作为 const char* 保存，可以实时判断当前的 typeid，但是没法把它转换回类型。
*/
Variant(const Variant& other) = delete;
Variant(Variant&& other) = delete;
// constexpr Variant(const Variant& other)
// requires (std::is_copy_constructible_v<Ts> && ...)
// {
// type = other.type;
// using T = IdToType<type, Ts...>::type; // error：type 不是编译时常量，不能用于编译期的类型获取
// new (data) T(other.get<type>());
// }
// constexpr Variant(Variant&& other)
// requires (std::is_move_constructible_v<Ts> && ...)
// {
// type = other.type;
// using T = IdToType<type, Ts...>::type;
// new (data) T(std::move(other.get<type>()));
// }
template <class T>
constexpr Variant(T&& t)
requires (
!std::is_same_v<std::decay_t<T>, Variant> &&
!T_is_instantiation_of<in_place_type_t, T>::value &&
!V_is_instantiation_of<in_place_index_t, T>::value &&
(TypeToId<std::decay_t<T>, Ts...>::value != variant_npos || ConvertTypeToId<std::decay_t<T>, Ts...>::value != variant_npos)
) // 可以再限制一下类型 T 在 Ts 的出现次数
{
using DT = std::decay_t<T>;
constexpr size_t id = TypeToId<DT, Ts...>::value != variant_npos ? TypeToId<DT, Ts...>::value : ConvertTypeToId<DT, Ts...>::value;
using RT = IdToType<id, Ts...>::type;
static_assert(std::is_constructible_v<RT, T>);
type = id;
new (data) RT(std::forward<T>(t));
}
template <class T>
Variant& operator =(T&& t)
requires (
!std::is_same_v<std::decay_t<T>, Variant> &&
(TypeToId<std::decay_t<T>, Ts...>::value != variant_npos || ConvertTypeToId<std::decay_t<T>, Ts...>::value != variant_npos)
)
{
using DT = std::decay_t<T>;
constexpr size_t id = TypeToId<DT, Ts...>::value != variant_npos ? TypeToId<DT, Ts...>::value : ConvertTypeToId<DT, Ts...>::value;
using RT = IdToType<id, Ts...>::type;
static_assert(std::is_assignable_v<RT&, T>);
Destroy();
type = id;
new (data) RT(std::forward<T>(t));
return *this;
}
template <class T, class... Args>
constexpr explicit Variant(in_place_type_t<T>, Args&&... args)
requires (
std::is_constructible_v<T, Args...> &&
TypeToId<T, Ts...>::value != variant_npos &&
CountType<T, Ts...>::value == 1
)
{
type = TypeToId<T, Ts...>::value;
new (data) T(std::forward<Args>(args)...);
}
template <size_t I, class... Args>
constexpr explicit Variant(in_place_index_t<I>, Args&&... args)
requires (I < sizeof...(Ts)) && std::is_constructible_v<typename IdToType<I, Ts...>::type, Args...>
{
type = I;
using T = IdToType<I, Ts...>::type;
new (data) T(std::forward<Args>(args)...);
}
// emplace
template <class T, class... Args>
T& emplace(Args&&... args)
requires (
std::is_constructible_v<T, Args...> &&
CountType<T, Ts...>::value == 1
)
{
Destroy();
type = TypeToId<T, Ts...>::value;
return *(new (data) T(std::forward<Args>(args)...));
}
template <std::size_t I, class... Args>
variant_alternative_t<I, Variant>& emplace(Args&&... args)
requires (I < sizeof...(Ts)) && std::is_constructible_v<typename IdToType<I, Ts...>::type, Args...>
{
Destroy();
type = I;
using T = IdToType<I, Ts...>::type;
return *(new (data) T(std::forward<Args>(args)...));
}
void Destroy() {
if (type != variant_npos) {
destroy_funcs[type](data);
type = variant_npos;
}
}
// get
template <typename T>
T& get() {
static_assert(CountType<T, Ts...>::value == 1);
constexpr size_t index = TypeToId<T, Ts...>::value;
return get<index>();
}
template <typename T>
const T& get() const {
static_assert(CountType<T, Ts...>::value == 1);
constexpr size_t index = TypeToId<T, Ts...>::value;
return get<index>();
}
template <size_t index>
typename IdToType<index, Ts...>::type& get() {
if (index != type) {
throw std::bad_variant_access();
}
return *std::launder(reinterpret_cast<typename IdToType<index, Ts...>::type*>(data));
}
template <size_t index>
const typename IdToType<index, Ts...>::type& get() const {
if (index != type) {
throw std::bad_variant_access();
}
return *std::launder(reinterpret_cast<typename IdToType<index, Ts...>::type*>(
const_cast<unsigned char*>(data) // const this 只能获取到 const uchar*
));
}
constexpr std::size_t index() const noexcept {
return type;
}
private:
size_t type;
// alignas(MaxAlign<Ts...>::value)
alignas(Ts...) unsigned char data[MaxSize<Ts...>::value]; // alignas(T...) 也可展开。对象会取最大的对齐值
using destroy_func_t = void (*)(unsigned char*);
static constexpr destroy_func_t destroy_funcs[] = { DestroyImpl<Ts>... };
// 注意不要与类内的 Destroy 定义重名，会优先选择后者
};
// template <typename... Ts>
// const typename Variant<Ts...>::destroy_func_t Variant<Ts...>::destroy_funcs[] = { DestroyImpl<Ts>... };
// --- 非成员函数
// --- get：通过下标/类型访问 variant 的当前值。
template <size_t I, class... Ts>
variant_alternative_t<I, Variant<Ts...>>& get(Variant<Ts...>& v) {
return v.template get<I>();
}
template <size_t I, class... Ts>
const variant_alternative_t<I, Variant<Ts...>>& get(const Variant<Ts...>& v) {
return v.template get<I>();
}
template <class T, class... Ts>
T& get(Variant<Ts...>& v) {
return v.template get<T>();
}
template <class T, class... Ts>
const T& get(const Variant<Ts...>& v) {
return v.template get<T>();
}
// --- get_if：返回 variant 当前值的指针。若下标/类型与当前值不符，或 pv 是空指针，则返回 nullptr 不抛出异常。
template <size_t I, class... Ts>
constexpr std::add_pointer_t<variant_alternative_t<I, Variant<Ts...>>>
get_if(Variant<Ts...>* pv) noexcept {
if (I != pv->index()) {
return nullptr;
}
return std::addressof(pv->template get<I>());
}
template <size_t I, class... Ts>
constexpr std::add_pointer_t<const variant_alternative_t<I, Variant<Ts...>>>
get_if(const Variant<Ts...>* pv) noexcept {
if (I != pv->index()) {
return nullptr;
}
return std::addressof(pv->template get<I>());
}
template <typename T, class... Ts>
constexpr T* get_if(Variant<Ts...>* pv) noexcept {
constexpr size_t index = TypeToId<T, Ts...>::value;
if (index != pv->index()) {
return nullptr;
}
return std::addressof(pv->template get<T>());
}
template <typename T, class... Ts>
constexpr const T* get_if(const Variant<Ts...>* pv) noexcept {
constexpr size_t index = TypeToId<T, Ts...>::value;
if (index != pv->index()) {
return nullptr;
}
return std::addressof(pv->template get<T>());
}
// ---
struct A {
double a, b;
A(): a(0), b(0) {}
A(int i): a(i), b(i) {}
bool operator ==(const A& x) const {
return a == x.a && b == x.b;
}
};
struct B {
char c;
B() {c=0;}
B(char c): c(c) {}
~B() {}
B(const B& b) {c=b.c;}
B(B&& b) {c=b.c; b.c=0;}
};
int add(int a, int b) {
return a + b;
}
double minus(double a) {
return -a;
}
int main() {
using std::vector;
using std::string;
using std::get;
using std::get_if;
using std::holds_alternative;
#if false
#define Variant std::variant
#define in_place_type std::in_place_type
#define in_place_index std::in_place_index
#endif
A a{};
B b{'0'};
{
Variant<A, char> v;
assert((size_t)std::addressof(get<0>(v)) % 8 == 0);
assert(alignof(get<0>(v)) == 8 && alignof(v) == 8);
using V = Variant<A, int, B, string>;
V v1;
assert(holds_alternative<A>(v1) && v1.index() == 0 && get<A>(v1) == A{});
assert(!holds_alternative<int>(v1));
V v2{b};
assert(v2.index() == 2 && get<2>(v2).c == '0' && b.c == '0');
V v3{std::move(b)};
assert(v3.index() == 2 && get<2>(v3).c == '0' && b.c == 0);
V v4{"abc"};
assert(v4.index() == 3 && get<3>(v4) == "abc");
using V2 = Variant<A, vector<int>, string, char>;
V2 a {in_place_type<vector<int>>, 3, (int)'a'};
assert(a.index() == 1 && get<1>(a).size() == 3 && get<1>(a)[0] == 'a');
V2 b {in_place_type<string>, 3, 'a'};
assert(b.index() == 2 && get<2>(b) == "aaa");
V2 c {in_place_index<1>, 3, 'a'};
assert(c.index() == 1 && get<1>(c).size() == 3 && get<1>(c)[0] == 'a' && holds_alternative<vector<int>>(c));
V2 d {in_place_index<2>, "ABCDE", 4};
assert(d.index() == 2 && get<2>(d) == "ABCD" && holds_alternative<string>(d));
}
{
Variant<int(*)(int, int), int, double(*)(double)> x = add;
assert(get<0>(x)(1, 2) == 3);
x.emplace<2>(minus);
assert(get<2>(x)(3) == -3);
x = add;
assert(get<0>(x)(2, 3) == 5);
Variant<string, bool, const char*> a = "abc";
assert(a.index() == 2);
// 不存放 const char[4]。"abc" 实际是 const char&[4]，也需要 remove_ref
Variant<string, const char*, const char[4]> b = "abc";
assert(b.index() == 1);
// Variant<A, in_place_index_t<1>> e;
// e = in_place_index_t<1>{}; // error
}
// get
{
Variant<int, float> v;
int& i = get<int>(v);
assert(i == 0);
i = 1;
int j = get<0>(v);
assert(j == 1);
// get<3>(v); // 越界会有编译期模板错误
// get_if<double>(&v); // 使用不存在的类型会有编译期模板错误
try { // 抛异常
get<float>(v);
get<1>(v);
}
catch (const std::bad_variant_access&) {
puts("catch");
}
assert(*get_if<0>(&v) == 1);
assert(*get_if<int>(&v) == 1);
assert(get_if<1>(&v) == nullptr);
assert(get_if<float>(&v) == nullptr);
}
// operator =
{
Variant<string, string> v1;
v1 = "abc";
assert(v1.index() == 0 && get<0>(v1) == "abc");
v1.emplace<1>("def");
assert(v1.index() == 1 && get<1>(v1) == "def");
using V = Variant<A, int, vector<int>, string>;
V v2 {vector<int>{1, 2, 3}};
assert(v2.index() == 2 && !holds_alternative<string>(v2));
v2 = "abc";
assert(v2.index() == 3 && get<string>(v2) == "abc");
v2 = 3;
assert(v2.index() == 1 && get<int>(v2) == 3);
V v3 {1};
assert(v3.index() == 1);
v3 = vector<int>(2); // resize(2)
get<2>(v3).push_back(1);
get<2>(v3).push_back(2);
for (const auto& v : get<2>(v3)) {
cout << v << ' ';
} cout << '\n';
}
// emplace
{
Variant<string, string> v1;
v1.emplace<0>("abc");
assert(v1.index() == 0 && get<0>(v1) == "abc");
v1.emplace<1>("def");
assert(v1.index() == 1 && get<1>(v1) == "def");
using V = Variant<A, int, vector<int>, string>;
V v2 {vector<int>{1, 2, 3}};
assert(v2.index() == 2 && !holds_alternative<string>(v2));
v2.emplace<string>("abc");
assert(v2.index() == 3 && get<string>(v2) == "abc");
v2.emplace<0>(3);
assert(v2.index() == 0 && get<A>(v2) == A{3});
V v3 {1};
assert(v3.index() == 1);
v3.emplace<2>(2); // resize(2)
get<2>(v3).push_back(1);
get<2>(v3).push_back(2);
auto& vec = get<2>(v3);
assert(vec[0] == 0 && vec[2] == 1 && vec[3] == 2);
}
// TODO
{
std::variant<float, long, double> b = 0;
assert(b.index() == 1); // 目前实现的结果将是 0
}
// type check
using i2t1 = IdToType<0, double, int, float, char[3]>::type;
using i2t2 = IdToType<2, double, int, float, char[3]>::type;
using i2t3 = IdToType<3, double, int, float, char[3]>::type;
using f = FirstType<int, double, A[2]>::type;
[](...) {}(
MaxSize<int, char, double, char[3], A[2]>::value,
MaxAlign<int, char, A, char[3], A[2]>::value,
TypeToId<int, int, char[3], double, A>::value,
TypeToId<char[3], int, char[3], double, A>::value,
TypeToId<A[2], int, char[3], double, A[2]>::value,
TypeToId<A[2], int, char[3], double, A>::value,
TypeToId<const char*, std::string>::value,
ConvertTypeToId<const char*, int, std::string>::value,
ConvertTypeToId<const char*, std::string, std::string>::value,
// std::is_same_v<const char*, const char[4]>, // false
TypeToId<const char[4], std::string, const char*, const char[4]>::value, // const char[4] 无意义，里面不需要放数组。此时直接匹配 const char*
TypeToId<const char*, std::string, const char*>::value,
ConvertTypeToId<const char[4], std::string, const char*>::value, // 实际应该是 1，判断时需用 decay(T)
TypeToId<decltype(0), float, long, double>::value,
ConvertTypeToId<decltype(0), float, long, double>::value, // 将匹配第一个 float，实际应该是 long
T_is_instantiation_of<in_place_type_t, in_place_type_t<int>>::value,
T_is_instantiation_of<in_place_type_t, in_place_index_t<1>>::value,
V_is_instantiation_of<in_place_index_t, in_place_index_t<1>>::value
// CheckAll<std::is_copy_constructible, A, int, B>::value
);
}
std::any
#include <any>
#include <cstdio>
#include <vector>
#include <iostream>
#define pc putchar
using std::cout;
using std::string;
using std::vector;
template<typename T>
std::ostream& operator << (std::ostream& out, const vector<T>& v) {
out << "[";
for (auto it = v.begin(); it != v.end(); it++) {
if (it != v.begin()) out << ", ";
out << *it;
}
out << "]";
return out;
}
class Any {
public:
Any(): data(nullptr) {}
Any(const Any& other) {
if (other.data) {
data = other.data->clone();
}
}
Any(Any&& other): data{other.data} {
other.data = nullptr;
}
Any& operator =(const Any& other) {
if (this == &other) {
return *this;
}
reset();
if (other.data) {
data = other.data->clone();
}
return *this;
}
Any& operator =(Any&& other) {
reset();
data = other.data;
other.data = nullptr;
return *this;
}
template <typename T,
typename = std::enable_if_t<!std::is_same_v<Any, std::decay_t<T>>>>
Any(T&& v): data(new Data<std::decay_t<T>>(std::forward<T>(v))) {}
// 注意 Data 的模板上不能带引用，不然就不能用Data<T>准确获取了。但为了完美转发，构造函数上的T还是要带引用
// 此外 Data 的成员 data 的类型也不能带引用，否则传左值时它就是 T&，会获取引用，而不是进行拷贝，可能导致悬垂引用！
// 但与 remove_reference 相比，decay 更合适，见 function
~Any() {
reset();
}
template <typename T>
T& any_cast() {
auto p = data == nullptr ? nullptr : dynamic_cast<Data<T>*>(data);
if (p == nullptr) {
throw std::bad_any_cast();
}
return p->data;
// return ((Data<T>*)data)->data;
}
void reset() noexcept {
delete data;
}
void swap(Any& other) noexcept {
std::swap(data, other.data);
}
const std::type_info& type() const noexcept {
return data ? data->type() : typeid(nullptr);
}
friend std::ostream& operator << (std::ostream& out, const Any& any);
private:
struct Base {
virtual ~Base() {}
virtual Base* clone() const = 0;
virtual const std::type_info& type() const noexcept = 0;
virtual std::ostream& print(std::ostream& out) = 0;
};
Base* data;
template <typename T>
struct Data: Base {
template <typename UT>
Data(UT&& v): data(std::forward<UT>(v)) {
static_assert(std::is_same_v<T, std::decay_t<UT>>);
}
// 为了实现完美转发，构造函数中的模板必须带引用；但类本身的模板不能带引用，所以只能写两个模板参数
Base* clone() const override {
return new Data<T>(*this);
}
const std::type_info& type() const noexcept override {
return typeid(T);
}
std::ostream& print(std::ostream& out) override { // 类型需要重载 operator <<
out << data;
return out;
}
T data;
};
};
std::ostream& operator << (std::ostream& out, const Any& any) {
if (any.data) {
any.data->print(out);
} else {
out << "null";
}
return out;
}
struct Test {
Test() { x = 0; debug && puts("Test()");}
~Test() { debug && printf("~Test(%d)\n", x);}
Test(const Test& o) { x = o.x; debug && puts("Test(const Test&)");}
Test(Test&& o) { x = o.x; o.x = 0; debug && puts("Test(&&)");}
int x;
static constexpr bool debug = false;
};
int main() {
if (true) {
vector<Any> vec{1, 2.0, 3.f, "abc", vector<Any>{'a', "str"}};
cout << vec << '\n';
vec[2] = vector<int>{3, 3};
cout << vec << '\n';
}
if (false) {
Any a = Test();
cout << a.any_cast<Test>().x << '\n'; // 0
}
if (false) {
Test t;
t.x = 1;
Any b = t;
cout << b.any_cast<Test>().x << '\n'; // 1
t.x = 2;
cout << b.any_cast<Test>().x << '\n'; // 1
b.any_cast<Test>().x *= -1;
Test t2 = b.any_cast<Test>();
cout << t2.x << '\n'; // -1
// copy
Any c = b;
Test& t3 = c.any_cast<Test>();
cout << t3.x << '\n'; // -1
t3.x --;
cout << c.any_cast<Test>().x << '\n'; // -2
Any d = std::move(c);
try {
cout << d.any_cast<Test>().x << '\n'; // -2
cout << c.any_cast<Test>().x << '\n'; // error
}
catch(const std::exception& e) {
std::cerr << e.what() << '\n';
}
}
if (true) {
Any a = 5;
Any b = 1.f;
Any c = std::vector<int>{1, 2};
cout << a.type().name() << '\n';
cout << b.type().name() << '\n';
cout << c.type().name() << '\n';
}
cout << "end\n";
}
std::function
#include <cstdio>
#include <iostream>
#include <functional>
using std::cout;
// class bad_function_call: public std::exception {
// virtual const char* what() const noexcept {
// return "bad function call";
// }
// };
template <typename>
class Function;
template <typename R, typename... Args>
class Function<R(Args...)> {
public:
Function(): callable(nullptr) {}
Function(const Function& other) {
if (other.callable) {
callable = other.callable->clone();
}
}
Function(Function&& other): callable(other.callable) { // 注意这里不要clone，直接获取值
other.callable = nullptr;
}
template <typename F,
typename = std::enable_if_t<!std::is_same_v<Function, std::decay_t<F>>>>
Function(F&& f): callable(new NormalCallable<std::decay_t<F>>(std::forward<F>(f))) {}
// 模板类型不能带引用，否则会产生悬垂引用，见 any
// 但去除引用后，NormalCallable 的 F 会被推导为原类型，赋值函数时将是函数类型
// 而数据成员的类型不能是函数类型。使用 decay 而非 remove_reference 刚好可做到这点（对于函数类型，会转为函数指针）
// 但是 decay 后 Function g = f; 会匹配到这个模板构造函数，而非 Function(const Function&)，除非加 enable_if 或 Function(Function&)
template <typename C, typename Func>
Function(Func C::* f): callable(new MemberFunctionPointer<C, Func>(std::forward<Func C::*>(f))) {}
~Function() {
delete callable;
}
operator bool() const noexcept {
return this->callable != nullptr;
}
R operator()(Args... args) {
if (static_cast<bool>(*this) == false) {
throw std::bad_function_call();
}
return callable->invoke(std::forward<Args>(args)...);
}
void swap(Function &other) noexcept {
std::swap(callable, other.callable);
}
private:
// 抽象基类，用于存储可调用对象的指针
class BaseCallable {
public:
virtual R invoke(Args... args) = 0;
virtual ~BaseCallable() {}
virtual BaseCallable* clone() const = 0;
};
BaseCallable* callable;
// 具体实现类，用于存储特定类型的可调用对象
// #1 存储普通函数指针、仿函数、lambda、bind
template <typename F>
class NormalCallable : public BaseCallable {
public:
template <typename T>
NormalCallable(T&& f) : func(std::forward<T>(f)) {
// 对于仿函数，F为仿函数类型，T为 F&& 或 F&
// 对于普通函数，F为函数指针，T为函数类型（可能带引用）
static_assert(std::is_same_v<F, std::decay_t<T>>);
}
R invoke(Args... args) override {
return func(std::forward<Args>(args)...);
}
BaseCallable* clone() const override {
return new NormalCallable(*this);
}
private:
F func;
};
// #2 存储函数成员指针
template <typename C, typename F>
class MemberFunctionPointer : public BaseCallable {
public:
MemberFunctionPointer(F C::*f) : func(f) {}
R invoke(Args... args) override {
return invokeImpl(args...);
}
template <typename... Args2>
R invokeImpl(C& object, Args2... args) {
return (object.*func)(std::forward<Args2>(args)...);
}
template <typename... Args2>
R invokeImpl(const C& object, Args2... args) {
return (object.*func)(std::forward<Args2>(args)...);
}
BaseCallable* clone() const override {
return new MemberFunctionPointer(*this);
}
private:
F C::*func;
};
};
struct Node {
Node(int x): x(x) {}
int f(int v) {
cout << "Node::f(" << v << ") x:" << x << '\n';
return x;
}
int const_f(int v) const {
cout << "Node::const_f(" << v << ") x:" << x << '\n';
return x;
}
int x;
};
struct Func {
int operator()(int x) {
return x + 1;
}
};
int add(int x) {
return x + 1;
}
int add2(int x, int y) {
return x + y;
}
int main() {
// #define Function std::function
// #1 存储普通函数指针
Function<int (int)> f_add = add;
cout << f_add(1) << '\n'; // 2
Function<int (int)> f_add_c = f_add;
cout << f_add_c(1) << '\n'; // 2
// 通过 clone 创建新的 callable
auto f_add2 = std::move(f_add);
cout << f_add2(2) << '\n'; // 3
// cout << f_add(2) << '\n'; // bad_function_call
// #2 存储成员函数指针
Node node{1};
Function<int (Node&, int)> fp = &Node::f; // 通过Node&实例调用（也可以是const Node&）
cout << fp(node, 2) << '\n'; // 1
Function<int (const Node&, int)> fpc = &Node::const_f; // 通过const Node&实例调用
cout << fpc(1, 2) << '\n'; // 1 隐式构造的右值可以绑定到const左值引用
// 通过 clone 创建新的 callable
auto fp2 = fp;
cout << fp2(node, 3) << '\n'; // 1
// #3 （不支持）存储数据成员指针
// Function<int& (Node&)> fr = &Node::x; // 也可以是 int (const Node&)
// cout << fr(node) << '\n'; // 1
// fr(node) = 3;
// cout << node.x << '\n'; // 3
// #4 存储仿函数
Function<int (int)> ff = Func();
cout << ff(3) << '\n'; // 4
// #5 存储lambda
int tmp = 1;
auto lam = [&tmp](int x) {
tmp += x;
return tmp;
};
Function<int (int)> f_lam = lam;
cout << f_lam(2) << '\n'; // 3
cout << tmp << '\n'; // 3
// #6 存储bind表达式
Function<int (int)> f_bind = std::bind(add2, 2, std::placeholders::_1);
cout << f_bind(3) << '\n'; // 5
}
std::