网站开发需要2个月吗,做网站时如何建立栅格,网站建设频教程,中国核工业第五建设有限公司待遇一、有关list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后一个元素。Ii…一、有关list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。Iist与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代以让其更简单高效。与其他的序列式容器相比(array,vector,deque),Iist通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比Iist和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置比如头部或者尾部迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息对于存储类型较小元素的大list来说这可能是一个重要的因素)list中的sort和算法库中sort的区别
在C中有两种不同的 sort 函数一种是 list 容器的成员函数 sort另一种是算法库中的 std::sort。它们在功能和应用上有一些区别。 list 中的 sort list 是 C 标准库中的双向链表容器它具有自己的成员函数 sort可以用于对链表中的元素进行排序。list::sort 使用的是链表特有的插入、删除操作因此适用于链表这种数据结构。它的时间复杂度为 O(N*logN)。由于链表的特性其插入、删除操作的时间复杂度为 O(1)因此 list::sort 可以高效地对链表进行排序。 算法库中的 std::sort std::sort 是 C 标准库中的算法可以用于对各种容器如数组、向量等中的元素进行排序。std::sort 使用的是比较和交换操作适用于随机访问迭代器所表示的数据结构比如数组、向量等。它的时间复杂度也为 O(N*logN)。对于随机访问迭代器所表示的数据结构std::sort 是一种通用的排序算法可以适用于各种数据结构。
总的来说list::sort 适用于对链表进行排序而 std::sort 适用于对各种支持随机访问的数据结构进行排序例如数组、向量等。选择哪种排序方式取决于你使用的数据结构以及具体的排序需求。
迭代器的类型
虽然不管是算法库中的sort还是list中的sort在传参时都使用了模板理论上是可以传递任意类型的迭代器但是它们在实现函数时可能使用了 只有特定迭代器 才能使用的操作导致如果传递的迭代器不支持这个功能该函数就无法使用。
例如在库sort实现时使用了指针相减来确定元素距离而对于链表来说它的指针的指向不是顺序的而是随机的用指针相减是毫无意义的。 那我们在使用时如果确定传递怎样的迭代器呢
实际上在文档中命名迭代器时会有提示。 例如在算法库中sort迭代器命名为 RandomAccessIterator - 随机访问迭代器。所以在使用前可以查看一下文档。
迭代器从功能分类上可以分为五种主要类型 输入迭代器Input Iterator 只能用于读取数据一般用于单向遍历容器中的元素例如 std::vector、std::list 等。 输出迭代器Output Iterator 只能用于写入数据也是单向的只能逐个元素地写入数据。 单向迭代器Forward Iterator 可以读取和写入数据支持在序列中向前移动例如单向链表。 双向迭代器Bidirectional Iterator 除了具备前向迭代器的功能外还支持在序列中向后移动例如 std::list。 随机访问迭代器Random Access Iterator 提供了对迭代器进行算术操作的功能可以在 O(1) 的时间复杂度内实现随机访问和跳跃式遍历例如数组。
需要注意的是我们传递的迭代器只要能够满足该函数所需的功能即可不是一定要传特定的迭代器才行。例如双向迭代器和随机访问迭代器含有单向迭代器的功能所以这两个迭代器是可以传递给所使用的函数的。 二、list的模拟实现
list的数据结构
// 带头双向循环链表的一个节点
templateclass T
struct list_node
{// 成员变量list_nodeT* _prev;list_nodeT* _next;T _data;// 构造函数list_node(const T x T()):_data(x), _prev(nullptr), _next(nullptr){}
};templateclass T
class list
{typedef list_nodeT node;public:// 迭代器typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;
private:// 头节点的指针 node* _head;
};
1、迭代器
这里迭代器的底层一定是一个Node*的指针但是不能直接将Node*定义为iterator因为Node*是一个指针属于内置类型当我们使用iterator时将相当于将Node*指针向后移动一个Node大小的空间而list每一个节点存放的地址并不是连续的所以这时候的操作是不行的。
注对于string和vector来说他俩的底层是使用一个可变空间的数组每一个元素存放的地址是连续的不需要对操作符进行重载所以他俩可以直接使用原生指针作为迭代器不用进行封装。
为了达到iterator的功能是移动到下一个节点处我们需要重载操作符因为对于内置类型才能进行重载操作符所以我们要将Node*封装成为一个自定类型进而对操作符进行重载。
先大概看一下对于操作符 * 和 的重载后面会详细讲解
reference operator*() const { return node-data; }self operator()
{ node node-_next;return *this;
}
所以迭代器的框架可以定义为
struct __list_iterator
{// 成员变量typedef list_nodeT node;typedef __list_iteratorT self; // 因为__list_iterator名字较长可以在内部重命名一下node* _node;
};
这个自定义类型也需要有一个构造函数
__list_iterator(node* n):_node(n)
{}迭代器中对操作符的重载
然后再__list_iterator自定义类型内部对各种操作符进行重载
// 解引用操作符返回的是node指向的值要求可以被修改所以返回值要使用引用
Ref operator*()
{return _node-_data;
}// 前置
self operator()
{_node _node-_next;return *this;
}// 后置
self operator(int)
{self ret(*this);_node _node-_next;return ret;
}// 前置--
self operator--()
{_node _node-_prev;return *this;
}// 后置--
self operator--(int)
{self ret(*this);_node _node-_prev;return ret;
}bool operator!(const self s)
{ return _node ! s._node;
}bool operator(const self s)
{return _node s._node;
}const迭代器的设计
使用场景
void func(const listint lt)
{listint::iterator it lt.begin();while (it ! lt.end()){(*it) * 2;cout *it ;it;}cout endl;
}
会出现以下错误 原因是因为lt是一个const的对象则会用一个const的对象调用begin和end而实现的begin()和end()都是普通对象才能够调用的所以我们还要重载一个const对象使用的begin和end函数。
iterator begin() const
{return iterator(_head-_next);
}
但是如果只是使用const修饰begin()和end()会出现这样的问题我们使用const对象作为参数主要是不想更改对象的内容的但是现在这段代码还是可以改变该对象的内容的。
这是因为这个begin()返回的迭代器_head-_next是一个普通迭代器并没有使用const进行修饰所以可以修改迭代器指向的内容。
分析
需要注意的是虽然begin()使用const进行修饰也能创建出一个普通的迭代器(非const)const修饰的是 listint* this 即 const *this所以const修饰的是this指针指向的_head所以_head的常性的同时_head也是一个指针用const修饰代表着_head的指向不能再改变了但是_head指向的内容是可以改变的即_head-_next是可以改变的非const修饰的所以由_head-_next创建出来的迭代器也是非const修饰的。 所以还要让这两个函数的返回值设置成一个const迭代器要求不能通过这个const迭代器修改其指向的值。
错误结构 不能直接在普通迭代器前面加上一个const成为一个const迭代器这种写法是保证迭代器本身不能被修改我们想要实现的效果是迭代器指向的内容不能被修改
注意这里的typedef进行重命名时不是进行简单的替换typedef const iterator const_iterator;并不等于 typedef const node* const_iterator而应该是 typedef node* const const_iterator
所以const修饰的是node的指针并不是修饰node指针指向的内容。例如
int main()
{int a 2;int c 1;typedef int* PA;const PA b a;*b 2;printf(%d, a);return 0;
} 我们发现可以通过b修改 a 的值从a 2变成a 4。并且
int main()
{int a 2;int c 1;typedef int* PA;const PA b a;b c;return 0;
} b的指向不能被改变。
所以这样进行定义是不行的const修饰的是b指针而不是b指向的内容。 正确结构
我们可以对按照普通迭代器一样再创建一个const类型的迭代器。
const迭代器和普通迭代器的之间的实现对于其他操作符的实现不用改变如、需要改变的就是 * 操作符的重载const迭代器要求迭代器指向的值不能被修改因此只需要在实现 * 操作符的重载时将返回值设置成为常量这样就完成了。
templateclass T
struct __list_const_iterator
{// 成员变量typedef list_nodeT node;typedef __list_const_iteratorT self;node* _node;// 函数、运算符__list_const_iterator(node* n):_node(n){}// 解引用操作符返回的是node指向的值要求不可以被修改所以返回值要使用常量引用const T operator*(){return _node-_data;}// 前置self operator(){_node _node-_next;return *this;}// 后置self operator(int){self ret(*this);_node _node-_next;return ret;}// 前置--self operator--(){_node _node-_prev;return *this;}// 后置--self operator--(int){self ret(*this);_node _node-_prev;return ret;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}
}; 但是我们发现这两个迭代器只有解引用操作符的返回值类型不同其余的函数和变量都相同代码比较冗余。
我们可以再使用一个模板参数进行改进当我们在创建一个迭代器时可以将迭代器的类型作为一个参数进行创建。
templateclass T, class Ref
struct __list_iterator
{// 成员变量typedef list_nodeT node;typedef __list_iteratorT, Ref self;node* _node;// 函数、运算符__list_iterator(node* n):_node(n){}// 解引用操作符返回的是node指向的值要求可以被修改所以返回值要使用引用Ref operator*(){return _node-_data;}};typedef __list_iteratorT, T iterator;
typedef __list_iteratorT, const T const_iterator;
这样就可以使用一个模板完成两个类才能完成的工作。 const对象调用const类型的begin()begin()函数返回一个const类型的迭代器注意const类型的迭代器不是const对象其本身是可以修改的是其指向的内容不能被修改这样设计就能完成前面的使用场景了。 - 操作符的重载
使用场景
struct AA
{int _a1;int _a2;AA(int a1, int a2):_a1(a1), _a2(a2){}
} 操作符右操作数为AA类型的一个对象lt指向list第一个对象也就是AA所以lt就是AA类型的一个指针由于没有对进行重载所以不能进行打印。
所以解决办法要么我们对操作符进行重载 要么用这种方法进行使用但用起来不方便在C语言中我们可以通过-操作符访问一个自定义类型指针的成员变量所以我们也可以对-操作符进行重载。
T* operator-()
{return _node-data;
}
可以这样使用 使用的时候可以这样使用但是通过分析好像有点不妥 我们发现 it.operator-() 得到的只是AA*并没有得到_a1如果想要得到_a1还要在此基础上再加一个-才能得到_a1即 (it.operator-())-_a1it--_a1.
但事实上我们可以只用一个-就可以访问到_a1其实是编译器进行了优化省略了一个箭头。 同时为保证重载的operator-() 也有const的版本也会像上面那样再添加一个模板参数用来实例化operator-() 不同的迭代器。
templateclass T, class Ref, class Ptr
struct __list_iterator
{// 成员变量typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node* _node;Ptr operator-(){return _node-data;}
};typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;2、list相关函数实现
1Modifiers
Ⅰ. insert
这里的insert的操作就是在一个带头双向循环链表中插入一个节点
void insert(iterator pos, const T x)
{node* cur pos._node;node* prev cur-_prev;node* new_node new node(x);prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;
}
同时也要注意迭代器失效的问题这里需要设置一个返回值用来更新外部迭代器的位置。
iterator insert(iterator pos, const T x)
{node* cur pos._node;node* prev cur-_prev;node* new_node new node(x);prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;return new_node;
}
与之逻辑相配的函数是push_back()和push_front()因此这两个函数的实现可以对insert进行复用
void push_back(const T x)
{insert(end(), x);
}void push_front(const T x)
{insert(begin(), x);
}
Ⅱ. erase
iterator erase(iterator pos)
{assert(pos ! end());node* prev pos._node-_prev;node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);
}
注意这里的迭代器失效问题会导致野指针的问题所以同样设置一个返回值。
与之逻辑相配的函数是pop_back()和pop_front()因此这两个函数的实现可以对erase进行复用
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
} 2默认成员函数
Ⅰ. destructor
在模拟实现析构函数前先介绍一下clear()函数。
clear()
Removes all elements from the list container (which are destroyed), and leaving the container with a size of 0.--移除所有元素不包括头节点。
这里为了防止迭代器失效的问题可以使用erase的返回值返回删除当前节点的下一个。
// 不清除头节点
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}
也可以使用下面这种写法。
// 不清除头节点
void clear()
{iterator it begin();while (it ! end()){erase(it);}
}
注意这里并不是通过 it 进行删除的而是使用 it 返回的一个拷贝值进行删除。 析构函数
可以对clear()函数进行复用并删除头节点即可。
~list()
{clear();delete _head;_head nullptr;
}
Ⅱ. constructor
构造函数
// 构造函数
list()
{_head new node;_head-_next _head;_head-_prev _head;
}这里手动创建了一个头节点。 当然也可以使用迭代器进行构造一个对象这里可以复用push_back()函数但是在使用push_back之前需要有一个头节点。因为后面也要使用到初始化list让list有一个头节点所以可以将这个步骤写成一个函数empty_init()
void empty_init()
{_head new node;_head-_next _head;_head-_prev _head;
}// 迭代器区间的初始化
templateclass Iterator
list(Iterator first, Iterator last)
{// 使用push_back之前需要有头节点empty_init();while (first ! last){push_back(*first);first;}
}拷贝构造函数
第一种方法根据右边的节点一个一个创建出节点值相同的list
void empty_init()
{_head new node;_head-_next _head;_head-_prev _head;
}// 拷贝构造函数传统写法
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}第二种使用迭代器区间的构造函数构造一个对象再交换两者的指针
void empty_init()
{_head new node;_head-_next _head;_head-_prev _head;
}void swap(listT temp)
{std::swap(_head, temp._head);
}
// 拷贝构造函数使用swap交换头指针
list(const listT lt)
{empty_init();// 使用迭代器区间构建一个对象listT temp(lt.begin(), lt.end());// 交换指针swap(temp);
} operator
第一种传统写法
// 传统写法
listT operator(const listT lt)
{if (this ! lt){clear(); // 删除被赋值list中的值for (auto e : lt) // 插入值{push_back(e);}}return *this;
}第二种写法
listT operator(listT lt)
{swap(lt);return *this;
}
注意不能将对象的引用作为参数。要与被拷贝对象的一个拷贝进行交换传值调用了拷贝构造函数如果使用引用会导致右边被赋值的对象被改变。
3iterator
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;Ⅰ. begin()
这里的细节在前面已经讲过了。
iterator begin()
{return iterator(_head-_next);
}const_iterator begin() const
{return const_iterator(_head-_next);
}
Ⅱ. end()
iterator end()
{return iterator(_head);
}const_iterator end() const
{return const_iterator(_head);
}
3、反向迭代器
1反向迭代器的介绍
反向迭代器是一种迭代器它可以在容器中从后向前遍历元素。与正向迭代器不同的是反向迭代器的操作符是让迭代器指向前一个元素--操作符是让迭代器指向后一个元素。反向迭代器通常用于需要从后往前遍历容器的算法和场景中。
反向迭代器和正向迭代器在使用上有相似之处它们都可以通过解引用运算符来访问当前迭代器指向的元素也可以通过比较运算符来判断迭代器之间的大小关系。但是它们之间也存在一些区别和联系。
区别 步进方向不同正向迭代器的步进方向是从前向后而反向迭代器的步进方向是从后向前。 支持的操作不同由于反向迭代器的步进方向不同因此它们不支持正向迭代器的某些操作例如递增和递减操作等。 消耗的空间不同反向迭代器需要保存一个正向迭代器来实现其功能因此它们通常会消耗更多的空间。
联系 都是迭代器反向迭代器和正向迭代器都是STL迭代器的一种都具有迭代器的基本特性。 具有相同的接口反向迭代器和正向迭代器都具有相同的解引用和比较运算符等接口。 可以互相转换由于反向迭代器是基于正向迭代器实现的因此它们可以通过std::reverse_iterator构造函数进行互相转换。
2反向迭代器的模拟实现
反向迭代器的就是正向迭代器的-反向迭代器的一就是正向迭代器的因此反向迭 代器的实现可以借助正向迭代器。
如果直接在正向迭代器的基础上更改个别操作符的重载方法虽然能够实现反向迭代器的功能但是方法比较笨拙。
标准库中对反向迭代器是通过适配器适配正向迭代器来实现的。
所以反向迭代器的底层就是正向迭代器
templateclass Iterator // 使用一个正向迭代器适配出一个反向迭代器
struct Reverse_Iterator
{Iterator cur; // 底层是一个正向迭代器// 构造函数Reverse_Iterator(Iterator it):cur(it){}
};
// 正向迭代器
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;// 反向迭代器
typedef Reverse_Iteratoriterator, T, T* reverse_iterator;
typedef Reverse_Iteratoriterator, const T, const T* const_reverse_iterator;
有一些标准库中有以下规定并不是所有的库都是这样实现的 因此在链表中rbegin()和rend()的模拟实现如下
// 反向迭代器
reverse_iterator rbegin()
{return iterator(end());
}reverse_iterator rend()
{return iterator(begin());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
} 反向迭代器对操作符的重载
反向迭代器的操作符是让迭代器指向前一个元素所以反向迭代器对操作符的重载可以复用正向迭代器的 --操作符同时加上前面对正向迭代器关于const问题的处理最终重载的结果为
templateclass Iterator, class Ref, class Ptr // 使用一个正向迭代器适配出一个反向迭代器
struct Reverse_Iterator
{typedef Reverse_IteratorIterator, Ref, Ptr Self;Iterator cur; // 底层是一个正向迭代器// 构造函数Reverse_Iterator(Iterator it):cur(it){}Self operator(){--cur; // 调用正向迭代器的--操作符return *this;}Self operator(int){Iterator tmp *this;--cur; // 调用正向迭代器的--操作符return tmp;}
};
--操作符是让迭代器指向后一个元素所以反向迭代器对--操作符的重载可以复用正向迭代器的 操作符
Self operator--()
{cur; // 调用正向迭代器的操作符return *this;
}Self operator--(int)
{Iterator tmp *this;cur; // 调用正向迭代器的操作符return tmp;
} 和 ! 的重载
bool operator!(const Self it)
{return cur ! it.cur; // 调用正向迭代器的!操作符
}bool operator(const Self it)
{return cur it.cur; // 调用正向迭代器的操作符
}
* 和 - 的重载
因为我们选择让 实现的反向迭代器和正向迭代器的begin和end具有一定的对称性 所以这里对 * 操作符的重载并不能直接对正向迭代器的 * 操作符进行复用。
因为 rbegin 指向 end 的位置直接使用正向迭代器的 * 操作符会出现错误所以反向迭代器对 * 的重载应该返回 rbegin 前一个的元素
Ref operator*()
{Iterator tmp cur;--tmp;return *tmp; // 调用正向迭代器的解引用操作符
}
在前面正向迭代器部分我们知道-操作符返回的是迭代器指向元素的指针所以
Ptr operator-()
{return (operator*());
}
首先让我们来解读 operator*() 函数的实现
在函数内部创建一个临时的迭代器对象 temp并将其初始化为当前迭代器对象 _it。对 temp 进行递减操作符 -- 的操作将其指向前一个元素。返回 temp 所指向的元素对象 *temp。
这段代码的作用是返回当前迭代器所指向的元素。通过创建一个临时的迭代器对象并将其指向前一个元素然后返回该元素实现了迭代器的解引用操作。
接下来我们来看 operator-() 函数的实现
在函数内部调用 operator*() 函数获取当前迭代器所指向的元素。使用取地址符 取得该元素的指针并返回该指针。
这段代码的作用是返回一个指向当前迭代器所指向元素的指针。通过调用 operator*() 函数获取元素的引用然后使用取地址符 获取该元素的指针实现了迭代器的箭头操作符。 注意
因为这里的迭代器使用了一个模板所以不仅可以实现list的反向迭代器也可以通过其他容器的正向迭代器适配出它的反向迭代器。 今天的分享就到这里了如果你感觉这篇博客对你有帮助的话就点个赞吧感谢感谢……
