【C++】STL容器:list的模拟实现-创新互联
一、list的结构
1. list的节点
二、list的迭代器
2. 反向迭代器
三、构造和析构
四、insert和erase
五、其他元素操作
文章题目:【C++】STL容器:list的模拟实现-创新互联
文章来源:http://pwwzsj.com/article/ddisch.html
list的底层是一个带头双向循环链表,但list本身和list的节点是不同的结构,需要分开实现。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名与空间、虚拟主机、营销软件、网站建设、砀山网站维护、网站推广。list节点的结构:
templatestruct list_node
{list_node* _next;
list_node* _prev;
T _data;
//构造:使用x初始化节点的数据
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
2. list的结构class list
{typedef list_nodenode;
//……
private:
node* _head;
size_t _size;
};
二、list的迭代器
list的迭代器不能再像vector一样用普通指针作为迭代器,因为存储节点的空间不保证连续。
list迭代器必须有能力指向list的节点,并能够正确的进行++、--、*、->
等操作,所谓正确是指:++
时指向下一个节点,--
时指向上一个节点,*
取的是节点的数据值,->
取的是节点数据成员的地址。
list的迭代器使用封装 + 操作符重载,以达到在使用方式上如同指针一样的目的。
list是一个双向链表,迭代器必须具有前移++、后移- -,所以list的迭代器是一个双向迭代器。
1. 正向迭代器templatestruct __list_iterator
{typedef list_nodenode;
typedef __list_iteratorSelf;
node* _pnode;//迭代器内部要有一个指针,指向list的节点
//constructor
__list_iterator(node* p)
:_pnode(p)
{}
Ptr operator->()
{//return &_pnode->_data;
return &(operator*());//标准做法
}
// iterator it
// *it
// ++it;
// 解引用取到的是节点的数据值
Ref operator*()
{return _pnode->_data;
}
const T& operator*() const
{return _pnode->_data;
}
// ++it
Self& operator++()
{_pnode = _pnode->_next;
return *this;
}
// it++
Self operator++(int)//返回类型为迭代器自己
{//拷贝构造,这里只需要浅拷贝,使用系统生成的即可满足需求
Self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
//--it
Self& operator--()
{_pnode = _pnode->_prev;
return *this;
}
//it--
Self operator--(int)
{Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
//比较指向节点的指针即节点的地址
bool operator!=(const Self& it) const
{return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{return _pnode == it._pnode;
}
};
2. 反向迭代器
反向迭代器的实现体现了泛型思维。反向迭代器是正向迭代器的封装,内部有一个正向迭代器成员
模板参数Iterator:给我不同容器的正向迭代器,适配出对应的这个容器需要的反向迭代器。比如要实现vector的反向迭代器只需将其正向迭代器作为参数传入即可。
// 适配器 -- 复用
templateclass ReverseIterator
{typedef ReverseIteratorSelf;
private:
Iterator _it;
public:
ReverseIterator(Iterator it)
:_it(it)
{}
Ref operator* ()
{Iterator tmp = _it;
return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}
Ptr operator->()
{return &(operator*());//显示调解引用再取地址
}
//前置++
Self& operator++ ()
{--_it;//反向迭代器的++是正向迭代器的--
return *this;
}
//后置++
Self operator++ (int)
{ReverseIterator tmp(_it);
--_it;
return tmp;
}
//前置--
Self& operator-- ()
{++_it;
return *this;
}
//后置--
Self operator-- (int)
{ReverseIterator tmp(_it);
++_it;
return tmp;
}
bool operator!= (const Self& s)
{return _it != s._it;
}
};
3. 迭代器失效问题list的一个性质:插入操作不会造成原迭代器失效。删除操作也只有”指向“被删除元素的迭代器失效,其他不受影响。
4. 具体实现templateclass list
{typedef list_nodenode;
private:
node* _head;
size_t _size;
//……
public:
//前面使用模板参数是为了根据传入参数不同实现不同迭代器
typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
typedef ReverseIteratorreverse_iterator;
typedef ReverseIteratorconst_reverse_iterator;
//反向迭代器
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());
}
const_iterator begin() const
{return const_iterator(_head->_next);
}
const_iterator end() const
{return const_iterator(_head);
}
iterator begin()
{return iterator(_head->_next);
}
iterator end()
{//iterator it(_head);
//return it;
return iterator(_head);
}
};
可以发现正向迭代器和反向迭代器是对称的,这也是为什么在反向迭代器实现中会有如下代码:
Ref operator* ()
{Iterator tmp = _it;
return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}
三、构造和析构
- 构造一个空链表
void empty_initialize()
{_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list() {empty_initialize(); }//生成一个空链表
- 区间构造
templatelist(InputIterator first, InputIterator last)
{empty_initialize();
while (first != last)
{push_back(*first);
++first;
}
}
- 拷贝构造和赋值运算符重载
//传统写法
// lt2(lt1)
//list(const list& lt)
//{// empty_initialize();
// for (const auto& e : lt)
// {// push_back(e);
// }
//}
lt1 = lt3
//list& operator=(const list& lt)
//{// if (this != <)
// {// clear();
// for (const auto& e : lt)
// {// push_back(e);
// }
// }
// return *this;
//}
void swap(list& lt)
{std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// lt2(lt1)
list(const list& lt)
//list(const list& lt) //虽然C++语法支持类名作为类型,但是不建议
{empty_initialize();
listtmp(lt.begin(), lt.end());
swap(tmp);
}
// lt3 = lt1
list& operator=(listlt)
//list& operator=(list lt) // 不建议
{swap(lt);
return *this;
}
- 析构
void clear()
{iterator it = begin();
while (it != end())
{it = erase(it);
}
}
~list()
{clear();//clear完成除头节点外其他节点的销毁工作
delete _head;
_head = nullptr;
}
四、insert和erase
//在pos前插入
iterator insert(iterator pos, const T& x)
{node* newnode = new node(x);
node* cur = pos._pnode;
node* prev = cur->_prev;
// prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos)
{assert(pos != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
return iterator(next);
}
五、其他元素操作
void push_back(const T& x)
{//node* newnode = new node(x);
//node* tail = _head->_prev;
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{insert(begin(), x);
}
void pop_front()
{erase(begin());
}
void pop_back()
{erase(--end());
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:【C++】STL容器:list的模拟实现-创新互联
文章来源:http://pwwzsj.com/article/ddisch.html