list模拟实现 伪代码
知识点
节点
template<class T>
struct list_node //这是一个通用节点模板，所以名字还用list_node，方便不同容器共享节点结构，在容器内可以改别名Node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x = T()) //如果调用构造函数时不传参，就自动调用T类型的默认构造函数生成一个默认值
:_next(nullptr), _prev(nullptr), _data(x)
{}
};
正向迭代器
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*() { return _node->_data; } //_node->_data是实际值，引用它即访问它，可做左值
Ptr operator->() { return &_node->_data; } //返回node的data的地址，&取值
Self& operator++()
{
_node = _node->_next;
return *this; //this是Self*，*this是Self&
}
Self operator++(int) //后置版本it++
{
Self tmp(*this); //用当前对象构造新Self
_node = _node->_next; //当前对象本身前进
return tmp; //返回原来的位置
}
Self operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& it) const //比较两个迭代器内部的节点指针是否指向同一个位置
{
/*if (it->data == *this->data)
{
return true;
}
else
return false;*/
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
反向迭代器
template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Iterator _it; //反向迭代器内部的_it实际上是正向迭代器中 当前位置的下一个元素
Reverse_iterator(Iterator it) :_it(it) {}
Ref operator*()
{
Iterator tmp = _it; //规定_it指向的是最后一个元素的后一个位置
return *--tmp;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp = _it;
--_it;
return *tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp = _it;
++_it;
return *tmp;
}
bool operator!=(const Self& it) const
{
return _it != it._it;
}
bool operator==(const Self& it) const
{
return _it == it._it;
}
};
包装的正向迭代器
- 其中，
_it其实是一个正向迭代器
为什么？
真正“传入”的时机是你用它时！
比如这样：
bit::list<int>::iterator it = lst.end();
bit::Reverse_iterator<bit::list<int>::iterator, int&, int*> rit(it);
这一句就做了这些事：
| 模板参数名 | 实际传入值 | 含义 |
|---|---|---|
| Iterator | bit::list<int>::iterator |
正向迭代器类型 |
| Ref | int& |
解引用操作返回引用 |
| Ptr | int* |
-> 操作返回指针类型 |
bit::list<int>::iterator第一层：
class list中typedef list_iterator<T, T&, T*> iterator第二层：
struct list_iterator中typedef list_iterator<T, Ref, Ptr> Self;
所以：
- 之后
*rit实际调用的是int& operator*()，而*--tmp最终是你自己的list_iterator的operator*()返回的引用
正向反向遍历逻辑一致
| 位置 | 正向迭代器值 | 反向迭代器内部 _it 应该是 |
|---|---|---|
| rbegin() | 指向 30 | _it = v.end() |
| rend() | 超出左边界 | _it = v.begin() |
题目
1. 下面有关 vector 和 list 的区别，描述正确的是：
- A. 两者在尾部插入的效率一样高 ❌ 错误
vector 在尾部插入通常是 摊还 O(1)，但可能因 扩容而移动整个数组，所以不是绝对高效。
list 在尾部插入是 O(1)，不会移动元素。
👉 所以虽然通常效率都高，但不能说“一样高”。
- B. 两者在头部插入的效率一样高 ❌ 错误
vector 在头部插入是 O(n)，因为要搬动所有元素。
list 在头部插入是 O(1)，只改链指针。
👉 所以效率差距很大，不一样高。
- C. 两者都提供了 push_back 和 push_front 方法 ❌ 错误
list：✅ 提供 push_back() 和 push_front()
vector：✅ 有 push_back()，❌ 没有 push_front()
👉 所以这个选项错误。
- D. 两者都提供了迭代器，且迭代器都支持随机访问 ❌ 错误
vector 的迭代器是 随机访问迭代器 ✅
list 的迭代器是 双向迭代器 ❌，不支持随机访问（不能 +n、[]）
2. 以下程序输出结果为( )
int main()
{
int ar[] = { 0,1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = sizeof(ar) / sizeof(int);
list<int> mylist(ar, ar+n);
list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);
reverse(mylist.begin(), pos);
reverse(pos, mylist.end());
list<int>::const_reverse_iterator crit = mylist.crbegin();
while(crit != mylist.crend())
{
cout<<*crit<<" ";
++crit;
}
cout<<endl;
}
reverse()是左闭右开
完整代码
list.h
#pragma once
#include<assert.h>
//class list {
//public:
//
//private:
//
//}; //不能直接以这个结构开始，要命名空间以及使用模板类
namespace zoya {
template<class T>
struct list_node //这是一个通用节点模板，所以名字还用list_node，方便不同容器共享节点结构，在容器内可以改别名Node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x = T()) //如果调用构造函数时不传参，就自动调用T类型的默认构造函数生成一个默认值
:_next(nullptr), _prev(nullptr), _data(x)
{}
};
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*() { return _node->_data; } //_node->_data是实际值，引用它即访问它，可做左值
Ptr operator->() { return &_node->_data; } //返回node的data的地址，&取值
Self& operator++()
{
_node = _node->_next;
return *this; //this是Self*，*this是Self&
}
Self operator++(int) //后置版本it++
{
Self tmp(*this); //用当前对象构造新Self
_node = _node->_next; //当前对象本身前进
return tmp; //返回原来的位置
}
Self operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& it) const //比较两个迭代器内部的节点指针是否指向同一个位置
{
/*if (it->data == *this->data)
{
return true;
}
else
return false;*/
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
};
template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Iterator _it; //反向迭代器内部的_it实际上是正向迭代器中 当前位置的下一个元素
Reverse_iterator(Iterator it) :_it(it) {}
Ref operator*()
{
Iterator tmp = _it; //规定_it指向的是最后一个元素的后一个位置
return *--tmp;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp = _it;
--_it;
return *tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp = _it;
++_it;
return *tmp;
}
bool operator!=(const Self& it) const
{
return _it != it._it;
}
bool operator==(const Self& it) const
{
return _it == it._it;
}
};
template<class T>
class list
{
typedef list_node<T> Node; //默认为private，辅助性内部别名，低关注度
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
list()
{
empty_init();
}
list(std::initializer_list<T> lt) //{1, 2, 3, 4} 这种语法，在 C++11 中被设计为会被自动转换为一个 std::initializer_list<int> 类型的对象。
{
empty_init();
for (const auto& e : lt)
{
push_back(e);
}
}
list(const list<T>& lt)
{
empty_init();
for (const auto& e : lt)
{
push_back(e);
}
}
list<T>& operator=(list<T> lt) //如果用list<T>& lt，就不能进行swap()，因不能修改const引用。本质上不是交换，不用考虑本引用的list本身
{
swap(lt);
return *this; //返回被赋值的本身
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_head); } //循环双向链表，所以到head表示整个链表都遍历完了
const_iterator begin() const { return const_iterator(_head->_next); }
const_iterator end() const { return const_iterator(_head); }
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
size_t size() const { return _size; }
bool empty() const { return _size == 0; }
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return iterator(next);
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
private:
void empty_init()
{
//_head = NULL;
_head = new Node; //堆上分配的这块内存的指针
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
Node* _head;
size_t _size;
};
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
#include <ctime>
#include "list.h"
using namespace std;
void test_list1()
{
list<int> lt1 = { 1,2,3,4 };
for (auto e : lt1)
cout << e << " ";
cout << endl;
list<int> lt2 = { 10,2,30,5 };
for (auto e : lt2)
cout << e << " ";
cout << endl;
}
void test_list2()
{
list<int> lt1 = { 1,2,3,4 };
lt1.assign(2, 1); //清空lt，放入2个1
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
struct A //带默认参数的构造函数
{
A(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {} //直接初始化列表，直接调用有参构造，不用再调用默认构造
int _a1;
int _a2;
};
ostream& operator<<(ostream& os, const A& a) {
os << "(" << a._a1 << ", " << a._a2 << ")";
return os;
}
void test_list3()
{
list<A> lt1;
lt1.push_back(A(2, 2));
for (auto e : lt1)
cout << e << " ";
cout << endl;
lt1.emplace_back(2, 2);
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
void test_list4()
{
list<int> lt1 = { 10,2,30,5,2,4,2 };
lt1.remove(100);
lt1.remove(5);
lt1.remove(2);
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
void test_list5()
{
list<int> lt1 = { 10,2,30,5,2,4,2 };
lt1.sort();
for (auto e : lt1)
cout << e << " ";
cout << endl;
lt1.sort(greater<int>()); //从大到小排序
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
void test_list6()
{
list<int> lt1 = { 10,2,30,5,2,5,5,2,4,2 };
lt1.sort();
lt1.unique(); //只移除相邻且相等的元素，保留第一个。因unique() 不会自动排序，所以通常要先调用 sort()
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
void test_list7()
{
list<int> lt1 = { 1,2,3,4,5,6 };
lt1.splice(lt1.end(), lt1, lt1.begin());
for (auto e : lt1)
cout << e << " ";
cout << endl;
}
void test_op1()
{
srand(time(0));
const int N = 1000000;
vector<int> v;
list<int> lt1;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i; //rand()生成的随机数范围有限，有时会重复，加上i尽量保证每个元素至少不完全相同
v.push_back(e);
lt1.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort(); //std::list的迭代器是双向迭代器，不支持随机访问，但std::sort要求随机访问迭代器，list无法直接用std::sort，所以用自身的成员函数sort()。
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1); //vector sort:341
printf("list sort:%d\n", end2 - begin2); //list sort : 564
}
void test_op2()
{
srand(time(0));
const int N = 1000;
list<int> lt1, lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
vector<int> v(lt2.begin(), lt2.end());
sort(v.begin(), v.end());
lt2.assign(v.begin(), v.end()); //把vector中的元素复制覆盖到list中
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("list copy to vector and sort and copy to list:%d\n", end1 - begin1); //1
printf("list sort:%d\n", end2 - begin2); //0
}
void test_zoyalist1()
{
zoya::list<int> lt1 = { 1,2,3,4 };
for (auto it = lt1.begin(); it != lt1.end(); ++it)
{
*it += 1;
cout << *it << " ";
}
cout << endl;
}
void Print(const zoya::list<int>& lt)
{
zoya::list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_zotalist2()
{
zoya::list<A> lt1;
lt1.push_back({ 1,1 });
lt1.push_back({ 2,2 });
lt1.push_back({ 3,3 });
lt1.push_back({ 4,4 });
for (auto it = lt1.begin(); it != lt1.end(); ++it)
cout << it->_a1 << ":" << it->_a2 << endl;
zoya::list<int> lt2 = { 1,2,3,4 };
Print(lt2);
}
void test_zoyalist3()
{
zoya::list<int> lt1 = {1, 2, 3, 4};
for (auto it = lt1.rbegin(); it != lt1.rend(); ++it)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
//test_list2();
//test_list3();
//test_list4();
//test_list5();
//test_list6();
//test_list7();
//test_op1();
//test_op2();
//test_zoyalist1();
//test_zotalist2();
test_zoyalist3();
return 0;
}
小天才公司福利 784人发布