[C++]迭代器实现及二维链表实现
最近因为期末所以好久没更新了，最近会把一些积累的存货发出来
这章主要讲的是迭代器，那么什么是迭代器呢？
这篇文章各位可以和之前我发的二维链表实现对照起来看
我们知道，尽管不同容器的内部结构各异，但它们本质上都是用来存储大量数据的，换句话说，都是一串能存储多个数据的存储单元。因此，诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。
既然类似，完全可以利用泛型技术，将它们设计成适用所有容器的通用算法，从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置，它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。
这是泛型思维发展的必然结果，于是迭代器就产生了。
REFERENCE:http://c.biancheng.net/view/6675.html跳转
迭代器的种类
迭代器有很多种：正迭代器、逆迭代器、随机访问迭代器、双向迭代器等等
它们支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较
正向迭代器就是最常见的形式，可以通过++移动到下一个元素，反向迭代器则相反，双向迭代器顾名思义支持前进和后退操作，值得一提的是，这里前进代表移动到下一个元素，而后退意味着移动到前一个元素
随机访问迭代器功能更加强大，支持前后移动i个单位元素
下面以我的作业为例展示迭代器的实现方法
.hpp文件
我们需要将实现写在doubll2d-impl.hpp中，我不知道为什么这么include不会报错，哪位懂的老哥可以在评论区介绍一下
#ifndef _HW7_DOUBLL2D_HPP_
#define _HW7_DOUBLL2D_HPP_
#include <cstddef>
#include <iterator>
#include <functional>
template<typename T>
class doubll2d;
// Detailed implementation of doubll2d.
// Namespaces are used to prevent users from directly using them.
namespace __detail {
// Helper class for creating iterable from two iterators.
// You do not need to implement or use this.
template<typename T>
class iterable {
private:
T begin_;
T end_;
public:
iterable(T begin, T end) : begin_{begin}, end_{end} {}
T begin() const { return begin_; }
T end() const { return end_; }
};
template<typename T>
iterable<T> make_iterable(T begin, T end) { return iterable<T>{begin, end}; }
// Helper class to create reverse iterator from normal iterator.
// You do not need to implement or use this.
template<class I>
class reverse_iter
: public std::iterator<typename std::iterator_traits<I>::iterator_category,
typename std::iterator_traits<I>::value_type,
typename std::iterator_traits<I>::difference_type,
typename std::iterator_traits<I>::pointer,
typename std::iterator_traits<I>::reference> {
public:
explicit reverse_iter(I iter) : inner{iter} {}
// reference operator (implemented)
typename reverse_iter::reference operator*() { return *inner; }
// pointer operator (implemented)
typename reverse_iter::pointer operator->() { return &*inner; }
// self increment operator (implemented)
reverse_iter &operator++() {
--inner;
return *this;
}
reverse_iter operator++(int) { return reverse_iter{inner--}; }
// self decrement operator (implemented)
reverse_iter &operator--() {
++inner;
return *this;
}
reverse_iter operator--(int) { return reverse_iter{inner++}; }
// comparison operator (implemented)
bool operator==(const reverse_iter &other) { return inner == other.inner; }
bool operator!=(const reverse_iter &other) { return inner != other.inner; }
private:
I inner;
};
// List node, you do not need to implement this
template<typename T>
class list_node {
public:
// Initialize the node with a value (implemented)
explicit list_node(const T &value) :
left{nullptr}, right{nullptr}, up{nullptr}, down{nullptr}, data{value} {}
// Copy constructor (compiler generated)
list_node(const list_node &other) = default;
// Destructor (compiler generated)
~list_node() = default;
// Copy assignment operator (compiler generated)
list_node &operator=(const list_node &rhs) = default;
// adjacent nodes
list_node *left;
list_node *right;
list_node *up;
list_node *down;
// Data of the node
T data;
};
// Iterator of the list element in some row.
template<typename T>
class list_row_elem_iter : public std::iterator<std::bidirectional_iterator_tag, T> {
public:
explicit list_row_elem_iter(list_node<T> *inner) : inner{inner} {}
// reference operator (implement this)
typename list_row_elem_iter::reference operator*();
// pointer operator (implement this)
typename list_row_elem_iter::pointer operator->();
// self increment operator (implement this)
// move to the right element
list_row_elem_iter &operator++();
list_row_elem_iter operator++(int);
// self decrement operator (implement this)
// move to the left element
list_row_elem_iter &operator--();
list_row_elem_iter operator--(int);
// comparison operator (implement this)
bool operator==(const list_row_elem_iter &other);
bool operator!=(const list_row_elem_iter &other);
private:
list_node<T> *inner;
// this allows you get the inner node inside this iter
friend class doubll2d<T>;
};
// Iterator of the row in the list
template<typename T>
class list_row_iter : public std::iterator<std::bidirectional_iterator_tag, list_row_iter<T>> {
public:
// Type renaming
using iterator = list_row_elem_iter<T>;
using reverse_iterator = __detail::reverse_iter<iterator>;
list_row_iter(list_node<T> *left, list_node<T> *right) : left{left}, right{right} {}
// the leftmost iterator of this row (implement this)
iterator begin();
// the iterator next to the rightmost element in this row (implement this)
iterator end();
// the `reverse_iterator` of the rightmost element in this row (implement this)
reverse_iterator rbegin();
// the `reverse_iterator` before the leftmost element in this row (implement this)
reverse_iterator rend();
iterable<reverse_iterator> riterable() { return make_iterable(rbegin(), rend()); }
// reference operator (implement this)
typename list_row_iter::reference operator*();
// pointer operator (implement this)
typename list_row_iter::pointer operator->();
// self increment operator (implement this)
// move to the row below
list_row_iter &operator++();
list_row_iter operator++(int);
// self decrement operator (implement this)
// move to the row above
list_row_iter &operator--();
list_row_iter operator--(int);
// comparison operator (implement this)
bool operator==(const list_row_iter &other);
bool operator!=(const list_row_iter &other);
private:
list_node<T> *left; // leftmost element in the row
list_node<T> *right; // rightmost element in the row
};
// Iterator of the list element in some column.
template<typename T>
class list_col_elem_iter : public std::iterator<std::bidirectional_iterator_tag, T> {
public:
// Type renaming
explicit list_col_elem_iter(list_node<T> *inner) : inner{inner} {}
// reference operator (implement this)
typename list_col_elem_iter::reference operator*();
// pointer operator (implement this)
typename list_col_elem_iter::pointer operator->();
// self increment operator (implement this)
// move to the element below
list_col_elem_iter &operator++();
list_col_elem_iter operator++(int);
// self decrement operator (implement this)
// move to the element above
list_col_elem_iter &operator--();
list_col_elem_iter operator--(int);
// comparison operator (implement this)
bool operator==(const list_col_elem_iter &other);
bool operator!=(const list_col_elem_iter &other);
private:
list_node<T> *inner;
// this allows you get the inner node inside this iter
friend class doubll2d<T>;
};
// Iterator of the column in the list
template<typename T>
class list_col_iter : public std::iterator<std::bidirectional_iterator_tag, list_col_iter<T>> {
public:
// Type renaming
using iterator = list_col_elem_iter<T>;
using reverse_iterator = __detail::reverse_iter<iterator>;
list_col_iter(list_node<T> *up, list_node<T> *down) : up{up}, down{down} {}
// the top iterator of this column (implement this)
iterator begin();
// the iterator below the bottom element in this column (implement this)
iterator end();
// the `reverse_iterator` of the bottom element in this column (implement this)
reverse_iterator rbegin();
// the `reverse_iterator` above the top element in this column (implement this)
reverse_iterator rend();
iterable<reverse_iterator> riterable() { return make_iterable(rbegin(), rend()); }
// reference operator (implement this)
typename list_col_iter::reference operator*();
// pointer operator (implement this)
typename list_col_iter::pointer operator->();
// self increment operator (implement this)
// move to the next column
list_col_iter &operator++();
list_col_iter operator++(int);
// self decrement operator (implement this)
// move to the previous column
list_col_iter &operator--();
list_col_iter operator--(int);
// comparison operator (implement this)
bool operator==(const list_col_iter &other);
bool operator!=(const list_col_iter &other);
private:
list_node<T> *up; // top element in the column
list_node<T> *down; // bottom element in the column
};
}
// 2D Doubly linked list class
template<typename T>
class doubll2d {
public:
// Type renaming
using size_type = size_t;
using row_iter = __detail::list_row_iter<T>;
using col_iter = __detail::list_col_iter<T>;
using row_riter = __detail::reverse_iter<row_iter>;
using col_riter = __detail::reverse_iter<col_iter>;
// Default constructor
doubll2d() :
up_left{nullptr}, up_right{nullptr},
down_left{nullptr}, down_right{nullptr},
dim_row{0}, dim_col{0} {}
// Copy and move constructor are deleted
doubll2d(const doubll2d &other) = delete;
doubll2d(doubll2d &&other) = delete;
// Destructor
~doubll2d() { clear(); }
// Copy and move assignment operator are deleted
doubll2d &operator=(const doubll2d &other) = delete;
doubll2d &operator=(doubll2d &&other) = delete;
// The number of rows in the list
size_type get_dim_row() const { return dim_row; }
// The number of columns in the list
size_type get_dim_col() const { return dim_col; }
// Iterator to the first (top) row (implement this)
row_iter row_begin();
// Iterator below the last (bottom) row (implement this)
row_iter row_end();
__detail::iterable<row_iter> row_iterable() {
return __detail::make_iterable(row_begin(), row_end());
}
// `reverse_iterator` to the last (bottom) row (implement this)
row_riter row_rbegin();
// `reverse_iterator` above the first (top) row (implement this)
row_riter row_rend();
__detail::iterable<row_riter> row_riterable() {
return __detail::make_iterable(row_rbegin(), row_rend());
}
// Iterator to the first (leftmost) column (implement this)
col_iter col_begin();
// Iterator after the last (rightmost) column (implement this)
col_iter col_end();
__detail::iterable<col_iter> col_iterable() {
return __detail::make_iterable(col_begin(), col_end());
}
// `reverse_iterator` to the last (rightmost) column (implement this)
col_riter col_rbegin();
// `reverse_iterator` before the first (leftmost) column (implement this)
col_riter col_rend();
__detail::iterable<col_riter> col_riterable() {
return __detail::make_iterable(col_rbegin(), col_rend());
}
// Insert a new row in the list below the row referenced by `cursor`.
// The data stores from `input_iter` `begin` to `end`. (implement this)
//
// Remember, our 2D doubly linked list should always be a rectangular. When the length
// of data is shorter than it should be, you should fill the rest part by default value of T.
// Additionally, it is okay that the length of data is longer than needed, in this case
// you should make use of the `dim_col` items from `begin` and ignore the extra elements.
//
// If the list is empty, you should insert the whole data from `begin` to `end`.
// If the list is empty and `begin` equals to `end`, do nothing and return `row_end()`.
//
// If the cursor equals to `row_end()` operator, insert the data above the origin first row.
//
// Return the iter of the row inserted.
template<typename input_iter>
row_iter insert_row(row_iter cursor, input_iter begin, input_iter end);
// Insert a new column in the list after the column referenced by `cursor`.
// The data stores from `input_iter` `begin` to `end`. (implement this)
//
// Remember, our 2D doubly linked list should always be a rectangular. When the length
// of data is shorter than it should be, you should fill the rest part by default value of T.
// Additionally, it is okay that the length of data is longer than needed, in this case
// you should make use of the first `dim_row` items from `begin` and ignore the extra elements.
//
// If the list is empty, you should insert the whole data from `begin` to `end`.
// If the list is empty and `begin` equals to `end`, do nothing and return `col_end()`.
//
// If the cursor is `col_end()` operator, insert the data before the origin first column.
//
// Return the iter of the column inserted.
template<typename input_iter>
col_iter insert_col(col_iter cursor, input_iter begin, input_iter end);
// Delete the row where the given `cursor` reference to and returns the `row_iter` above
// the given `cursor`. If the first row is deleted, then return the `row_iter`
// below the given `cursor`. If the deleted row is the only row in the list,
// return `row_end()`. (implement this)
//
// If the cursor is `row_end()` operator, do nothing and return `row_end()` operator.
// If the last row in list is deleted, the size of the list should be set to 0*0.
row_iter delete_row(row_iter cursor);
// Delete the column where the given `cursor` reference to and returns the `col_iter` left to
// the given `cursor`. If the first column is deleted, then return the `col_iter`
// right to the given `cursor`. If the deleted column is the only column in the list,
// return `col_end()`. (implement this)
//
// If the cursor is `col_end()` operator, do nothing and return `col_end()` operator.
// If the last column in list is deleted, the size of the list should be set to 0*0.
col_iter delete_col(col_iter cursor);
// Clear all the nodes in the list (implement this)
void clear();
// This reduce() implementation takes a reducer function and an initial value
// for the accumulator. For each iterable item, the reducer is called, passing
// it the accumulator and the current list element.
//
// The return value is assigned to the accumulator. When it's finished applying the
// reducer to all of the values in the list, the accumulated value is returned.
template<class R>
R reduce(std::function<R(R, const T &)> fn, R init);
private:
__detail::list_node<T> *up_left; // top-left element
__detail::list_node<T> *up_right; // top-right element
__detail::list_node<T> *down_left; // bottom-left element
__detail::list_node<T> *down_right; // bottom-right element
size_t dim_row;
size_t dim_col;
};
#include "doubll2d-impl.hpp"
#endif // _HW7_DOUBLL2D_HPP_
doubll2d-impl.hpp
刚开始我还在犹豫怎么写函数之前一段冗长的声明，但是VSC好像有这个功能，只要将鼠标移在上面就可以显示出来，像这样，真的省了我很多时间
迭代器实现
我先将Insert以上的函数给出
完全按照template的顺序，如果看不懂前面这段冗长的声明可以直接在上面doubll2d.hpp中找，这里面有一些简单的迭代器实现，关于正向迭代器和逆迭代器的实现和各个操作符的实现各位均可以在下面找到
template<class T>
typename __detail::list_row_elem_iter<T>::reference __detail::list_row_elem_iter<T>::operator*()
{
return inner->data;
}
template<class T>
typename __detail::list_row_elem_iter<T>::pointer __detail::list_row_elem_iter<T>::operator->()
{
return &(inner->data);
}
template<class T>
typename __detail::list_row_elem_iter<T> &__detail::list_row_elem_iter<T>::operator++()
{
if(!this->inner)
{
return *this;
}
inner = inner->right;
return *this;
}
template<class T>
typename __detail::list_row_elem_iter<T> __detail::list_row_elem_iter<T>::operator++(int)
{
if(!this->inner)
{
return *this;
}
list_row_elem_iter tmp(*this);
inner = inner->right;
return tmp;
}
template<class T>
typename __detail::list_row_elem_iter<T> &__detail::list_row_elem_iter<T>::operator--()
{
if(!this->inner)
{
return *this;
}
inner = inner->left;
return *this;
}
template<class T>
typename __detail::list_row_elem_iter<T> __detail::list_row_elem_iter<T>::operator--(int)
{
if(!this->inner)
{
return *this;
}
list_row_elem_iter tmp(*this);
inner = inner->left;
return tmp;
}
template<class T>
bool __detail::list_row_elem_iter<T>::operator==(const __detail::list_row_elem_iter<T> &other)
{
if (inner == other.inner)
{
return true;
}
return false;
}
template<class T>
bool __detail::list_row_elem_iter<T>::operator!=(const __detail::list_row_elem_iter<T> &other)
{
if (inner == other.inner)
{
return false;
}
return true;
}
//implementation of list_row_iter
template<class T>
typename __detail::list_row_elem_iter<T> __detail::list_row_iter<T>::begin()
{
return typename __detail::list_row_elem_iter<T>::list_row_elem_iter(left);
}
template<class T>
typename __detail::list_row_elem_iter<T> __detail::list_row_iter<T>::end()
{
if(!right)
{
return typename __detail::list_row_elem_iter<T>::list_row_elem_iter(right);
}
return typename __detail::list_row_elem_iter<T>::list_row_elem_iter(right->right);
}
template<class T>
typename __detail::reverse_iter<__detail::list_row_elem_iter<T>> __detail::list_row_iter<T>::rbegin()
{
return typename __detail::reverse_iter<__detail::list_row_elem_iter<T>>(__detail::list_row_elem_iter<T>(right));
}
//typename __detail::reverse_iter<list_col_elem_iter<T>>::reverse_iter(__detail::list_col_elem_iter<T>::list_col_elem_iter(up->up));
template<class T>
__detail::reverse_iter<__detail::list_row_elem_iter<T>> __detail::list_row_iter<T>::rend()
{
if(!left)
{
return typename __detail::reverse_iter<__detail::list_row_elem_iter<T>>(__detail::list_row_elem_iter<T>(left));
}
return typename __detail::reverse_iter<__detail::list_row_elem_iter<T>>(__detail::list_row_elem_iter<T>(left->left));
}
template<class T>
typename __detail::list_row_iter<T>::reference __detail::list_row_iter<T>::operator*()
{
return *this;
}
template<class T>
typename __detail::list_row_iter<T>::pointer __detail::list_row_iter<T>::operator->()
{
return this;
}
template<class T>
typename __detail::list_row_iter<T> &__detail::list_row_iter<T>::operator++()
{
if(!this->left)
{
return *this;
}
left = left->down;
right = right->down;
return *this;
}
template<class T>
typename __detail::list_row_iter<T> __detail::list_row_iter<T>::operator++(int)
{
if(!this->left)
{
return *this;
}
list_row_iter tmp(*this);
left = left->down;
right = right->down;
return tmp;
}
template<class T>
typename __detail::list_row_iter<T> &__detail::list_row_iter<T>::operator--()
{
if(!this->left)
{
return *this;
}
left = left->up;
right = right->up;
return *this;
}
template<class T>
typename __detail::list_row_iter<T> __detail::list_row_iter<T>::operator--(int)
{
if(!this->left)
{
return *this;
}
list_row_iter tmp(*this);
left = left->up;
right = right->up;
return tmp;
}
template<class T>
bool __detail::list_row_iter<T>::operator==(const __detail::list_row_iter<T> &other)
{
if(left==other.left && right==other.right)
{
return true;
}
return false;
}
template<class T>
bool __detail::list_row_iter<T>::operator!=(const __detail::list_row_iter<T> &other)
{
if(left==other.left && right==other.right)
{
return false;
}
return true;
}
//list_col_elem_iter
template<class T>
typename __detail::list_col_elem_iter<T>::reference __detail::list_col_elem_iter<T>::operator*()
{
return inner->data;
}
template<class T>
typename __detail::list_col_elem_iter<T>::pointer __detail::list_col_elem_iter<T>::operator->()
{
return &(inner->data);
}
template<class T>
typename __detail::list_col_elem_iter<T> &__detail::list_col_elem_iter<T>::operator++()
{
if(!this->inner)
{
return *this;
}
inner = inner->down;
return *this;
}
template<class T>
typename __detail::list_col_elem_iter<T> __detail::list_col_elem_iter<T>::operator++(int)
{
if(!this->inner)
{
return *this;
}
list_col_elem_iter tmp(*this);
inner = inner->down;
return tmp;
}
template<class T>
typename __detail::list_col_elem_iter<T> &__detail::list_col_elem_iter<T>::operator--()
{
if(!this->inner)
{
return *this;
}
inner = inner->up;
return *this;
}
template<class T>
typename __detail::list_col_elem_iter<T> __detail::list_col_elem_iter<T>::operator--(int)
{
if(!this->inner)
{
return *this;
}
list_col_elem_iter tmp(*this);
inner = inner->up;
return tmp;
}
template<class T>
bool __detail::list_col_elem_iter<T>::operator==(const __detail::list_col_elem_iter<T> &other)
{
if(inner==other.inner)
{
return true;
}
return false;
}
template<class T>
bool __detail::list_col_elem_iter<T>::operator!=(const __detail::list_col_elem_iter<T> &other)
{
if(inner==other.inner)
{
return false;
}
return true;
}
//list_col_iter
template<class T>
typename __detail::list_col_elem_iter<T> __detail::list_col_iter<T>::begin()
{
return typename __detail::list_col_elem_iter<T>::list_col_elem_iter(up);
}
template<class T>
__detail::list_col_elem_iter<T> __detail::list_col_iter<T>::end()
{
if(!down)
{
return typename __detail::list_col_elem_iter<T>::list_col_elem_iter(down);
}
return typename __detail::list_col_elem_iter<T>::list_col_elem_iter(down->down);
}
template<class T>
__detail::reverse_iter<__detail::list_col_elem_iter<T>> __detail::list_col_iter<T>::rbegin()
{
return typename __detail::reverse_iter<__detail::list_col_elem_iter<T>>(__detail::list_col_elem_iter<T>(down));
}
template<class T>
__detail::reverse_iter<__detail::list_col_elem_iter<T>> __detail::list_col_iter<T>::rend()
{
if(!up)
{
return typename __detail::reverse_iter<__detail::list_col_elem_iter<T>>(__detail::list_col_elem_iter<T>(up));
}
return typename __detail::reverse_iter<__detail::list_col_elem_iter<T>>(__detail::list_col_elem_iter<T>(up->up));
}
template<class T>
typename __detail::list_col_iter<T>::reference __detail::list_col_iter<T>::operator*()
{
return *this;
}
template<class T>
typename __detail::list_col_iter<T>::pointer __detail::list_col_iter<T>::operator->()
{
return this;
}
template<class T>
__detail::list_col_iter<T> &__detail::list_col_iter<T>::operator++()
{
if(!this->up)
{
return *this;
}
up = up->right;
down = down->right;
return *this;
}
template<class T>
__detail::list_col_iter<T> __detail::list_col_iter<T>::operator++(int)
{
if(!this->up)
{
return *this;
}
list_col_iter tmp(*this);
up = up->right;
down = down->right;
return tmp;
}
template<class T>
__detail::list_col_iter<T> &__detail::list_col_iter<T>::operator--()
{
if(!this->up)
{
return *this;
}
up = up->left;
down = down->left;
return *this;
}
template<class T>
__detail::list_col_iter<T> __detail::list_col_iter<T>::operator--(int)
{
if(!this->up)
{
return *this;
}
list_col_iter tmp(*this);
up = up->left;
down = down->left;
return *this;
}
template<class T>
bool __detail::list_col_iter<T>::operator==(const __detail::list_col_iter<T> &other)
{
if(up==other.up && down==other.down)
{
return true;
}
return false;
}
template<class T>
bool __detail::list_col_iter<T>::operator!=(const __detail::list_col_iter<T> &other)
{
if(up==other.up && down==other.down)
{
return false;
}
return true;
}
//doubll2d
template<class T>
__detail::list_row_iter<T> doubll2d<T>::row_begin()
{
return typename __detail::list_row_iter<T>::list_row_iter(up_left,up_right);
}
template<class T>
__detail::list_row_iter<T> doubll2d<T>::row_end()
{
if(dim_col==0||dim_row==0)
{
return typename __detail::list_row_iter<T>::list_row_iter(down_left,down_right);
}
return typename __detail::list_row_iter<T>::list_row_iter(down_left->down,down_right->down);
}
template<class T>
__detail::reverse_iter<__detail::list_row_iter<T>> doubll2d<T>::row_rbegin()
{
return typename __detail::reverse_iter<__detail::list_row_iter<T>>(__detail::list_row_iter<T>(down_left,down_right));
}
//typename __detail::reverse_iter<list_col_elem_iter<T>>::reverse_iter(__detail::list_col_elem_iter<T>::list_col_elem_iter(up->up));
template<class T>
__detail::reverse_iter<__detail::list_row_iter<T>> doubll2d<T>::row_rend()
{
if(!up_left)
{
return typename __detail::reverse_iter<__detail::list_row_iter<T>>(__detail::list_row_iter<T>(up_left,up_right));
}
return typename __detail::reverse_iter<__detail::list_row_iter<T>>(__detail::list_row_iter<T>(up_left->up,up_right->up));
}
template<class T>
__detail::list_col_iter<T> doubll2d<T>::col_begin()
{
return typename __detail::list_col_iter<T>::list_col_iter(up_left,down_left);
}
template<class T>
__detail::list_col_iter<T> doubll2d<T>::col_end()
{
if(!up_right)
{
return typename __detail::list_col_iter<T>::list_col_iter(up_right,down_right);
}
return typename __detail::list_col_iter<T>::list_col_iter(up_right->right,down_right->down);
}
template<class T>
__detail::reverse_iter<__detail::list_col_iter<T>> doubll2d<T>::col_rbegin()
{
return typename __detail::reverse_iter<__detail::list_col_iter<T>>(__detail::list_col_iter<T>(up_right,down_right));
}
template<class T>
__detail::reverse_iter<__detail::list_col_iter<T>> doubll2d<T>::col_rend()
{
if(!up_left)
{
return typename __detail::reverse_iter<__detail::list_col_iter<T>>(__detail::list_col_iter<T>(up_left,down_left));
}
return typename __detail::reverse_iter<__detail::list_col_iter<T>>(__detail::list_col_iter<T>(up_left->left,down_left->left));
}
insert-row insert-col
这个函数比较复杂，所以我单独列出来写，本来我写了300多行，但是好像逻辑混乱而冗长，我将代码重构了一下，只写了150多行，并且非常清晰
template<class T>
template<class input_iter>
__detail::list_row_iter<T> doubll2d<T>::insert_row(__detail::list_row_iter<T> cursor, input_iter begin, input_iter end)
{
if(dim_row == 0 && begin == end) // If the list is empty and `begin` equals to `end`, do nothing and return `row_end()`.
{
return row_end();
}
//below list not empty or begin != end
//first: list empty but begin != end
__detail::list_node<T> *itr ;
__detail::list_node<T> *prev = nullptr;
__detail::list_node<T> *head;
__detail::list_node<T> *tail;
size_t index = 0;
if(dim_row == 0 && begin != end)
{
while(begin!=end)
{
itr = new __detail::list_node<T>(*begin);
if(index == 0)// left right relation
{
itr->left = nullptr;
head = itr;
}
else{
itr->left = prev;
prev->right = itr;
}
itr->up = nullptr;
itr->down = nullptr;
prev = itr;
index++;
begin++;
}
prev->right = nullptr;
dim_col = index;
dim_row = 1;
tail = prev;
up_left = head;
down_left = head;
up_right = tail;
down_right = tail;
return row_iter(head,tail);
}
//below are list not empty
//__detail::list_node<T> *itr = cursor.begin().inner;
int flag = 0; // flag 1: begin==end insert defult 0: begin!=defult
int flag_1 = 0; //flag_1 0:middle 1:top 2:bottom
//int flag_2 = 0; //flag_2 0:length <= dim_col 1:length > dim_col
if(begin == end)
{
flag = 1;
}
__detail::list_node<T> *ptr = cursor.begin().inner;
//__detail::list_node<T> *prev_head = itr->up;
//__detail::list_node<T> *prev_tail = nullptr;
//__detail::list_node<T> *next_head = itr->down;
//__detail::list_node<T> *next_tail = nullptr;
__detail::list_node<T> *first_line = up_left;
__detail::list_node<T> *last_line = down_left;
if(cursor == row_end())//insert first row
{
flag_1 = 1;
}
if(ptr == down_left)//insert below last row
{
flag_1 = 2;
}
if(flag_1 == 1){
ptr = up_left;
}
while((ptr != nullptr))//when insert in the first row notice that ptr is nullptr
{
if(begin == end){//start insert defult
flag = 1;
}
//determine which kind of node to generate
if(flag == 0)//begin != end
{
itr = new __detail::list_node<T>(*begin);
}
else{
itr = new __detail::list_node<T>(T());
}
//determine head and tail
if(index == 0){
head = itr;
}
if(index == dim_col -1){//dim_col is the determonant of whether to stop not ptr->right
tail = itr;
}
//determine leftmost or middle or rightmost left right relation
if(ptr->left == nullptr){//leftmost
itr->left = nullptr;
}
if(ptr->right == nullptr){//rightmost
itr->right = nullptr;
if(ptr->left !=nullptr){// to avoid the possibility of only one col both leftmost and rightmost
prev->right = itr;
itr->left = prev;
}
}
if(ptr->left!=nullptr && ptr->right!=nullptr){//middle
itr->left = prev;
prev->right = itr;
}
//determine which section to insert up down relation
if(flag_1 == 0)//insert middle
{
ptr->down->up = itr;
itr->down = ptr->down;
itr->up = ptr;
ptr->down = itr;
}
if(flag_1 == 1){//insert top
itr->up = nullptr;
itr->down = first_line;
first_line->up = itr;
if(index == 0){
up_left = itr;
}
if(index == dim_col - 1){
up_right = itr;
}
first_line = first_line->right;
}
if(flag_1==2){//insert bottom
itr->down = nullptr;
itr->up = last_line;
last_line->down = itr;
if(index == 0){
down_left = itr;
}
if(index == dim_col - 1){
down_right = itr;
}
last_line = last_line->right;
}
prev = itr;
ptr = ptr->right;
index++;
begin++;
}
dim_row+=1;
return row_iter(head,tail);
}
template<class T>
template<class input_iter>
__detail::list_col_iter<T> doubll2d<T>::insert_col(__detail::list_col_iter<T> cursor, input_iter begin, input_iter end)
{
if(dim_col == 0 && begin == end) // If the list is empty and `begin` equals to `end`, do nothing and return `row_end()`.
{
return col_end();
}
//below list not empty or begin != end
//first: list empty but begin != end
__detail::list_node<T> *itr ;
__detail::list_node<T> *prev = nullptr;
__detail::list_node<T> *head;
__detail::list_node<T> *tail;
size_t index = 0;
if(dim_col == 0 && begin != end)
{
while(begin!=end)
{
itr = new __detail::list_node<T>(*begin);
if(index == 0)// left right relation
{
itr->up = nullptr;
head = itr;
}
else{
itr->up = prev;
prev->down = itr;
}
itr->left = nullptr;
itr->right = nullptr;
prev = itr;
index++;
begin++;
}
prev->down = nullptr;
dim_row = index;
dim_col = 1;
tail = prev;
up_left = head;
up_right = head;
down_left = tail;
down_right = tail;
return col_iter(head,tail);
}
//below are list not empty
//__detail::list_node<T> *itr = cursor.begin().inner;
int flag = 0; // flag 1: begin==end insert defult 0: begin!=defult
int flag_1 = 0; //flag_1 0:middle 1:leftmost 2:rightmost
//int flag_2 = 0; //flag_2 0:length <= dim_row 1:length > dim_row
if(begin == end)
{
flag = 1;
}
__detail::list_node<T> *ptr = cursor.begin().inner;
//__detail::list_node<T> *prev_head = itr->up;
//__detail::list_node<T> *prev_tail = nullptr;
//__detail::list_node<T> *next_head = itr->down;
//__detail::list_node<T> *next_tail = nullptr;
__detail::list_node<T> *first_col = up_left;
__detail::list_node<T> *last_col = up_right;
if(cursor == col_end())//insert first row
{
flag_1 = 1;
}
if(ptr == up_right)//insert after last col
{
flag_1 = 2;
}
if(flag_1 == 1){
ptr = up_left;
}
while((ptr != nullptr))//when insert in the first row notice that ptr is nullptr
{
if(begin == end){//start insert defult
flag = 1;
}
//determine which kind of node to generate
if(flag == 0)//begin != end
{
itr = new __detail::list_node<T>(*begin);
}
else{
itr = new __detail::list_node<T>(T());
}
//determine head and tail
if(index == 0){
head = itr;
}
if(index == dim_row -1){//dim_col is the determonant of whether to stop not ptr->right
tail = itr;
}
//determine leftmost or middle or rightmost left right relation
if(ptr->up == nullptr){//upmost
itr->up = nullptr;
}
if(ptr->down == nullptr){//downmost
itr->down = nullptr;
if(ptr->up !=nullptr){// to avoid the possibility of only one col both leftmost and rightmost
prev->down = itr;
itr->up = prev;
}
}
if(ptr->up!=nullptr && ptr->down!=nullptr){//middle
itr->up = prev;
prev->down = itr;
}
//determine which section to insert up down relation
if(flag_1 == 0)//insert middle
{
ptr->right->left = itr;
itr->right = ptr->right;
itr->left = ptr;
ptr->right = itr;
}
if(flag_1 == 1){//insert leftmost
itr->left = nullptr;
itr->right = first_col;
first_col->left = itr;
if(index == 0){
up_left = itr;
}
if(index == dim_row - 1){
down_left = itr;
}
first_col = first_col->down;
}
if(flag_1==2){//insert rightmost
itr->right = nullptr;
itr->left = last_col;
last_col->right = itr;
if(index == 0){
up_right = itr;
}
if(index == dim_row - 1){
down_right = itr;
}
last_col = last_col->down;
}
prev = itr;
ptr = ptr->down;
index++;
begin++;
}
dim_col+=1;
return col_iter(head,tail);
}
delete-row delete-col
关于这个函数我有两种写法，都是对的，我这里将第二份给注释起来
template<class T>
__detail::list_row_iter<T> doubll2d<T>::delete_row(__detail::list_row_iter<T> cursor)
{
if(cursor == row_end() || dim_row==0)//do nothing and return `row_end()` operator
{
return row_end();
}
__detail::list_row_elem_iter<T> node_buffer = cursor.begin();//the first node in the row to be deleted
__detail::list_node<T> *prev;
size_t index = 0;
prev = nullptr;
if(node_buffer.inner == up_left && dim_row==1)//delete last row
{
while(node_buffer != cursor.end())
{
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
}
delete prev;
up_left = nullptr;
up_right = nullptr;
down_left = nullptr;
down_right = nullptr;
//delete node_buffer.inner;
dim_row = 0;
dim_col = 0;
return row_end();
}
if(node_buffer.inner == up_left)//delete first but not last row
{
cursor++;
__detail::list_row_elem_iter<T> down_node = cursor.begin();
up_left = down_node.inner;
while(node_buffer != cursor.end())
{
down_node.inner->up = nullptr;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
down_node++;
}
up_right = prev->down;
delete prev;
//delete node_buffer.inner;
//down_node.inner->up = nullptr;
dim_row-=1;
return cursor;
}
if(node_buffer.inner == down_left)//delete bottom but not last row;
{
cursor--;
__detail::list_row_elem_iter<T> up_node = cursor.begin();
down_left = up_node.inner;
while(node_buffer != cursor.end())
{
up_node.inner->down = nullptr;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
up_node++;
}
down_right = prev->up;
delete prev;
//delete node_buffer.inner;
//up_node.inner->down = nullptr;
dim_row-=1;
return cursor;
}
// delete middle row
cursor--;
__detail::list_row_elem_iter<T> up_node = cursor.begin();
cursor++;
cursor++;
__detail::list_row_elem_iter<T> down_node = cursor.begin();
while(node_buffer != cursor.end())
{
up_node.inner->down = down_node.inner;
down_node.inner->up = up_node.inner;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
up_node++;
down_node++;
}
delete prev;
//delete node_buffer.inner;
//up_node.inner->down = down_node.inner;
//down_node.inner->up = up_node.inner;
dim_row-=1;
cursor--;
return cursor;
// if(cursor == row_end())
// {
// return row_end();
// }
// __detail::list_node<T> *itr = cursor.begin().inner;
// __detail::list_node<T> *temp = nullptr;
// __detail::list_node<T> *prev_head = itr->up;
// __detail::list_node<T> *prev_tail = nullptr;
// __detail::list_node<T> *next_head = itr->down;
// __detail::list_node<T> *next_tail = nullptr;
// if(itr == up_left)//delete first row
// {
// up_left = up_left->down;
// up_right = up_right->down;
// }
// if(itr == down_left)//delete last row
// {
// down_left = down_left->up;
// down_right = down_right->up;
// }
// while(itr != nullptr)
// {
// if(itr->up)
// {
// itr->up->down = itr->down;// not first row
// }
// if(itr->down)
// {
// itr->down->up = itr->up;// not last row
// }
// temp = itr->right;
// if(temp == nullptr)//last node
// {
// prev_tail = itr->up;
// next_tail = itr->down;
// }
// delete itr;
// itr = temp;
// }
// dim_row-=1;
// if(dim_row == 0)
// {
// dim_col = 0;
// return row_end();
// }
// if(prev_head == nullptr)
// {
// return row_iter(next_head, next_tail);
// }
// else{
// return row_iter(prev_head, prev_tail);
// }
}
template<class T>
__detail::list_col_iter<T> doubll2d<T>::delete_col(__detail::list_col_iter<T> cursor)
{
if(cursor == col_end() || dim_col==0)//do nothing and return `row_end()` operator
{
return col_end();
}
__detail::list_col_elem_iter<T> node_buffer = cursor.begin();//the first node in the row to be deleted
//__detail::list_row_iter<T> return_row;
__detail::list_node<T> *prev;
size_t index = 0;
prev = nullptr;
if(node_buffer.inner == up_left && dim_col==1)//delete last col
{
while(node_buffer != cursor.end())
{
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
}
//last 2 node
delete prev;
up_left = nullptr;
up_right = nullptr;
down_left = nullptr;
down_right = nullptr;
//delete node_buffer.inner;
dim_row = 0;
dim_col = 0;
return col_end();
}
if(node_buffer.inner == up_left)//delete first but not last col
{
cursor++;
__detail::list_col_elem_iter<T> right_node = cursor.begin();
up_left = right_node.inner;
while(node_buffer != cursor.end())
{
right_node.inner->left = nullptr;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
right_node++;
}
down_left = prev->right;
delete prev;
//delete node_buffer.inner;
//down_node.inner->up = nullptr;
dim_col-=1;
return cursor;
}
if(node_buffer.inner == up_right)//delete bottom but not last col;
{
cursor--;
__detail::list_col_elem_iter<T> left_node = cursor.begin();
up_right = left_node.inner;
while(node_buffer != cursor.end())
{
left_node.inner->right = nullptr;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
left_node++;
}
down_right = prev->left;
delete prev;
//delete node_buffer.inner;
//up_node.inner->down = nullptr;
dim_col-=1;
return cursor;
}
// delete middle row
cursor--;
__detail::list_col_elem_iter<T> left_node = cursor.begin();
cursor++;
cursor++;
__detail::list_col_elem_iter<T> right_node = cursor.begin();
while(node_buffer != cursor.end())
{
left_node.inner->right = right_node.inner;
right_node.inner->left = left_node.inner;
if(index!=0){
delete prev;
}
prev = node_buffer.inner;
index++;
node_buffer++;
left_node++;
right_node++;
}
delete prev;
//delete node_buffer.inner;
//up_node.inner->down = down_node.inner;
//down_node.inner->up = up_node.inner;
dim_col-=1;
cursor--;
return cursor;
// if(cursor == col_end())
// {
// return col_end();
// }
// __detail::list_node<T> *itr = cursor.begin().inner;
// __detail::list_node<T> *temp = nullptr;
// __detail::list_node<T> *prev_head = itr->left;
// __detail::list_node<T> *prev_tail = nullptr;
// __detail::list_node<T> *next_head = itr->right;
// __detail::list_node<T> *next_tail = nullptr;
// if(itr == up_left)//delete first col
// {
// up_left = up_left->right;
// down_left = down_left->right;
// }
// if(itr == up_right)//delete last col
// {
// up_right = up_right->left;
// down_right = down_right->left;
// }
// while(itr != nullptr)
// {
// if(itr->left)
// {
// itr->left->right = itr->right;// not first row
// }
// if(itr->right)
// {
// itr->right->left = itr->left;// not last row
// }
// temp = itr->down;
// if(temp == nullptr)//last node
// {
// prev_tail = itr->left;
// next_tail = itr->right;
// }
// delete itr;
// itr = temp;
// }
// dim_col-=1;
// if(dim_col == 0)
// {
// dim_row = 0;
// return col_end();
// }
// if(prev_head == nullptr)
// {
// return col_iter(next_head, next_tail);
// }
// else{
// return col_iter(prev_head, prev_tail);
// }
}
之后的一些函数
有了上面这些函数，下面这几个函数就变得非常容易了
// Clear all the nodes in the list (implement this)
template<class T>
void doubll2d<T>::clear()
{
while(dim_row != 0)
{
delete_row(row_begin());
}
return ;
}
// This reduce() implementation takes a reducer function and an initial value
// for the accumulator. For each iterable item, the reducer is called, passing
// it the accumulator and the current list element.
//
// The return value is assigned to the accumulator. When it's finished applying the
// reducer to all of the values in the list, the accumulated value is returned.
template<class T>
template<class R>
R doubll2d<T>::reduce(std::function<R (R, const T &)> fn, R init)
{
R value = init;
__detail::list_row_iter<T> row = row_begin();
while(row != row_end())
{
__detail::list_row_elem_iter<T> node = row.begin();
while(node.inner != nullptr)
{
value = fn(value,node.inner->data);
node++;
}
row++;
}
return value;
}
main调试函数
这里我用我朋友的调试函数供各位调试，并附上标准答案
#include "doubll2d.hpp"
#include <iostream>
#include <vector>
using namespace std;
using namespace __detail;
template<class T>
void printMat(doubll2d<T>& mat){
for(list_row_iter<T> row = mat.row_begin(); row != mat.row_end(); ++row){
for(list_row_elem_iter<T> elem = row.begin();elem!=row.end();++elem){
cout<< *elem <<" ";
}
cout<<endl;
}
cout<<endl;
}
template<class T>
list_row_iter<T> toRowIndex(doubll2d<T>& mat , int index){
list_row_iter<T> row = mat.row_begin();
for(int i = 0;i<index;i++){
++row;
}
return row;
}
template<class T>
list_col_iter<T> toColIndex(doubll2d<T>& mat , int index){
list_col_iter<T> col = mat.col_begin();
for(int i = 0;i<index;i++){
++col;
}
return col;
}
int main(){
vector<int> v1 = {1,2,3};
vector<int> v11 = {99,99,99,99,99,99,99,99,99,99,99};
vector<int> v2 = {4,5,6};
vector<int> v3 = {7,8,9};
vector<int> l1 = {10,11,12};
vector<int> l2 = {13,14,15};
vector<int> l3 = {16,17,18};
doubll2d<int> mat1;
doubll2d<int> mat2;
//insert test
//1. insert nothing to 0*0
mat1.insert_row(toRowIndex(mat1, 0), v1.begin(), v1.begin());
printMat(mat1);
mat1.insert_col(toColIndex(mat1, 0), v1.begin(), v1.begin());
printMat(mat1);
//output: NONE
//2. insert a row to 0*0
mat1.insert_row(toRowIndex(mat1, 0), v1.begin(), v1.end());
printMat(mat1);
//Output: 1 2 3
//3. insert a row to 1*3 at bottom
mat1.insert_row(toRowIndex(mat1, 0), v2.begin(), v2.end());
printMat(mat1);
//Output: 1 2 3
// 4 5 6
mat1.row_rbegin();
mat1.row_rend();
mat1.col_rbegin();
mat1.col_rend();
mat1.row_begin().rbegin();
mat1.row_begin().rend();
mat1.col_begin().rbegin();
mat1.col_begin().rend();
//4. insert a row to 2*3 at top
mat1.insert_row(toRowIndex(mat1, 2), v3.begin(), v3.end());
printMat(mat1);
//7 8 9
//1 2 3
//4 5 6
//5. insert nothing to 3*3 at top
mat1.insert_row(toRowIndex(mat1, 3), v1.begin(), v1.begin());
printMat(mat1);
//0 0 0
//7 8 9
//1 2 3
//4 5 6
//6. insert nothing to 3*4 at bottom
mat1.insert_row(toRowIndex(mat1, 3), v1.begin(), v1.begin());
printMat(mat1);
//0 0 0
//7 8 9
//1 2 3
//4 5 6
//0 0 0
//6. insert nothing to 3*5 at middle
mat1.insert_row(toRowIndex(mat1, 2), v1.begin(), v1.begin());
printMat(mat1);
//0 0 0
//7 8 9
//1 2 3
//0 0 0
//4 5 6
//0 0 0
//7. insert excessive row to the 3*6 at top bottom and middle
mat1.insert_row(toRowIndex(mat1, 5), v11.begin(), v11.end());
mat1.insert_row(toRowIndex(mat1, 7), v11.begin(), v11.end());
mat1.insert_row(toRowIndex(mat1, 4), v11.begin(), v11.end());
printMat(mat1);
//99 99 99
//0 0 0
//7 8 9
//1 2 3
//0 0 0
//99 99 99
//4 5 6
//0 0 0
//99 99 99
//8. delete testing I
mat1.delete_row(mat1.delete_row(toRowIndex(mat1, 0)));
mat1.delete_row(mat1.delete_row(toRowIndex(mat1, 6)));
mat1.delete_row(mat1.delete_row(toRowIndex(mat1, 3)));
mat1.delete_row(mat1.delete_row(toRowIndex(mat1, 3)));
printMat(mat1);
//7 8 9
//1 2 3
//4 5 6
//9. delete testing II
mat1.delete_row(mat1.delete_row(mat1.delete_row(toRowIndex(mat1, 0))));
printMat(mat1);
//NONE
//10. delete testing III
mat1.insert_row(toRowIndex(mat1, 0), v1.begin(), v1.end());
mat1.insert_row(toRowIndex(mat1, 0), v2.begin(), v2.end());
mat1.insert_row(toRowIndex(mat1, 2), v3.begin(), v3.end());
mat1.insert_row(toRowIndex(mat1, 3), v1.begin(), v1.begin());
mat1.insert_row(toRowIndex(mat1, 3), v1.begin(), v1.begin());
mat1.insert_row(toRowIndex(mat1, 2), v1.begin(), v1.begin());
mat1.insert_row(toRowIndex(mat1, 5), v11.begin(), v1.end());
mat1.insert_row(toRowIndex(mat1, 7), v11.begin(), v1.end());
mat1.insert_row(toRowIndex(mat1, 4), v11.begin(), v1.end());
mat1.delete_col(toColIndex(mat1,0));
mat1.delete_col(toColIndex(mat1,1));
printMat(mat1);
//99
//0
//8
//2
//0
//99
//5
//0
//99
//mat1.delete_col(toColIndex(mat1,0));
//printMat(mat1);
//None
// mat1.insert_row(toRowIndex(mat1, 0), v1.begin(), v1.end());
// mat1.insert_row(toRowIndex(mat1, 1), v2.begin(), v2.end());
// mat1.insert_row(toRowIndex(mat1, 1), v3.begin(), v3.end());
// printMat(mat1);
// mat1.delete_row(toRowIndex(mat1, 0));
// printMat(mat1);
// mat1.insert_col(toColIndex(mat1, 1), l1.begin(), l1.end());
// printMat(mat1);
// mat1.insert_row(toRowIndex(mat1, 3), v1.begin(), v1.end());
// mat1.insert_col(toColIndex(mat1, 4), v11.begin(), v11.end());
// mat1.insert_col(toColIndex(mat1, 0), l3.begin(), l3.end());
//printMat(mat1);
// mat1.delete_row(toRowIndex(mat1, 0));
// printMat(mat1);
// mat1.delete_col(toColIndex(mat1, 4));
// mat1.delete_col(toColIndex(mat1, 3));
// mat1.delete_col(toColIndex(mat1, 2));
// mat1.delete_col(toColIndex(mat1, 1));
// mat1.delete_col(toColIndex(mat1, 5));
// printMat(mat1);
// mat1.clear();
// mat1.insert_row(toRowIndex(mat1, 0), v1.begin(), v1.end());
// printMat(mat1);
return 0;
}