目錄
- 一、list的介紹
- 二、list的使用
- 2.1 list的構(gòu)造函數(shù)
- 2.2 list迭代器的使用
- 2.3 list相關(guān)的容量大小相關(guān)的函數(shù)
- 2.4 list數(shù)據(jù)的訪問相關(guān)的函數(shù)
- 2.5 list的數(shù)據(jù)調(diào)整相關(guān)的函數(shù)
- 2.6 list中其他函數(shù)操作
一、list的介紹
list的介紹
- list是可以以O(shè)(1)的時(shí)間復(fù)雜度任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
- list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過指針指向其前一個(gè)元素和后一個(gè)元素。
- list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡(jiǎn)單高效。
- 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
- 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問，比如：要訪問list的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間開銷；list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類型較小元素的大list來說這可能是一個(gè)重要的因素)
二、list的使用
2.1 list的構(gòu)造函數(shù)
| 構(gòu)造函數(shù) |
接口說明 |
| list() |
空構(gòu)造 |
| list (size_type n, const value_type& val = value_type()) |
初始化的list中包含n個(gè)val值 |
| list (const list& x) |
拷貝構(gòu)造函數(shù) |
| list (InputIterator first, InputIterator last) |
用迭代器區(qū)間[first,last)構(gòu)造list |
void test_list1()
{
// 空構(gòu)造
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (int e: l1)
{
cout << e << " ";
}
cout << endl;
// 初始化的list中包含n個(gè)val值
list<int> l2(4,10);
for (int e : l2)
{
cout << e << " ";
}
cout << endl;
// 拷貝構(gòu)造函數(shù)
list<int> l3(l1);
for (int e : l3)
{
cout << e << " ";
}
cout << endl;
// 用迭代器區(qū)間[first,last)構(gòu)造list
list<int> l4(l3.begin(), l3.end());
for (int e : l4)
{
cout << e << " ";
}
}
2.2 list迭代器的使用
| 函數(shù)聲明 |
接口說明 |
| begin+end |
返回第一個(gè)元素的迭代器+返回最后一個(gè)元素的下一個(gè)位置的迭代器 |
| rbegin+rend |
返回end位置+返回begin位置 |
// 正\反向迭代器
void test_list2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
// 正向迭代器
list<int>::iterator it = lt.begin();
while (it!=lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 反向迭代器
list<int>::reverse_iterator rit = lt.rbegin();
while (rit!=lt.rend())
{
cout << *rit << " ";
++rit;
}
}
2.3 list相關(guān)的容量大小相關(guān)的函數(shù)
| 函數(shù)聲明 |
接口說明 |
| empty |
檢測(cè)list是否為空，是返回true，否返回false |
| size |
返回list中有效結(jié)點(diǎn)的個(gè)數(shù) |
void test_list3()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
cout << l1.size() << endl; // 4
cout << l1.empty() << endl;// 0
}
2.4 list數(shù)據(jù)的訪問相關(guān)的函數(shù)
| 函數(shù)聲明 |
接口說明 |
| front |
返回list中的第一個(gè)結(jié)點(diǎn)值的引用 |
| back |
返回list中最后一個(gè)結(jié)點(diǎn)值的引用 |
void test_list4()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
cout << l1.front() << endl; // 1
cout << l1.back() << endl; // 4
}
2.5 list的數(shù)據(jù)調(diào)整相關(guān)的函數(shù)
| 函數(shù)聲明 |
接口說明 |
| push_front |
在首元素前插入元素 |
| pop_front |
刪除第一個(gè)元素 |
| push_back |
尾插 |
| pop_back |
尾刪 |
| insert |
在pos位置插入值 |
| erase |
刪除pos位置的值 |
| swap |
交換兩個(gè)list中的值 |
| clear |
清空l(shuí)ist中的有效元素 |
void test_list5()
{
list<int> l;
l.push_back(1);
l.push_front(2);
list<int>::iterator it = l.begin();
++it;
l.insert(it, 20);
for (int e : l)
{
cout << e << " ";
}
cout << endl;
cout << "------" << endl;
l.clear();
for (int e : l)
{
cout << e << " ";
}
}
2.6 list中其他函數(shù)操作
| 函數(shù)聲明 |
接口說明 |
| sort |
排序 |
| reverse |
逆置 |
| unique |
去重(去重之前一般需要先排序) |
| remove |
刪除給定的一個(gè)值 |
void test_list6()
{
list<int> l1;
l1.push_back(1);
l1.push_back(7);
l1.push_back(3);
l1.push_back(3);
l1.push_back(3);
l1.push_back(4);
// 排序
l1.sort();
for (int e : l1)
{
cout << e << " ";
}
cout << endl;
// 逆置
l1.reverse();
for (int e : l1)
{
cout << e << " ";
}
cout << endl;
// 去重
l1.unique();
for (int e : l1)
{
cout << e << " ";
}
cout << endl;
// 刪除給定的一個(gè)值
l1.remove(7);
for (int e : l1)
{
cout << e << " ";
}
cout << endl;
}
提供CDN加速