​​

list的认识与使用

• list的介绍
• list的使用
• • Member functions（成员函数）
  • • constuctor（构造函数）
    • destructor（析构函数）
    • operator=（赋值构造）
  • Iterators（迭代器）
  • • begin
    • end
    • rbegin
    • rend
  • Capacity（容量）
  • • empty
    • size
    • max_size
  • Element access（元素访问）
  • • front
    • back
  • Modifiers（修饰符）
  • • assign
    • push_front
    • pop_front
    • push_back
    • pop_back
    • insert
    • erase
    • swap
    • resize
    • clear
  • Operations（操作）
  • • reverse
    • sort
  • Non-member function overloads（非成员函数重载）
  • • relational operators (list)
    • swap (list)

list的介绍

​​

• std::list
• template < class T, class Alloc = allocator > class list;

1.list是可以在常数范围内可以在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2.list的底层是双向链表结构，双向链表中的每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3.list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，比起更加简单高效。

4.与其他的序列式容器相比（array，vector，deque），list通常在任意位置进行插入，移除元素的执行效率更好。

5.与其他的序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息（对于存储类型较小元素的大list来说这可能是一个重要的因素）。

list的使用

Member functions（成员函数）

constuctor（构造函数）

• std::list::list
• 构造链表
• default (1)
  explicit list (const allocator_type& alloc = allocator_type());
  空容器构造函数（默认构造函数）

	list lt1; 

• fill (2)
  explicit list (size_type n, const value_type& val = value_type(),
  const allocator_type& alloc = allocator_type());
  多参数构造函数

	list lt2(4, 100); 

• range (3)
  template < class InputIterator >
  list (InputIterator first, InputIterator last,
  const allocator_type& alloc = allocator_type());
  范围构造函数

	list lt3(lt2.begin(), lt2.end()); 

• copy (4)
  list (const list& x);
  拷贝构造函数

	list lt4(lt3); 

destructor（析构函数）

• std::list::~list
• ~list();
• list的析构函数

operator=（赋值构造）

• std::list::operator=

• copy (1)
  list& operator= (const list& x);

• 分配内容

	list lt1; 	list lt2(4, 100);  	lt1 = lt2; 

Iterators（迭代器）

begin

• std::list::begin

• iterator begin();

• const_iterator begin() const;

• 返回指向开始的迭代器

end

• std::list::end
• iterator end();
• const_iterator end() const;
• 返回指向结尾的迭代器

	list lt(4, 100); 	list::iterator it = lt.begin(); 	while (it != lt.end()) 	{ 		cout << *it << " "; 		++it; 	} 	cout << endl; 

rbegin

• std::list::rbegin
• reverse_iterator rbegin();
• const_reverse_iterator rbegin() const;
• 返回指向反向开始的反向迭代器

rend

• std::list::rend
• reverse_iterator rend();
• const_reverse_iterator rend() const;
• 返回指向反向结尾的反向迭代器

	list lt(4, 100); 	list::iterator it = lt.end(); 	while (it != lt.begin()) 	{ 		cout << *it << " "; 		--it; 	} 	cout << endl; 

【注意】
1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。

Capacity（容量）

empty

• std::list::empty
• bool empty() const;
• 检测容器是否为空

	list lt(2, 5); 	cout << lt.empty() << endl; 

size

• std::list::size
• size_type size() const;
• 返回list中有效节点的个数

	list lt(2, 5); 	cout << lt.size() << endl; 

max_size

• std::list::max_size
• size_type max_size() const;
• 返回容器最大字节

	list lt; 	cout << lt.max_size() << endl; 

Element access（元素访问）

front

• std::list::front
• reference front();
• const_reference front() const;
• 返回list的第一个节点中值的引用

	list lt(5, 20); 	cout << lt.front() << endl; 

back

• std::list::back
• reference back();
• const_reference back() const;
• 返回list的最后一个节点中值的引用

	list lt(5, 20); 	cout << lt.back() << endl; 

Modifiers（修饰符）

assign

• std::list::assign
• range (1)
  template < class InputIterator >
  void assign (InputIterator first, InputIterator last);
• fill (2)
  void assign (size_type n, const value_type& val);
• 分配新的内容给容器

	list lt1; 	list lt2;  	lt1.assign(4, 12); 	lt2.assign(lt1.begin(), lt1.end()); 

push_front

• std::list::push_front
• void push_front (const value_type& val);
• 在list首元素前插入值为val的元素

	list lt1; 	lt1.assign(4, 12); 	lt1.push_front(1); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

pop_front

• std::list::pop_front
• void pop_front();
• 删除list中第一个元素

	list lt1; 	lt1.assign(4, 12); 	lt1.pop_back(); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

push_back

• std::list::push_back
• void push_back (const value_type& val);
• 在list尾部插入值为val的元素

	list lt1; 	lt1.assign(4, 12); 	lt1.push_back(1); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

pop_back

• std::list::pop_front
• void pop_front();
• 删除list中最后一个元素

	list lt1; 	lt1.assign(4, 12); 	lt1.pop_front(); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

insert

• std::list::insert
• single element (1)
  iterator insert (iterator position, const value_type& val);
• fill (2)
  void insert (iterator position, size_type n, const value_type& val);
• range (3)
  template < class InputIterator>
  void insert (iterator position, InputIterator first, InputIterator last);
• 在list position位置插入值为val的元素

	list lt1; 	lt1.push_back(1); 	lt1.push_back(2); 	lt1.push_back(3); 	lt1.push_back(4); 	list::iterator it = lt1.begin(); 	++it; 	lt1.insert(it, 19); 

erase

• std::list::erase
• iterator erase (iterator position);
• iterator erase (iterator first, iterator last);
• 删除list position位置中插入值为val的元素

	list lt1; 	lt1.push_back(1); 	lt1.push_back(2); 	lt1.push_back(3); 	lt1.push_back(4); 	list::iterator it = lt1.begin(); 	++it; 	lt1.erase(it); 

swap

• std::list::swap
• void swap (list& x);
• 交换list中的有效元素

	list lt1(3, 5); 	list lt2(4, 2); 	lt1.swap(lt2) 

resize

• std::list::resize
• void resize (size_type n, value_type val = value_type());
• 改变大小

	list lt1(3, 5); 	lt1.resize(10, 1); 

clear

• std::list::clear
• void clear();
• 清空list中的有效元素

	list lt1(3, 5); 	lt1.clear(); 

Operations（操作）

reverse

• std::list::reverse
• void reverse();
• 翻转列表

	list lt1; 	lt1.push_back(1); 	lt1.push_back(2); 	lt1.push_back(3); 	lt1.push_back(4); 	lt1.reverse(); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

sort

• std::list::sort
• (1) void sort();
• (2) template < class Compare >
  void sort (Compare comp);
• 排序

	list lt1; 	lt1.push_back(2); 	lt1.push_back(3); 	lt1.push_back(1); 	lt1.push_back(4); 	lt1.sort(); 	for (auto t : lt1) 	{ 		cout << t << " "; 	} 	cout << endl; 

Non-member function overloads（非成员函数重载）

relational operators (list)

swap (list)