list.hpp

浏览该文件的文档.

/*
 * @Description: 列表类 头文件
 * @Version:
 * @Autor: dreamy-xay
 * @date: 2023-12-03
 * @LastEditors: dreamy-xay
 * @LastEditTime: 2024-03-06
 */
 
#ifndef COMMON_LIST_HPP
#define COMMON_LIST_HPP
 
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
 
#include "common/enum.h"
#include "common/macro.h"
#include "common/type.h"
 
namespace cm {
 
template <typename T>
class List : public std::vector<T> {
   public:
    using typename std::vector<T>::iterator;
    using typename std::vector<T>::const_iterator;
    using typename std::vector<T>::reverse_iterator;
    using typename std::vector<T>::const_reverse_iterator;
    using std::vector<T>::vector;
 
    List() = default;
    List(const List<T>& list) = default;
    List(const std::vector<T>& list);
    ~List() = default;
 
    List<T>& operator+=(const List<T>& list);
 
    template <typename U>
    friend List<U> operator+(const List<U>& list1, const List<U>& list2);
 
    template <typename U>
    friend std::ostream& operator<<(std::ostream& out, const List<U>& list);
 
    template <typename FUNC>
    List<T> Filter(const FUNC& func) const;
    template <typename U, typename FUNC>
    U Reduce(const FUNC& func, U initial_value = U{}) const;
    template <typename U = T, typename FUNC>
    List<U> Map(const FUNC& func) const;
 
    template <typename FUNC>
    List<T> MutFilter(const FUNC& func);
    template <typename U, typename FUNC>
    U MutReduce(const FUNC& func, U initial_value = U{});
    template <typename U = T, typename FUNC>
    List<U> MutMap(const FUNC& func);
 
    const_iterator Max() const;
    template <typename FUNC>
    const_iterator Max(const FUNC& func) const;
 
    const_iterator Min() const;
    template <typename FUNC>
    const_iterator Min(const FUNC& func) const;
 
    List<T>& Sort();
    template <typename FUNC>
    List<T>& Sort(const FUNC& func);
 
    iterator Order(size_t index);
    template <typename FUNC>
    iterator Order(size_t index, const FUNC& func);
 
    bool Include(const T& value) const;
    template <typename FUNC>
    bool Include(const FUNC& func) const;
 
    size_t Index(const T& value, size_t from_index = 0) const;
    template <typename FUNC>
    size_t Index(const FUNC& func, size_t from_index = 0) const;
    size_t LastIndex(const T& value, size_t from_index = INT_MAX) const;
    template <typename FUNC>
    size_t LastIndex(const FUNC& func, size_t from_index = INT_MAX) const;
 
    size_t Count(const T& value) const;
    template <typename FUNC>
    size_t Count(const FUNC& func) const;
 
    List<T>& Reverse();
 
    List<T>& Shuffle();
 
    List<T>& Fill(const T& value);
 
    List<T> Slice(size_t start, size_t end = UINT_MAX) const;
};
 
template <typename T>
inline List<T>::List(const std::vector<T>& list) : std::vector<T>(list) {}
 
template <typename T>
inline List<T>& List<T>::operator+=(const List<T>& list) {
    this->insert(this->end(), list.begin(), list.end());  // 插入list内容
 
    return *this;
}
 
template <typename U>
inline List<U> operator+(const List<U>& list1, const List<U>& list2) {
    List<U> new_list = list1;  // 新列表
 
    new_list.insert(new_list.end(), list2.begin(), list2.end());  // 插入 list2 内容
 
    return std::move(new_list);
}
 
template <typename U>
inline std::ostream& operator<<(std::ostream& out, const List<U>& list) {
    int list_len = list.size();  // 获取列表长度
 
    out << "[";  // 输出列表左括号
 
    if (list_len) {  // 如果列表内存在元素，则打印
        out << list[0];
        for (int i = 1; i < list_len; ++i)
            out << ", " << list[i];
    }
 
    out << "]";  // 输出列表右括号
 
    return out;
}
 
template <typename T>
template <typename FUNC>
inline List<T> List<T>::Filter(const FUNC& func) const {
    List<T> new_list;  // 新列表
 
    // 遍历所有项
    for (const T& item : *this)
        if (func(item))  // 如果不满足过滤条件则加入新列表
            new_list.emplace_back(item);
 
    return std::move(new_list);  // 返回过滤后的区间列表
}
 
template <typename T>
template <typename U, typename FUNC>
inline U List<T>::Reduce(const FUNC& func, U initial_value) const {
    // 遍历所有项
    for (const T& item : *this)
        initial_value = std::move(func(initial_value, item));  // 归并函数 func 每次的返回值
 
    return initial_value;  // 返回归并后的值
}
 
template <typename T>
template <typename U, typename FUNC>
inline List<U> List<T>::Map(const FUNC& func) const {
    List<U> new_list;  // 新列表
 
    // 遍历所有项
    for (const T& item : *this)
        new_list.emplace_back(func(item));
 
    return std::move(new_list);  // 返回重新映射后的区间列表
}
 
template <typename T>
template <typename FUNC>
inline List<T> List<T>::MutFilter(const FUNC& func) {
    List<T> new_list;  // 新列表
 
    // 遍历所有项
    for (T& item : *this)
        if (func(item))  // 如果不满足过滤条件则加入新列表
            new_list.emplace_back(item);
 
    return std::move(new_list);  // 返回过滤后的区间列表
}
 
template <typename T>
template <typename U, typename FUNC>
inline U List<T>::MutReduce(const FUNC& func, U initial_value) {
    // 遍历所有项
    for (T& item : *this)
        initial_value = std::move(func(initial_value, item));  // 归并函数 get_val 每次的返回值
 
    return initial_value;  // 返回归并后的值
}
 
template <typename T>
template <typename U, typename FUNC>
inline List<U> List<T>::MutMap(const FUNC& func) {
    List<U> new_list;  // 新列表
 
    // 遍历所有项
    for (T& item : *this)
        new_list.emplace_back(func(item));
 
    return std::move(new_list);  // 返回重新映射后的区间列表
}
 
template <typename T>
inline typename List<T>::const_iterator List<T>::Max() const {
    size_t list_len = this->size();  // 获取列表长度
 
    if (!list_len)  // 列表长度为0则直接返回结束迭代器
        return this->end();
 
    const_iterator max_value_iter = this->begin();  // 最大值的迭代器
 
    const_iterator cur_value_iter = max_value_iter + 1;  // 当前值的迭代器
    for (size_t i = 1; i < list_len; ++i, ++cur_value_iter)
        if (*max_value_iter < *cur_value_iter)
            max_value_iter = cur_value_iter;  // 更新最大值迭代器
 
    return max_value_iter;
}
 
template <typename T>
template <typename FUNC>
inline typename List<T>::const_iterator List<T>::Max(const FUNC& func) const {
    size_t list_len = this->size();  // 获取列表长度
 
    if (!list_len)  // 列表长度为0则直接返回结束迭代器
        return this->end();
 
    const_iterator max_value_iter = this->begin();  // 最大值的迭代器
 
    const_iterator cur_value_iter = max_value_iter + 1;  // 当前值的迭代器
    for (size_t i = 1; i < list_len; ++i, ++cur_value_iter)
        if (func(*max_value_iter, *cur_value_iter))
            max_value_iter = cur_value_iter;  // 更新最大值迭代器
 
    return max_value_iter;
}
 
template <typename T>
inline typename List<T>::const_iterator List<T>::Min() const {
    size_t list_len = this->size();  // 获取列表长度
 
    if (!list_len)  // 列表长度为0则直接返回结束迭代器
        return this->end();
 
    const_iterator min_value_iter = this->begin();  // 最小值的迭代器
 
    const_iterator cur_value_iter = min_value_iter + 1;  // 当前值的迭代器
    for (size_t i = 1; i < list_len; ++i, ++cur_value_iter)
        if (*cur_value_iter < *min_value_iter)
            min_value_iter = cur_value_iter;  // 更新最小值迭代器
 
    return min_value_iter;
}
 
template <typename T>
template <typename FUNC>
inline typename List<T>::const_iterator List<T>::Min(const FUNC& func) const {
    size_t list_len = this->size();  // 获取列表长度
 
    if (!list_len)  // 列表长度为0则直接返回结束迭代器
        return this->end();
 
    const_iterator min_value_iter = this->begin();  // 最小值的迭代器
 
    const_iterator cur_value_iter = min_value_iter + 1;  // 当前值的迭代器
    for (size_t i = 1; i < list_len; ++i, ++cur_value_iter)
        if (func(*cur_value_iter, *min_value_iter))
            min_value_iter = cur_value_iter;  // 更新最小值迭代器
 
    return min_value_iter;
}
 
template <typename T>
inline List<T>& List<T>::Sort() {
    std::sort(this->begin(), this->end());
 
    return *this;
}
 
template <typename T>
template <typename FUNC>
inline List<T>& List<T>::Sort(const FUNC& func) {
    std::sort(this->begin(), this->end(), func);
 
    return *this;
}
 
template <typename T>
inline typename List<T>::iterator List<T>::Order(size_t index) {
    List<T>::iterator end_iter = this->end();  // 结束迭代器
 
    // 如果序号大于等于列表项数，
    if (index >= this->size())
        return end_iter;
 
    List<T>::iterator begin_iter = this->begin();  // 开始迭代器
 
    // 归位第 index 个元素位置
    std::nth_element(begin_iter, begin_iter + index, end_iter);
 
    // 返回迭代器
    return begin_iter + index;
}
 
template <typename T>
template <typename FUNC>
inline typename List<T>::iterator List<T>::Order(size_t index, const FUNC& func) {
    List<T>::iterator end_iter = this->end();  // 结束迭代器
 
    // 如果序号大于等于列表项数，
    if (index >= this->size())
        return end_iter;
 
    List<T>::iterator begin_iter = this->begin();  // 开始迭代器
 
    // 归位第 index 个元素位置
    std::nth_element(begin_iter, begin_iter + index, end_iter, func);
 
    // 返回迭代器
    return begin_iter + index;
}
 
template <typename T>
inline bool List<T>::Include(const T& value) const {
    return this->Index(value) < this->size();
}
 
template <typename T>
template <typename FUNC>
inline bool List<T>::Include(const FUNC& func) const {
    return this->Index(func) < this->size();
}
 
template <typename T>
inline size_t List<T>::Index(const T& value, size_t from_index) const {
    size_t list_len = this->size();  // 列表长度
 
    // 从开始索引开始遍历整个列表
    for (size_t i = from_index; i < list_len; ++i)
        if ((*this)[i] == value)  // 找到指定值
            return i;
 
    return list_len;
}
 
template <typename T>
template <typename FUNC>
inline size_t List<T>::Index(const FUNC& func, size_t from_index) const {
    size_t list_len = this->size();  // 列表长度
 
    // 从开始索引开始遍历整个列表
    for (size_t i = from_index; i < list_len; ++i)
        if (func((*this)[i]))  // 找到指定值
            return i;
 
    return list_len;
}
 
template <typename T>
inline size_t List<T>::LastIndex(const T& value, size_t from_index) const {
    size_t list_len = this->size();  // 列表长度
 
    // 从开始索引开始遍历整个列表
    for (int i = std::min(int(list_len) - 1, int(from_index)); i >= 0; --i)
        if ((*this)[i] == value)  // 找到指定值
            return i;
 
    return list_len;
}
 
template <typename T>
template <typename FUNC>
inline size_t List<T>::LastIndex(const FUNC& func, size_t from_index) const {
    size_t list_len = this->size();  // 列表长度
 
    // 从开始索引开始遍历整个列表
    for (int i = std::min(int(list_len) - 1, int(from_index)); i >= 0; --i)
        if (func((*this)[i]))  // 找到指定值
            return i;
 
    return list_len;
}
 
template <typename T>
inline size_t List<T>::Count(const T& value) const {
    // 计数
    size_t count = 0;
 
    // 从开始索引开始遍历整个列表
    for (const T& item : *this)
        if (item == value)  // 如果值相等，计数器加1
            ++count;
 
    return count;
}
 
template <typename T>
template <typename FUNC>
inline size_t List<T>::Count(const FUNC& func) const {
    // 计数
    size_t count = 0;
 
    // 从开始索引开始遍历整个列表
    for (const T& item : *this)
        if (func(item))  // 如果值相等，计数器加1
            ++count;
 
    return count;
}
 
template <typename T>
inline List<T>& List<T>::Reverse() {
    List<T>& this_list = *this;
 
    size_t list_len = this->size();  // 列表长度
    size_t swap_len = list_len / 2;
 
    // 列表对半交换
    for (size_t i = 0; i < swap_len; ++i)
        std::swap(this_list[i], this_list[list_len - i - 1]);
 
    return this_list;
}
 
template <typename T>
inline List<T>& List<T>::Shuffle() {
    auto& this_list = *this;
    int list_len = this->size();  // 列表长度
 
    if (list_len <= 1)
        return this_list;
 
    // 随机种子
    std::srand((unsigned int)time(NULL));  // flawfinder: ignore
 
    for (size_t i = 0; i < list_len - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (list_len - i) + 1);
        std::swap(this_list[i], this_list[j]);
    }
 
    return this_list;
}
 
template <typename T>
inline List<T>& List<T>::Fill(const T& value) {
    // 遍历全部值设置为填充值
    for (T& item : *this)
        item = value;
 
    return *this;
}
 
template <typename T>
inline List<T> List<T>::Slice(size_t start, size_t end) const {
    const List<T>& this_list = *this;  // 列表本身
    List<T> new_list;                  // 提取的新列表
 
    size_t list_len = this->size();  // 列表长度
 
    // 结束位置最大不超过列表长度
    end = std::min(end, list_len - 1);
 
    // 根据起止信息从原列表中提取出一个新的列表
    for (size_t i = start; i < end; ++i)
        new_list.emplace_back(this_list[i]);
 
    return std::move(new_list);
}
 
}  // namespace cm
 
#endif