C++ 泛型编程：list 容器

作者
内容 隐藏
1 list 基本概念
2 list 构造函数
3 list 赋值和交换
4 list 大小操作
5 list 插入和删除
6 list 数据存取
7 list 反转和排序

list 基本概念

  • list 容器将数据进行链式存储，是一个双向循环链表
  • list 存储方式不是连续存储空间，迭代器只能前移和后移，属于双向迭代器
  • list 数据元素的逻辑顺序是通过指针链实现的
  • list 由一系列结点组成。节点由数据域和指针域构成
  • list 插入和删除不会造成原迭代器失效，这对 vector 是不成立的
  • list 和 vector 是最常被使用的容器

list 优点：

  • list 可以对任意位置进行快速插入和删除
  • 采用动态存储分配，不会造成内存的浪费和移除

list 缺点：

  • list 遍历速度没有 vector 快
  • list 占用的控件比 vector 大

list 构造函数

  • list<T> li1;
  • list<T> li2( li1.begin(), li1.end() ); // [ begin, end )，左闭右开
  • list<T> li3( n, elem );
  • list<T> li4( const list& lst )
void list_print(const list<int>& li)
{
	for (list<int>::const_iterator it = li.begin(); it != li.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void list_constructor()
{
	list<int> li1;
	li1.push_back(10);
	li1.push_back(20);
	li1.push_back(30);
	li1.push_back(40);
	list_print(li1);

	list<int> li2(li1.begin(), li1.end());
	list_print(li2);

	list<int> li3(li2);
	list_print(li3);

	list<int> li4(10, 1000);
	list_print(li4);
}

list 赋值和交换

  • list& operator=( const list& lst );
  • void assign( li.begin(), li.end() ); // [ begin, end )，左闭右开
  • void assign( n, elem);
  • void swap( list& lst );
void list_assign()
{
	list<int> li1;
	li1.push_back(10);
	li1.push_back(20);
	li1.push_back(30);
	li1.push_back(40);
	list_print(li1);

	list<int> li2 = li1;
	list_print(li2);

	list<int> li3;
	li3.assign(li2.begin(), li2.end());
	list_print(li3);

	list<int> li4;
	li4.assign(10, 100);
	list_print(li4);
}

void list_swap()
{
	list<int> li1;
	li1.push_back(10);
	li1.push_back(20);
	li1.push_back(30);
	li1.push_back(40);
	list_print(li1);

	list<int> li2;
	li2.assign(10, 100);

	cout << "交换前：" << endl;
	list_print(li1);
	list_print(li2);
	cout << "交换后：" << endl;
	li1.swap(li2);
	list_print(li1);
	list_print(li2);
}

list 大小操作

  • bool empty();
  • int size();
  • void resize( int num );
  • void resize ( int num, elem );
void list_size()
{
	list<int> li;
	li.push_back(10);
	li.push_back(20);
	li.push_back(30);
	li.push_back(40);
	list_print(li);

	if (li.empty())
	{
		cout << "li 为空" << endl;
	}
	else
	{
		cout << "li 不为空" << endl;
		cout << "li 的元素个数为：" << li.size() << endl;
	}

	li.resize(10);
	list_print(li);

	li.resize(15, 10000);
	list_print(li);

	li.resize(2);
	list_print(li);
}

list 插入和删除

  • void push_back( elem );
  • void pop_back();
  • void push_front( elem );
  • void pop_front();
  • iterator insert( const_iterator pos, elem );
  • iterator insert( const_iterator pos, int count, elem );
  • iterator insert( const_iterator pos, li.begin(), li.end() );
  • iterator erase( const_iterator pos);
  • iterator erase( li.begin(), li.end() );
  • void remove( elem )
  • void clear();
void list_insertAndErase()
{
	list<int> li;

	li.push_back(10);
	li.push_back(20);
	li.push_back(30);
	li.push_front(100);
	li.push_front(200);
	li.push_front(300);
	list_print(li);

	li.pop_back();
	li.pop_front();
	list_print(li);

	li.insert(++li.begin(), 1000);
	list_print(li);

	li.erase(li.begin());
	list_print(li);

	li.push_back(10000);
	li.push_back(10000);
	li.push_back(10000);
	li.push_back(10000);
	list_print(li);
	li.remove(10000);
	list_print(li);

	li.clear();
	list_print(li);
}

list 数据存取

  • T& front();
  • T& back();
  • 迭代器支持 it++ 和 it--，但是不支持 it += 1 和 it -= 1
void list_frontAndBack()
{
	list<int> li;
	li.push_back(10);
	li.push_back(20);
	li.push_back(30);
	li.push_back(40);

	cout << "第一个元素：" << li.front() << endl;
	cout << "最后一个元素：" << li.back() << endl;
}

list 反转和排序

  • void reverse();
  • void sort();
  • 注意，不支持随机访问迭代器的容器，会提供对应的成员函数用于排序
bool compare(int num1, int num2)
{
	return num1 > num2;
}

void list_sort()
{
	list<int> li;
	li.push_back(20);
	li.push_back(10);
	li.push_back(50);
	li.push_back(40);
	li.push_back(30);
	list_print(li);

	li.sort();
	list_print(li);

	li.sort(compare);
	list_print(li);
}

排序案例：

class Person
{
public:
	string m_name;
	int m_age;
	int m_height;

	Person(string name, int age, int height)
	{
		this->m_name = name;
		this->m_age = age;
		this->m_height = height;
	}
};

bool comparePerson(Person& p1, Person& p2)
{
	if (p1.m_age != p2.m_age)
	{
		return p1.m_age < p2.m_age;
	}
	return p1.m_height > p2.m_height;
}

void list_sortExample()
{
	list<Person> li;
	li.push_back(Person("刘备", 35, 175));
	li.push_back(Person("曹操", 45, 180));
	li.push_back(Person("孙权", 40, 170));
	li.push_back(Person("赵云", 25, 190));
	li.push_back(Person("张飞", 35, 160));
	li.push_back(Person("关羽", 35, 200));

	for (list<Person>::iterator it = li.begin(); it != li.end(); it++)
	{
		cout << "姓名：" << (*it).m_name << "年龄：" << (*it).m_age << "身高：" << (*it).m_height << endl;
	}

	cout << "-------------------------------------" << endl;
	cout << "排序后：" << endl;

	li.sort(comparePerson);
	for (list<Person>::iterator it = li.begin(); it != li.end(); it++)
	{
		cout << "姓名：" << (*it).m_name << "年龄：" << (*it).m_age << "身高：" << (*it).m_height << endl;
	}
}