首页 > 代码库 > STL 之 list源代码自行实现（iterator）
STL 之 list源代码自行实现（iterator）
一：起因
（1）数据结构里面两种非常重要的存储结构，线性结构中的连续存储结构（代表vector数组）和非连续存储结构（代表list链表），他们两者被广泛的应用在
各个领域，是最基本最基础的两种存储结构；
（2）vector 已经简单的实现了，请看STL 之 vector的实现 之前还实现了STL的string类，请看 STL 之 string 的实现
（3）之前的友元类只是停留在理论层面，真正实现还是头一次；（虽然友元函数，无数次的实现过了）这个友元类正是 Iterator 类，也是初次实现
Iterator，见识了Iterator ++ --运算符的重载，注意仅仅实现了单一方向的++ --（这是源代码这样处理的）；友元类非常像java中的内部类。。。
（4）list 自己也是结合STL的源代码，结合数据结构简单的实现的，里面可能有一些处理不当，请大神们指正，谢谢！
二：list实现
（1）list的分析
List是一种可在常数时间内在任何位置执行插入和删除操作的顺序容器。list是双向链表，其迭代器是双向的。与其他顺序容器(array, vector, deque)相比，list
容器在任意位置执行插入、提取、和移动元素的操作更高效，但它不能通过在容器中的位置直接获取元素。
（2）list中的一些主要函数（注意，自己仅仅实现了一部分）
Operations
list::splice() ———— 将一个list A中的元素转移到list B的指定位置，并将A中被转移的元素删除。
list::remove() ———— 将list中指定的元素删除。
list::unique() ———— 删除list中具有相同值的元素，只保留第一个。也可以根据条件删除具有相同条件的元素，只保留第一个。
list::merge() ———— 合并两个list，在合并之前两个list应该先排序，合并之后的list依然有序。也可以自定义排序的条件。
list::sort() ———— 对list中的元素进行排序，变更它们在容器中的位置。sort()还可以按给定条件进行排序。
list::reverse() ——_ 改变list中元素的顺序。
（3）list的实现
a 构造函数 MyList(const MyList<T>& list0)
template<class T>
MyList<T>::MyList(const MyList<T>& list0)
{
size = list0.size;
node *cur0 = list0.head;
node *tp = new node;
tp->data = http://www.mamicode.com/cur0->data;>b +=重载（注意自加）
// MyList 的+= 感觉可以改进的，别两个while了
MyList<T>& operator += (const MyList<T>& list)
{
if(list.head == (*this).head)
{// meichuli
//cout << "****" << endl;
MyList<T> other(list);
//cout << "&&&&&" << endl;
return *this += other;
}
if(NULL == list.head)// list 空串
return *this;
node *cur = list.head;
node *tp = new node;
tp->data = http://www.mamicode.com/cur->data;>
c 友元类（内部类）
//Iterator class
class MyIterator
{
friend class MyList<T>;
protected:
node* Iter;
MyIterator(node *iter)
{
Iter = iter;
}
public:
MyIterator(){}
// 先加上
MyIterator& operator ++()
{
Iter = Iter->next;
return *this;
}
// 先减去
MyIterator& operator --()
{
Iter = Iter->last;
return *this;
}
MyIterator& operator = (MyIterator& it)
{
Iter = it.Iter;
return *this;
}
bool operator ==(const MyIterator& iter)
{
return Iter==iter.Iter?true:false;
}
bool operator !=(const MyIterator& iter)
{
return Iter!=iter.Iter?true:false;
}
T operator *()
{
return Iter->data;
}
MyIterator &operator[](int n)
{
for(int i=0;i<n;i++)
{
assert(NULL!=Iter);
Iter=Iter->next;
}
return *this;
}
MyIterator &operator +(int n)
{
for(int i=0;i<n;i++)
{
assert(NULL!=Iter);
Iter=Iter->next;
}
return *this;
}
};// MyIterator 内部类
d 字符串反转
// reverse 对于同一个串进行交换。。
template<class T>
void MyList<T>::reserve(MyIterator& it1,MyIterator& it2)
{
node *le = it1.Iter;
node *ri = it1.Iter;
int c = 1;
// 不是很理解的
for(;ri!=it2.Iter;ri=ri->next)
{
c++;
}
for(;c>1;c-=2)
{
// 值交换，指针交换？？
le->data ^= ri->data;
ri->data ^= le->data;
le->data ^= ri->data;
le = le->next;
ri = ri->last;
}
}e 移除指定元素
// remove value
template<class T>
void MyList<T>::remove(T val)
{
node *tp = head;
for(;tp!=NULL;)
{
if(tp->data=http://www.mamicode.com/=val)>
（4）完整代码如下：MyList.h
#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED
#include <iostream>
#include <cassert>
#include <cstdio>
#include <string>
using namespace std;
template<class T>
class MyList
{
friend class MyIterator;
protected:
struct node
{
T data;
node *next;
node *last;
};
private:
node *head;
node *rear;
int size;
public:
//constructor
MyList();
MyList(const MyList<T>&);
MyList(T,int);
MyList(T);
//disconstructor
~MyList(){this->clear();}
//Iterator class
class MyIterator
{
friend class MyList<T>;
protected:
node* Iter;
MyIterator(node *iter)
{
Iter = iter;
}
public:
MyIterator(){}
// 先加上
MyIterator& operator ++()
{
Iter = Iter->next;
return *this;
}
// 先减去
MyIterator& operator --()
{
Iter = Iter->last;
return *this;
}
MyIterator& operator = (MyIterator& it)
{
Iter = it.Iter;
return *this;
}
bool operator ==(const MyIterator& iter)
{
return Iter==iter.Iter?true:false;
}
bool operator !=(const MyIterator& iter)
{
return Iter!=iter.Iter?true:false;
}
T operator *()
{
return Iter->data;
}
MyIterator &operator[](int n)
{
for(int i=0;i<n;i++)
{
assert(NULL!=Iter);
Iter=Iter->next;
}
return *this;
}
MyIterator &operator +(int n)
{
for(int i=0;i<n;i++)
{
assert(NULL!=Iter);
Iter=Iter->next;
}
return *this;
}
};// MyIterator 内部类
// public:// 功能函数
MyList<T> sublist(MyIterator&,MyIterator&);
MyList<T> sublist(MyIterator&,int);
MyList<T> sublist(MyIterator&);
void push_back(const T);
void push_front(const T);
void pop_back();
void pop_front();
void clear();
void reserve();
void reserve(MyIterator&,MyIterator&);
void replace(T,T);
void swap(MyList<T>&);
void display();
void display_rear();
void insert(MyIterator&,T);
void f_insert(MyIterator&,T);
void remove(T);
bool exist(T);
bool up_order();
bool down_order();
int get_size(){return size;}
// swap 值
friend void swap(MyIterator& it1,MyIterator& it2)
{
(it1.Iter)->data ^= (it2.Iter)->data;
(it2.Iter)->data ^= (it1.Iter)->data;
(it1.Iter)->data ^= (it2.Iter)->data;
}
// erase 当前的it,返回it->next
MyIterator erase(MyIterator& it)
{
assert(0 != size);
size--;
if(0 == size)
{
head = NULL;
rear = NULL;
return MyIterator(NULL);
}
if(it.Iter == head)
{
node *tp = head;
head = head->next;
head->last = NULL;
delete(tp);
return MyIterator(head);
}
if(it.Iter == rear)
{
node *tp = rear;
rear = rear->last;
rear->next = NULL;
delete(tp);
return MyIterator(NULL);
}
(it.Iter)->last->next = (it.Iter)->next;
(it.Iter)->next->last = (it.Iter)->last;
node *ans = it.Iter->next;
delete(it.Iter);
return MyIterator(ans);// 返回结果
}
// find 返回ter指针
MyIterator find(T val)
{
node *tp = head;
for(;tp!=NULL;tp=tp->next)
{
if((tp->data)==val) return MyIterator(tp);
}
return MyIterator(NULL);
}
MyIterator begin(){return MyIterator(head);}
MyIterator end(){return MyIterator(rear);}
T& front(){return head->data;}
T& back(){return rear->data;}
bool empty(){return 0==size?true:false;}
void link(MyList<T>& list0){*this += list0;}
void reset(MyIterator& it,T val){(it.Iter)->data = http://www.mamicode.com/val;}>
(5) 测试韩式main
#include "MyList.h"
using namespace std;
int main()
{
MyList<string> list0;
MyList<string> list7("ccc",3);
list0 += list7;
list0.display_rear();
string tmp = "aaa";
list0.push_back(tmp);
list0.push_front("bbbb");
list7.display();
list0 += list0;
list0.display_rear();
cout << "1: " << list0.get_size() << " ," << endl;
//MyList<string> list1(tmp);
list0.clear();
//list1.display();
//list1.clear();
//list1.display();
MyList<int> list1(5,4);
list1.push_back(1111);
MyList<int>::MyIterator it = list1.begin();
//++it;
list1.insert(it+2,2222);
list1.f_insert(it,555);
//list1.push_front(5555);
//list1.pop_back();
//list1.pop_front();
cout << "2: " << list1.get_size() << ", ";
list1.display();
MyList<int> list2(list1);
cout << "3: " << list2.get_size() << ", ";
list2.display();
list2.reserve(list2.begin()+2,list2.begin()+4);
list2.display_rear();
MyList<int> list3(3,6);
list3.swap(list1);
list1.reserve();
cout << "4: " << list1.get_size() << ",";
list1.display();
list1.push_back(33);
cout << "5:" << list1[6] << ",," << list1.down_order() << list1.up_order() << endl;
//list1.display_rear();
MyList<int> list4= list2.sublist(list2.begin()+2,list2.begin()+4);
list4.display();
return 0;
}
STL 之 list源代码自行实现（iterator）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。