list的底层结构
list底层是一个带头节点的双向循环链表，任意位置插入和删除时间复杂度0(1)
list迭代器
由于list底层是带头节点的双向循环链表，因此list的迭代器需要list的实现者自己提供
迭代器怎么实现呢？
迭代器的本质是指针，将指针封装出新的类型，指针有的操作，迭代器也视情况支持这些操作，比如：指针 ，–，*，-> 等操作。迭代器在类中将这些操作重载出来即可，然后将list迭代器看作list的一种内部类型使用。
list的操作
iterators: 迭代器
begin()
end()
rbegin() //重置后的开始
rend() //重置后的结尾
capacity:
empty（）
size（） //有效元素个数
resize（） //重置有效元素个数
element access:
front //返回第一个引用
back //返回最后一个引用
modifiers:
push_front
pop_front
push_back
pop_back
insert //任意位置插入
erase //任意位置删除
swap //交换两个list
clear //情空
operations:
remove //按条件删除元素
remove_if
unique //去重
merge //合并两个有序链表
sort //单链表排序
reversr //单链表的逆置
#include
#include
using namespace std;
void testlist1()
{
//构造空的list
listl1;
//构造10个值为1的list
listl2(10, 1);
//构造用一段区间中的元素构造list
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list l3(arr, arr sizeof(arr) / sizeof(arr[0]));
//用l3取构造l4
listl4(l3);
cout << "l1元素个数:" << l1.size() << endl;
cout << "l2元素个数:" << l2.size() << endl;
cout << "l3元素个数:" << l3.size() << endl;
cout << "l4元素个数:" << l4.size() << endl;
//遍历list1
list::iterator it1 = l1.begin();
while (it1 != l1.end())
{
cout << *it1 << " ";
it1;
}
cout << endl;
//遍历list2
list::iterator it2 = l2.begin();
while (it2 != l2.end())
{
cout << *it2 << " ";
it2;
}
cout << endl;
//遍历list3
list::iterator it3 = l3.begin();
while (it3 != l3.end())
{
cout << *it3 << " ";
it3;
}
cout << endl;
//遍历list4
list::iterator it4 = l4.begin();
while (it4 != l4.end())
{
cout << *it4 << " ";
it4;
}
cout << endl;
//逆向遍历list4
list::reverse_iterator it5 = l4.rbegin();
while (it5 != l4.rend())
{
cout << *it5 << " ";
it5;
}
cout << endl;
}
void testlist2()
{
listl;
//尾插
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
l.push_back(6);
list::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
//尾删
l.pop_back();
l.pop_back();
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
//头插
l.push_front(0);
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
l.pop_front();
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
任意位置的插入
//list::iterator pos = find(l.begin(), l.end(), 2);
//if (pos != l.end())
// pos = l.insert(pos, 9);
//it = l.begin();
//while (it != l.end());
//{
// cout << *it << " ";
// it;
//}
//cout << endl;
任意位置删除、
//l.erase(pos);
//it = l.begin();
//while (it != l.end())
//{
// cout << *it << " ";
// it;
//}
//cout << endl;
//给list重新赋值
int arr[] = { 1,2,3, 4, 5, 6, 7, 8, 9 };
l.assign(arr, arr sizeof(arr) / sizeof(arr[0]));
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
cout << "第一个元素" << l.front() << endl;
cout << "第一个元素" << l.back() << endl;
}
void testlist3()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
listl(arr, arr sizeof(arr) / sizeof(arr[0]));
list::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
l.remove(3); //按值删除
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
class odd
{
public:
bool operator()(int value)
{
return value & 0x01;
};
};
l.remove_if(odd());
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
}
void testlist4()
{
int arr[] = { 1, 2, 5, 3,1, 2, 3, 4, 5,7,6, 8, 9 };
listl(arr, arr sizeof(arr) / sizeof(arr[0]));
l.unique();
list::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
l.sort();
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
l.unique();
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
//class three
//{
//public:
// bool operator()(int left, int right)
// {
// return 0 == (left right) % 3;
// }
//};
//l.unique(three());
//it = l.begin();
//while (it != l.end());
//{
// cout << *it << " ";
// it;
//}
//cout << endl;
}
void testlist5()
{
listl;
l.push_back(1);
l.push_back(4);
l.push_back(6);
listl2;
l2.push_back(2);
l2.push_back(3);
l2.push_back(8);
//将两个已序链表合并成为一个链表，合并后依然有序
l.merge(l2);
list::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
//反转链表
l.reverse();
it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it;
}
cout << endl;
}
int main()
{
//testlist1(); 构造及其遍历
//testlist2();
//testlist3();
//testlist4();
//testlist5();
return 0;
}