蘇州做網(wǎng)站最好公司寧波靠譜營(yíng)銷(xiāo)型網(wǎng)站建設(shè)
目錄
- 前言
- 一,list的介紹
- 二,list的基本使用
- 2.1 list的構(gòu)造
- 2.2 list迭代器的使用
- 2.3 list的頭插,頭刪,尾插和尾刪
- 2.4 list的插入和刪除
- 2.5 list 的 resize/swap/clear
前言
list中的接口比較多,與string和vector類(lèi)似,只需要掌握如何正確的使用,然后再去深入研究背后的原理,已達(dá)到可擴(kuò)展的能力。本文只介紹list中一些常見(jiàn)的重要接口。
注意:使用list時(shí)需要包含頭文件< list >。
一,list的介紹
- list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器,并且該容器可以前后雙向迭代。
- list的底層是雙向鏈表結(jié)構(gòu),雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中,在節(jié)點(diǎn)中通過(guò)指針指向
其前一個(gè)元素和后一個(gè)元素。- list與forward_list非常相似:最主要的不同在于forward_list是單鏈表,只能朝前迭代,已讓其更簡(jiǎn)單高
效。- 與其他的序列式容器相比(array,vector,deque),list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率
更好。- 與其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問(wèn),比如:要訪問(wèn)list
的第6個(gè)元素,必須從已知的位置(比如頭部或者尾部)迭代到該位置,在這段位置上迭代需要線性的時(shí)間開(kāi)銷(xiāo);list還需要一些額外的空間,以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這可能是一個(gè)重要的因素)
二,list的基本使用
2.1 list的構(gòu)造
void TestList1()
{list<int> l1; // 構(gòu)造空的l1list<int> l2(4, 100); // l2中放4個(gè)值為100的元素list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左閉右開(kāi)的區(qū)間構(gòu)造l3list<int> l4(l3); // 用l3拷貝構(gòu)造l4// 以數(shù)組為迭代器區(qū)間構(gòu)造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;} cout << endl;// C++11范圍for的方式遍歷for (auto& e : l5)cout << e << " ";cout << endl;
}
2.2 list迭代器的使用
string和vector的是隨機(jī)迭代器,list的迭代器是雙向迭代器,不是隨機(jī)迭代器,所以只支持 ++ 和 - -,由于效率原因不支持 + 和 -。
// 注意:遍歷鏈表只能用迭代器和范圍for
void PrintList(const list<int>& l)
{// 注意這里調(diào)用的是list的 begin() const,返回list的const_iterator對(duì)象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 編譯不通過(guò)}cout << endl;
}void TestList2()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin(); // C++98中語(yǔ)法auto it = l.begin(); // C++11之后推薦寫(xiě)法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;
}
【注意】
1.begin與end為正向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向后移動(dòng)
2.rbegin(end)與rend(begin)為反向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向前移動(dòng)
2.3 list的頭插,頭刪,尾插和尾刪
// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4,頭部插入0L.push_back(4);L.push_front(0);PrintList(L);// 刪除list尾部節(jié)點(diǎn)和頭部節(jié)點(diǎn)L.pop_back();L.pop_front();PrintList(L);
}
2.4 list的插入和刪除
/ insert /erase
void TestList4()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 獲取鏈表中第二個(gè)節(jié)點(diǎn)auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值為4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5個(gè)值為5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)區(qū)間中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 刪除pos位置上的元素L.erase(pos);PrintList(L);// 刪除list中[begin, end)區(qū)間中的元素,即刪除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}
2.5 list 的 resize/swap/clear
// resize/swap/clear
void TestList5()
{// 用數(shù)組來(lái)構(gòu)造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交換l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 將l2中的元素清空l2.clear();cout << l2.size() << endl;
}