C++中l(wèi)ist容器的實現(xiàn)
一、list容器
1.1 簡介
① 功能：將數(shù)據(jù)進行鏈式存儲。
② 鏈表(list)是一種物理存儲單元上非連續(xù)的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實現(xiàn)的。
③ 鏈表的組成：鏈表由一系列結(jié)點組成。
④ 結(jié)點的組成：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。
⑤ 添加元素，將原指向下一個元素的指針指向新元素即可，新元素指向下一個元素
⑥ STL中的鏈表是一個雙向循環(huán)鏈表。
- 雙向：每一個指針既指向下一個結(jié)點的元素，也指向上一個結(jié)點的元素。
- 循環(huán)：最后一個結(jié)點的指針會指向第一個結(jié)點的元素，第一個結(jié)點的指針會指向最后一個結(jié)點的元素。
⑦ 由于鏈表的存儲方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器。
- 它只能通過指針域一個一個前移/后移去找，而不能連續(xù)的內(nèi)存空間，指針加一個數(shù)字，就可以找到數(shù)據(jù)。
⑧ list的優(yōu)點：
- 采用動態(tài)存儲分配，不會造成內(nèi)存浪費和溢出。
- 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動大量數(shù)據(jù)。
⑨ list的缺點：
- 鏈表靈活，但是空間(指針域)和時間(遍歷)額外耗費較大。
10.list有一個重要的性質(zhì)，插入操作和刪除操作都不會造成原有l(wèi)ist迭代器的失效，這在vector中是不成立的，vector當插入操作會創(chuàng)建一個更大的數(shù)據(jù)內(nèi)容，而vector容器的迭代器卻指向原有內(nèi)存，所以原有的vector容器失效了。
11.STL中l(wèi)ist和vector是兩個最長被用的容器，各有優(yōu)缺點。
1.2 構(gòu)造函數(shù)
① 功能描述：創(chuàng)建list容器。
② 函數(shù)原型：
list lst; //list采用模板類實現(xiàn)對象的默認構(gòu)造形式 list(beg,end); //構(gòu)造函數(shù)將[beg,end)區(qū)間中的元素拷貝給本身。 list(n,elem); //構(gòu)造函數(shù)將n個elem拷貝給本身。 list(const list &lst); //拷貝構(gòu)造函數(shù)。
③ list構(gòu)造方式同其他幾個STL容器一樣。
#include<iostream>
using namespace std;
#include <list>
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
//遍歷容器
printList(L1);
//區(qū)間方式構(gòu)造
list<int>L2(L1.begin(), L1.end());
printList(L2);
//拷貝構(gòu)造
list<int>L3(L2);
printList(L3);
//n個elem
list<int>L4(10, 1000);
printList(L4);
}
int main() {
test01();
system("pause");
return 0;
}運行結(jié)果：
10 20 30 40
10 20 30 40
10 20 30 40
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
請按任意鍵繼續(xù). . .
1.3 賦值和交換
① 功能描述：給list容器進行賦值，以及交換list容器。
② 函數(shù)原型：
assign(beg,end); //將[beg,end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。 assign(n,elem); //將n個elem拷貝賦值給本身。 list& operator=(const list &list); //重載等號操作符。 swap(list); //將lst與本身的元素互換。
#include<iostream>
using namespace std;
#include <list>
//list容器賦值和交換
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
//遍歷容器
printList(L1);
list<int>L2;
L2 = L1; //operator= 賦值
printList(L2);
list<int>L3;
L3.assign(L2.begin(), L2.end());
printList(L3);
list<int>L4;
L4.assign(10, 100);
printList(L4);
}
//交換
void test02()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
list<int>L2;
L2.assign(10, 100);
cout << "交換前：" << endl;
printList(L1);
printList(L2);
L1.swap(L2);
cout << "交換后：" << endl;
printList(L1);
printList(L2);
}
int main() {
test01();
test02();
system("pause");
return 0;
}
運行結(jié)果：
10 20 30 40
10 20 30 40
10 20 30 40
100 100 100 100 100 100 100 100 100 100
交換前：
10 20 30 40
100 100 100 100 100 100 100 100 100 100
交換后：
100 100 100 100 100 100 100 100 100 100
10 20 30 40
請按任意鍵繼續(xù). . .
1.4 大小操作
① 功能描述：對list容器的大小進行操作。
② 函數(shù)原型：
//返回容器中元素的個數(shù)。 size(); //判斷容器是否為空。 empty(); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置。 //如果容器變短，則末尾超出容器長度的元素被刪除。 resize(num); //重新指定容器的長度為num，若容器變成，則以elem值填充新位置。 //如果容器變短，則末尾超出容器長度的元素被刪除。 resize(num,elem);
#include<iostream>
using namespace std;
#include <list>
//list容器賦值和交換
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
//遍歷容器
printList(L1);
//判斷容器是否為空
if(L1.empty())
{
cout << "L1為空" << endl;
}
else
{
cout << "L1不為空：" << endl;
cout << "L1的元素個數(shù)為：" << L1.size() << endl;
}
//重新指定大小
L1.resize(10,10000);
printList(L1);
L1.resize(2);
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}運行結(jié)果：
10 20 30 40
L1不為空：
L1的元素個數(shù)為：4
10 20 30 40 10000 10000 10000 10000 10000 10000
10 20
請按任意鍵繼續(xù). . .
1.5 插入和刪除
① 功能描述：對list容器進行數(shù)據(jù)的插入和刪除。
② 函數(shù)原型：
push_back(elem); //在容器尾部加入一個元素。 pop_back(); //刪除容器中最后一個元素。 push_front(elem); //在容器開頭插入一個元素。 pop_front(); //從哪個容器開頭移除第一個元素 insert(pos,elem); //在pos位置插elem元素的拷貝，返回新數(shù)據(jù)的位置。 insert(pos,n,elem); //在pos位置插入n個elem數(shù)據(jù)，無返回值。 insert(pos,beg,end); //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。 clear(); //移除容器的所有數(shù)據(jù)。 erase(beg,end); //刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。 erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。 remove(elem); //刪除容器中所有與elem值匹配的元素。
#include<iostream>
using namespace std;
#include <list>
//list容器賦值和交換
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_front(100);
L1.push_front(200);
L1.push_front(300);
//遍歷容器
printList(L1);
//尾刪
L1.pop_back();
printList(L1);
//頭刪
L1.pop_front();
printList(L1);
//insert插入
list<int>::iterator it = L1.begin();
L1.insert(++it, 1000);
printList(L1);
//刪除
it = L1.begin();
L1.erase(it);
printList(L1);
//移除
L1.push_back(10000);
L1.push_back(10000);
L1.push_back(10000);
L1.push_back(10000);
printList(L1);
L1.remove(10000);
printList(L1);
//清空
L1.clear();
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}運行結(jié)果：
300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 1000 100 10 20
1000 100 10 20
1000 100 10 20 10000 10000 10000 10000
1000 100 10 20
請按任意鍵繼續(xù). . .
1.6 數(shù)據(jù)存取
① 功能描述：對list容器中數(shù)據(jù)進行存取。
② 函數(shù)原型：
front(); //返回第一個元素。 back(); //返回最后一個元素。
③ list容器不是連續(xù)的內(nèi)存空間，所以不能通過[]、at等方式隨機訪問。
#include<iostream>
using namespace std;
#include <list>
//list容器 數(shù)據(jù)存取
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
void test01()
{
//創(chuàng)建list容器
list<int>L1; //默認構(gòu)造
//添加數(shù)據(jù)
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
//L1[0] 不可以用[]訪問list容器中的元素
//L1.at(0) 不可以用at方式訪問list容器中的元素
//原因是list本質(zhì)鏈表，不是用連續(xù)線性空間存儲數(shù)據(jù)，迭代器也是不支持隨機訪問的。
cout << "第一個元素為：" << L1.front() << endl;
cout << "第一個元素為：" << L1.back() << endl;
//驗證迭代器是不支持隨機訪問的
list<int>::iterator it = L1.begin();
it++; //因為list是雙向的，所以支持遞增、遞減++、--的操作，但是不支持it = it+1;it = it+2;....，即不支持這樣的隨機訪問
}
int main() {
test01();
system("pause");
return 0;
}運行結(jié)果：
第一個元素為：10
第一個元素為：40
請按任意鍵繼續(xù). . .
1.7 反轉(zhuǎn)和排序
① 功能描述：將容器中的元素反轉(zhuǎn)，以及將容器中的數(shù)據(jù)進行排序。
② 函數(shù)原型：
reverse(); //反轉(zhuǎn)鏈表 sort(); //鏈表排序
#include<iostream>
using namespace std;
#include <list>
#include<algorithm>
//list容器 反轉(zhuǎn)和排序
void printList(const list<int>&L)
{
for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
bool myCopare(int v1, int v2)
{
//降序 就讓第一個數(shù) 大于第二個數(shù)為真
return v1 > v2;
}
void test01()
{
//反轉(zhuǎn)
list<int>L1;
//添加數(shù)據(jù)
L1.push_back(20);
L1.push_back(10);
L1.push_back(50);
L1.push_back(40);
L1.push_back(30);
cout << "反轉(zhuǎn)前：" << endl;
printList(L1);
//反轉(zhuǎn)
L1.reverse();
cout << "反轉(zhuǎn)后：" << endl;
printList(L1);
//排序
cout << "排序前：" << endl;
printList(L1);
//所有不支持隨機訪問迭代器的容器，不可以用標準算法
//不支持隨機訪問迭代器的容器，內(nèi)部會提供對應的一些算法
//sort(L1.begin(),L1.end()); //報錯，這是標準算法，全局函數(shù)的sort()
L1.sort(); //默認排序規(guī)則 從小到大 升序
cout << "排序后：" << endl;
printList(L1);
L1.sort(myCopare); //降序排列 這是成員函數(shù)的sort()
cout << "重載排序算法，降序排序后：" << endl;
printList(L1);
}
int main()
{
test01();
system("pause");
return 0;
}運行結(jié)果：
反轉(zhuǎn)前：
20 10 50 40 30
反轉(zhuǎn)后：
30 40 50 10 20
排序前：
30 40 50 10 20
排序后：
10 20 30 40 50
重載排序算法，降序排序后：
50 40 30 20 10
請按任意鍵繼續(xù). . .
到此這篇關(guān)于C++中l(wèi)ist容器的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ list容器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
VS中動態(tài)庫的創(chuàng)建和調(diào)用方式詳解
庫的存在形式本質(zhì)上來說庫是一種可執(zhí)行代碼的二進制,? 靜態(tài)庫和動態(tài)庫的區(qū)別主要是在鏈接階段處理庫的方式不同而區(qū)分的,本文介紹VS中動態(tài)庫的創(chuàng)建和調(diào)用方式,感興趣的朋友一起看看吧2024-01-01
C++實現(xiàn)二分法的一些細節(jié)(常用場景)
二分法算法思想首先確定有根區(qū)間，將區(qū)間二等分，通過判斷f（x）的符號，逐步將有根區(qū)間縮小，直至有根區(qū)間足夠小，便可求出滿足精度要求的近似值2021-07-07
這篇文章主要為大家詳細介紹了C語言基于EasyX實現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要是想喝大家一起聊聊來C++中的四種類型轉(zhuǎn)換符?：const_cast、reinterpret_cast、dynamic_cast和static_cast，感興趣的可以了解一下2022-07-07
這篇文章主要介紹了C++讀寫配置項的基本操作，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2021-01-01
這篇文章主要為大家介紹了C語言題解字符串變形的方法示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-08-08
C/C++中關(guān)于字符串的常見函數(shù)操作大全
這篇文章主要介紹了C/C++中關(guān)于字符串的常見函數(shù)操作，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-03-03
本文主要介紹了QT .pro文件的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
這篇文章主要介紹了在iOS中給視頻添加濾鏡的方法示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
下面小編就為大家?guī)硪黄狢和指針小結(jié)(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考，一起跟隨小編過來看看吧2016-06-06