184、基于范围的 for 循环
对于一个有范围的集合来说，在程序代码中指定循环的范围有时候是多余的，还可能犯错误。
C++11 中引入了基于范围的 for 循环。
语法：
for (迭代的变量 : 迭代的范围)
{
// 循环体。
}
注意：
1）迭代的范围可以是数组名、容器名、初始化列表或者可迭代的对象（支持 begin()、end()、++、
==）。
2）数组名传入函数后，已退化成指针，不能作为容器名。
3）如果容器中的元素是结构体和类，迭代器变量应该申明为引用，加 const 约束表示只读。
4）注意迭代器失效的问题。
示例：
#include <iostream>
#include <vector>
using namespace std;
class AA
{
public:
string m_name;
AA() { cout << "默认构造函数 AA()。\n"; }
AA(const string& name) : m_name(name) { cout << "构造函数，name=" << m_name <<
"。\n"; }
AA(const AA& a) : m_name(a.m_name) { cout << "拷贝构造函数，name=" << m_name <<
"。\n"; }
AA& operator=(const AA& a) { m_name = a.m_name; cout << "赋值函数，name=" <<
m_name << "。\n"; return *this; } ~AA() { cout << "析构函数，name=" << m_name<<"。\n"; }
};
int main()
{
vector<int> vv = { 1,2,3,4,5,6,7,8,9,10 };
//for (auto it = vv.begin(); it != vv.end(); it++) // 用迭代器遍历容器 vv。
//{
// cout << *it << " ";
//}
//cout << endl;
for (auto val : vv) // 用基于范围的 for 循环遍历数组 vv。
{
cout << val << " ";
vv.push_back(10);
}
cout << endl;
/*vector<AA> v;
cout << "1111，v.capacity()=" << v.capacity() << "\n";
v.emplace_back("西施");
cout << "2222，v.capacity()=" << v.capacity() << "\n";
v.emplace_back("冰冰");
cout << "3333，v.capacity()=" << v.capacity() << "\n";
v.emplace_back("幂幂");
cout << "4444，v.capacity()=" << v.capacity() << "\n";
for (const auto &a : v)
cout << a.m_name << " ";
cout << endl;*/
}
185、list 容器
list 容器封装了双链表。
包含头文件： #include<list>
list 类模板的声明：
template<class T, class Alloc = allocator<T>>
class list{
private:
iterator head;
iterator tail; ……
} 一、构造函数
1）list(); // 创建一个空的 list 容器。
2）list(initializer_list<T> il); // 使用统一初始化列表。
3）list(const list<T>& l); // 拷贝构造函数。
4）list(Iterator first, Iterator last); // 用迭代器创建 list 容器。
5）list(list<T>&& l); // 移动构造函数（C++11 标准）。
6）explicit list(const size_t n); // 创建 list 容器，元素个数为 n。
7）list(const size_t n, const T& value); // 创建 list 容器，元素个数为 n，值均为 value。
析构函数~list()释放内存空间。
示例：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
// 1）list(); // 创建一个空的 list 容器。
list<int> l1;
// cout << "li.capacity()=" << l1.capacity() << endl; // 链表没有容量说法。
cout << "li.size()=" << l1.size() << endl;
// 2）list(initializer_list<T> il); // 使用统一初始化列表。
list<int> l2({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
// list<int> l2={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// list<int> l2 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int value : l2) // 用基于范围的 for 循环遍历容器。
cout << value << " ";
cout << endl;
// 3）list(const list<T>& l); // 拷贝构造函数。
list<int> l3(l2);
// list<int> l3=l2;
for (int value : l3)
cout << value << " ";
cout << endl;
// 4）list(Iterator first, Iterator last); // 用迭代器创建 list 容器。
list<int> l4(l3.begin(), l3.end()); // 用 list 容器的迭代器。
for (int value : l4)
cout << value << " ";
cout << endl;
vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 创建 vector 容器。
list<int> l5(v1.begin() + 2, v1.end() - 3); // 用 vector 容器的迭代器创建 list 容器。
for (int value : l5)
cout << value << " ";
cout << endl;
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 创建数组。
list<int> l6(a1 + 2, a1 + 10 - 3); // 用数组的指针作为迭代器创建 list 容器。
for (int value : l6)
cout << value << " ";
cout << endl;
char str[] = "hello world"; // 定义 C 风格字符串。
string s1(str + 1, str + 7); // 用 C 风格字符串创建 string 容器。
for (auto value : s1) // 遍历 string 容器。
cout << value << " ";
cout << endl;
cout << s1 << endl; // 以字符串的方式显示 string 容器。
vector<int> v2(l3.begin(), l3.end()); // 用 list 迭代器创建 vector 容器。
for (auto value : v2) // 遍历 vector 容器。
cout << value << " ";
cout << endl;
}
二、特性操作
size_t max_size() const; // 返回容器的最大长度，此函数意义不大。
size_t size() const; // 返回容器的实际大小（已使用的空间）。
bool empty() const; // 判断容器是否为空。
void clear(); // 清空容器。
void resize(size_t size); // 把容器的实际大小置为 size。
void resize(size_t size,const T &value); // 把容器的实际大小置为 size，如果 size<实际大小，
会截断多出的部分；如果 size>实际大小，就用 value 填充。 三、元素操作
T &front(); // 第一个元素。
const T &front(); // 第一个元素，只读。
const T &back(); // 最后一个元素，只读。
T &back(); // 最后一个元素。 四、赋值操作
给已存在的容器赋值，将覆盖容器中原有的内容。
1）list &operator=(const list<T> &l); // 把容器 l 赋值给当前容器。
2）list &operator=(initializer_list<T> il); // 用统一初始化列表给当前容器赋值。
3）list assign(initializer_list<T> il); // 使用统一初始化列表赋值。
4）list assign(Iterator first, Iterator last); // 用迭代器赋值。
5）void assign(const size_t n, const T& value); // 把 n 个 value 给容器赋值。 五、交换、反转、排序、归并
void swap(list<T> &l); // 把当前容器与 l 交换，交换的是链表结点的地址。
void reverse(); // 反转链表。
void sort(); // 对容器中的元素进行升序排序。
void sort(_Pr2 _Pred); // 对容器中的元素进行排序，排序的方法由_Pred 决定（二元函数）。
void merge(list<T> &l); // 采用归并法合并两个已排序的 list 容器，合并后的 list 容器仍是有序
的。
示例：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
list<int> la = { 8,2,6,4,5 };
for (auto &val : la)
cout << val << " ";
cout << endl;
la.reverse(); // 反转链表。
for (auto& val : la)
cout << val << " ";
cout << endl;
la.sort(); // 链表排序。
for (auto& val : la)
cout << val << " ";
cout << endl;
list<int> lb = { 3,7,9,10,1 };
lb.sort(); // 链表排序。
la.merge(lb); // 归并链表。
for (auto& val : la)
cout << val << " ";
cout << endl;
}
六、比较操作
bool operator == (const vector<T> & l) const;
bool operator != (const vector<T> & l) const;
七、插入和删除
1）void push_back(const T& value); // 在链表的尾部追加一个元素。
2）void emplace_back(…); // 在链表的尾部追加一个元素，…用于构造元素。C++11
3）iterator insert(iterator pos, const T& value); // 在指定位置插入一个元素，返回指向插入元
素的迭代器。
4）iterator emplace (iterator pos, …); // 在指定位置插入一个元素，…用于构造元素，返回指向
插入元素的迭代器。C++11
5）iterator insert(iterator pos, iterator first, iterator last); // 在指定位置插入一个区间的元素，
返回指向第一个插入元素的迭代器。
6）void pop_back(); // 从链表尾部删除一个元素。
7）iterator erase(iterator pos); // 删除指定位置的元素，返回下一个有效的迭代器。
8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。
9）push_front(const T& value); // 在链表的头部插入一个元素。
10）emplace_front(…); // 在链表的头部插入一个元素，…用于构造元素。C++11
11）splice(iterator pos, const vector<T> & l); // 把另一个链表连接到当前链表。
12）splice(iterator pos, const vector<T> & l, iterator first, iterator last); // 把另一个链表指
定的区间连接到当前链表。
13）splice(iterator pos, const vector<T> & l, iterator first); // 把另一个链表从first开始的结
点连接到当前链表。
14）void remove(const T& value); // 删除链表中所有值等于 value 的元素。
15）void remove_if(_Pr1 _Pred); // 删除链表中满足条件的元素，参数_Pred 是一元函数。
16）void unique(); // 删除链表中相邻的重复元素，只保留一个。
17）void pop_front(); // 从链表头部删除一个元素。
示例：
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
list<int> la = { 8,2,6,4,5 };
for (auto& val : la) cout << val << " ";
cout << endl;
list<int> lb = { 3,7,9,10,1 };
for (auto& val : lb) cout << val << " ";
cout << endl;
auto first = lb.begin();
first++;
auto last = lb.end();
last--;
la.splice(la.begin(), lb, first, last);
for (auto& val : la) cout << val << " ";
cout << endl;
cout << "lb.size()=" << lb.size() << endl;
for (auto& val : lb) cout << val << " ";
cout << endl;
}
八、list 容器的简单实现
以下 demo 程序简单的实现了 list 容器。
示例：
#include<iostream>
using namespace std;
namespace
{
template<class _Ty> class List;
template<class _Ty> class ListIterator;
// 节点类。
template<class _Ty>
class ListNode
{
friend class List<_Ty>;
friend class ListIterator<_Ty>;
public:
ListNode() :_Value(_Ty()), _Next(nullptr), _Prev(nullptr) {}
ListNode(_Ty V, ListNode* next = nullptr, ListNode* prev = nullptr) :_Value(V), _Next(next), _Prev(prev) {}
private: _Ty _Value;
ListNode* _Next;
ListNode* _Prev;
};
// 迭代器。
template<class _Ty>
class ListIterator
{
typedef ListIterator<_Ty> _It;
public:
ListIterator() :_Ptr(nullptr) {}
ListIterator(ListNode<_Ty>* _P) :_Ptr(_P) {}
public: _It& operator++()
{ _Ptr = _Ptr->_Next;
return *this;
}_It& operator--()
{ _Ptr = _Ptr->Prev;
return *this;
}_Ty& operator*()
{
return (_Ptr->_Value);
}
bool operator!=(const _It& it)
{
return _Ptr != it._Ptr;
}
bool operator==(const _It& it)
{
return _Ptr == it._Ptr;
}
ListNode<_Ty>* _Mynode()
{
return _Ptr;
}
private:
ListNode<_Ty>* _Ptr;
};
// 链表类。
template<class _Ty>
class List
{
public:
typedef ListNode<_Ty>* _Nodeptr;
typedef ListIterator<_Ty> iterator;
public:
List() :_Size(0)
{
CreateHead();
}
List(size_t n, const _Ty& x = _Ty()) :_Size(0)
{
CreateHead(), insert(begin(), n, x);
}
List(const _Ty* first, const _Ty* last) :_Size(0)
{
CreateHead();
while (first != last)
push_back(*first++);
}
List(iterator first, iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
++first;
}
}
List(List<_Ty>& lt) :_Size(0)
{
CreateHead();
List<_Ty>tmp(lt.begin(), lt.end());
this->swap(tmp);
}~List()
{
clear();
delete _Head; _Size = 0;
}
public:
void push_back(const _Ty& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const _Ty& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}_Ty& front()
{
return *begin();
}
const _Ty& front()const
{
return *begin();
}_Ty& back()
{
return *--end();
}
const _Ty& back()const
{
return *--end();
}
public:
size_t size()const
{
return _Size;
}
bool empty()const
{
return (size() == 0);
}
public:
iterator begin()
{
return iterator(_Head->_Next);
}
iterator end()
{
return iterator(_Head);
}
void clear()
{
erase(begin(), end());
}
public:
//在_P 位置前插入值为 x 的节点
iterator insert(iterator _P, const _Ty& x)
{ _Nodeptr cur = _P._Mynode(); _Nodeptr _S = new ListNode<_Ty>(x); _S->_Next = cur; _S->_Prev = cur->_Prev; _S->_Prev->_Next = _S; _S->_Next->_Prev = _S; _Size++;
return iterator(_S);
}
void insert(iterator _P, size_t n, const _Ty& x = _Ty())
{
while (n--)
insert(_P, x);
}
//删除_P 位置的节点，返回该节点的下一个节点位置
iterator erase(iterator _P)
{ _Nodeptr cur = _P._Mynode(); _Nodeptr next_node = cur->_Next;
cur->_Prev->_Next = cur->_Next;
cur->_Next->_Prev = cur->_Prev;
delete cur; _Size--;
return iterator(next_node);
}
iterator erase(iterator first, iterator last)
{
while (first != last)
{
first = erase(first);
}
return first;
}
void swap(List<_Ty>& lt)
{
std::swap(_Head, lt._Head);
std::swap(_Size, lt._Size);
}
protected:
void CreateHead()
{ _Head = new ListNode<_Ty>; _Head->_Prev = _Head->_Next = _Head;
}
private: _Nodeptr _Head;
size_t _Size;
};
};
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
List<int>la(arr+2, arr + 10);
List<int>lb(la);
for (auto elem:la)
cout << elem << " ";
cout << endl;
for (auto elem : lb)
cout << elem << " ";
cout << endl;
}