目錄
1.什么是list
1.1list 的優勢和劣勢
優勢:
劣勢:
2.構造函數?
2.1??default (1)
2.2? fill (2)
2.3? range (3)
2.4? copy (4)
3.list iterator的使用
3.1. begin()
3.2. end()
3.3迭代器遍歷
4. list容量函數
4.1. empty()
4.2. size()
4.3. max_size()
4.4. front()
4.5. back()
5.list增刪查改函數?
5.1?push_front
5.2?pop_front?
5.3? push_back
5.4 pop_back
?5.5 insert
5.6. erase
5.7? swap?
5.8 clear?
?6.list操作函數
6.1. splice
6.2. remove
6.3. unique
6.4. reverse
?7.list的迭代器失效
?追隨光靠近光成為光
1.什么是list
在C++標準庫中,list
?是一個雙向鏈表容器,用于存儲一系列元素。與?vector
?和?deque
?等容器不同,list
?使用鏈表的數據結構來組織元素,因此在某些操作上具有獨特的優勢和性能特點。以下是關于 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 時,需要權衡其優勢和劣勢,根據實際場景來選擇合適的容器。當需要頻繁插入和刪除元素,且不需要隨機訪問時,list 可能是一個很好的選擇。但需要注意的是,由于鏈表的特性,list 并不適用于需要快速隨機訪問元素的場景,因為訪問某個位置的元素需要遍歷鏈表
1.1list 的優勢和劣勢
優勢:
插入和刪除效率高: 由于 std::list 是雙向鏈表,插入和刪除操作在常數時間內完成,不需要涉及內存的重新分配和元素的復制。這使得 std::list 在大量插入和刪除操作時非常高效。
迭代器的穩定性: std::list 的插入和刪除操作不會使迭代器失效,除非刪除的正是迭代器所指向的元素。這使得在遍歷過程中進行插入和刪除操作更加方便和安全。
空間占用相對穩定: std::list 的空間占用相對穩定,插入和刪除操作不會影響其他元素的空間占用。
劣勢:
不支持隨機訪問: 由于鏈表的結構,list 不支持像數組一樣的隨機訪問。訪問某個位置的元素需要從鏈表的開頭或結尾開始遍歷。
額外的指針開銷:list 中的每個元素都需要存儲指向前后元素的指針,這使得空間占用相對其他容器更高。
緩存效率低: 由于鏈表中元素在內存中的存儲位置不連續,導致在訪問鏈表元素時,緩存命中率較低,可能影響性能。
迭代器的使用限制:list 的迭代器不支持與普通指針類似的算術操作(如 + 和 -),因此無法像 vector 那樣靈活地進行迭代器操作
2.構造函數?
2.1??default (1)
這個構造函數用于創建一個空的?std::list
?容器。它可以接受一個可選的分配器參數,用于指定內存分配策略。
list<int> v; // 創建一個空的 list 容器
2.2? fill (2)
這個構造函數用于創建一個包含 n 個元素的list
?容器,并將這些元素初始化為?val
。你可以通過傳遞不同的?val
?值來創建一個包含相同值的容器。同樣,也可以傳遞一個可選的分配器參數。
list<int> v(10, 20); // 創建一個包含 10個元素,每個元素都是 20 的list 容器
2.3? range (3)
這個構造函數使用迭代器范圍?[first, last)?
中的元素創建一個list
?容器。這使你可以通過一個迭代器范圍來初始化容器。同樣,它也接受一個可選的分配器參數。
vector<int> v = {1, 2, 3, 4, 5};
list<int> my(v.begin(), v.end()); // 從迭代器范圍內的元素創建list 容器
2.4? copy (4)
這個構造函數用于創建一個與已存在的?list
?容器?x
?相同的副本。它會將?x
中的所有元素拷貝到新的容器中。這是一個拷貝構造函數。
list<int> v = {1, 2, 3, 4, 5};
list<int> my(v); // 創建一個原容器的副本
3.list iterator的使用
3.1. begin()
iterator begin() noexcept;
這個版本的?begin()
?返回一個迭代器,可以用于修改容器內的元素。noexcept
?表示這個函數不會拋出異常。
list<int> m = {1, 2, 3, 4, 5};
list<int>::iterator it = m.begin(); // 獲取可修改元素的迭代器
*it = 10; // 修改第一個元素的值為 10
3.2. end()
iterator end() noexcept;
這個版本的?end()
?返回一個迭代器,可以用于修改容器內的元素。noexcept
?表示這個函數不會拋出異常。這個迭代器指向的位置實際上是容器的末尾位置之后一個虛擬的位置,所以它并不指向容器內的任何元素。
list<int> m = {1, 2, 3, 4, 5};
list<int>::iterator it = m.end(); // 獲取可修改元素的迭代器
--it; // 將迭代器前移一個位置,指向最后一個元素
*it = 20; // 修改最后一個元素的值為 20
3.3迭代器遍歷
(list不支持[? ],? 只能用迭代器遍歷(范圍for也可以底層是迭代器))
#include<iostream>
#include<list>
using namespace std;void mylist()
{list<int> m;m.push_back(1);m.push_back(2);m.push_back(3);//迭代器list<int>::iterator it = m.begin();while (it != m.end()){cout << *it << " ";it++;}cout << endl;//范圍forfor (auto e : m){cout << e << " ";}cout << endl;}int main()
{mylist();return 0;
}
4. list容量函數
4.1. empty()
empty() 是 list 容器的一個成員函數,用于判斷容器是否為空。它返回一個布爾值,表示容器是否不包含任何元素。函數聲明如下:
bool empty() const noexcept;
返回值:如果容器為空,則返回 true,否則返回 false。
例子?
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m;if (m.empty()) {cout << "The list is empty." << endl;}else {cout << "The list is not empty." << endl;}m.push_back(10);if (m.empty()) {cout << "The list is empty." << endl;}else {cout << "The list is not empty." << endl;}return 0;
}
4.2. size()
size()
?是?list
?容器的一個成員函數,用于返回容器中元素的數量。它返回一個無符號整數類型,表示容器中的元素數量。函數聲明如下:
size_type size() const noexcept;
返回值:返回容器中元素的數量,即大小。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m;m.push_back(1);m.push_back(2);m.push_back(3);m.push_back(4);m.push_back(5);cout << "Size of the list: " << m.size() << endl;return 0;
}
4.3. max_size()
max_size() 是 list 容器的一個成員函數,用于返回容器可能容納的最大元素數量,通常受到系統內存限制的影響。它返回一個無符號整數類型,表示容器的最大大小。函數簽名如下:
size_type max_size() const noexcept;
返回值:返回容器可能容納的最大元素數量。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m;cout << "Size of the list: " << m.max_size() << endl;return 0;
}
?
4.4. front()
front()
?是?list
?容器的成員函數,用于返回容器中第一個元素的引用。這個函數有兩個版本,一個用于可修改容器的對象,另一個用于只讀(const)容器的對象。函數的簽名如下:
reference front();
reference:返回一個對容器中第一個元素的非常引用。
加了const是只讀的不能被修改
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {9,2,3,4,5,6};int& firstElement = m.front();cout << "First element: " << m.front() << endl;return 0;
}
?
4.5. back()
back() 是 list 容器的成員函數,用于返回容器中最后一個元素的引用。這個函數有兩個版本,一個用于可修改容器的對象,另一個用于只讀(const)容器的對象。函數的簽名如下:
reference back();
reference:返回一個對容器中最后一個元素的非常引用。加了const是只讀的不能被修改
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {9,2,3,4,5,6};int& firstElement = m.back();cout << "Last element: " << m.back() << endl;return 0;
}
?
5.list增刪查改函數?
函數說明 | 接口說明 |
push_front | 在list首元素前插入值為val的元素 |
pop_front | 刪除list中第一個元素 |
push_back | 在list尾部插入值為val的元素 |
pop_back | 刪除list中最后一個元素 |
insert | 在list position 位置中插入值為val的元素 |
erase | 刪除list position位置的元素 |
swap | 交換兩個list中的元素 |
clear | 清空list中的有效元素 |
5.1?push_front
push_front 是 list 容器的成員函數,用于在容器的開頭插入一個新元素。
這個函數有兩個版本:
void push_front (const value_type& val);:接受一個常量引用參數,會創建一個新元素并將參數的值拷貝到新元素中。
void push_front (value_type&& val);:接受一個右值引用參數,用于移動構造一個新元素。這樣可以避免額外的拷貝操作,提高了效率。
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m;int value = 10;m.push_front(value); // Copy insertcout << "List contents:" << endl;for (const auto& num : m) {cout << num << " ";}cout << endl;m.push_front(20); // Move insert,右值引用,更簡單高效cout << "List contents after move insert:" << endl;for (const auto& num : m) {cout << num << " ";}cout << endl;return 0;
}
?
5.2?pop_front?
void pop_front();
?是用于從 ist 的開頭移除一個元素的成員函數。它會刪除列表中的第一個元素,并且將列表的大小減小一個單位。
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {10,20,30,40,50};m.pop_front();for (auto e : m){cout << e << " ";}cout << endl;return 0;
}
5.3? push_back
void push_back (const value_type& val);
?是?list
?容器的成員函數,用于在列表的末尾插入一個新元素。它接受一個常量引用作為參數,將傳入的值插入到列表末尾
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m;m.push_back(2);m.push_back(4);m.push_back(6);m.push_back(8);m.push_back(10);for (auto e : m){cout << e << " ";}cout << endl;return 0;
}
5.4 pop_back
void pop_back();
?是?list?
容器的成員函數,用于刪除列表中的最后一個元素。它會將列表的最后一個元素從容器中移除,同時釋放相應的內存資源。
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m;m.push_back(2);m.push_back(4);m.push_back(6);m.push_back(8);m.push_back(10);m.pop_back();m.pop_back();list<int>::iterator it = m.begin();while (it != m.end()){cout<<*it<<" ";it++;}cout << endl;return 0;
}
?
?5.5 insert
在list position 位置中插入值為val的元素
iterator insert (iterator position, const value_type& val); 是 list 容器的成員函數,用于在指定位置插入一個新元素,新元素的值由 val 參數確定。
參數說明:
position:要插入新元素的位置的迭代器。
val:要插入的元素的值。
該函數返回一個迭代器,指向插入的元素。
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {1,2,3,4,5};auto a = m.begin();a++; //begin的下一個位置,第二個位置m.insert(a,10);list<int>::iterator it = m.begin();while (it != m.end()){cout<<*it<<" ";it++;}cout << endl;return 0;
}
?
5.6. erase
刪除list position位置的元素
iterator erase (iterator position); 和 iterator erase (iterator first, iterator last); 是 std::list 容器的成員函數,用于從列表中刪除一個或多個元素。
iterator erase (iterator position); 刪除指定位置的元素,并返回指向下一個元素的迭代器。
參數說明:
position
:要刪除的元素的位置的迭代器。
返回值:指向被刪除元素之后的元素的迭代器。
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {1,2,3,4,5};auto a = m.begin();a++; //begin的下一個位置,第二個位置m.erase(a);
}
5.7? swap?
交換兩個list中的元素
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> m = {1,2,3,4,5};list<int> n = { 6,7,8,9,0};m.swap(n);list<int>::iterator it = m.begin();cout << "m:";;while (it != m.end()){cout << *it << " ";it++;}cout << endl;list<int>::iterator is = n.begin();cout << "n:";while (is != n.end()){cout << *is << " ";is++;}cout << endl;return 0;
}
5.8 clear?
清空list中的有效元素
#include<iostream>
#include<list>
using namespace std;#include <iostream>
#include <list>int main() {list<int> m = { 1, 2, 3, 4, 5 };cout << "m before clear: ";for (int num : m) {cout << num << " ";}cout << endl;m.clear(); // 清空列表cout << "m after clear: ";for (int num : m) {cout << num << " ";}cout << endl;return 0;
}
?6.list操作函數
6.1. splice
void splice (iterator position, list& x);
該成員函數用于將另一個列表?x
?中的所有元素移動到當前列表中,插入到指定位置?position
?前。x
?列表在移動后會變為空列表。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m1 = { 1, 2, 3 };list<int> m2 = { 4, 5, 6 };auto it = m1.begin();advance(it,1); m1.splice(it, m2); // 將 m2 的元素插入到 m1 中cout << "m1 after splice: ";for (int num : m1) {cout << num << " ";}cout << endl;cout << "m2 after splice: ";for (int num : m2) {cout << num << " ";}cout << endl;return 0;
}
6.2. remove
void remove (const value_type& val);
該成員函數用于從列表中移除所有等于給定值?val
?的元素。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m = { 1, 2, 3, 2, 4, 2, 5 };m.remove(2); // 移除列表中所有值為 2 的元素cout << "m after remove: ";for (int num : m) {cout << num << " ";}cout << endl;return 0;
}
?
6.3. unique
void unique();
這個成員函數用于移除列表中相鄰的重復元素。它只保留第一個出現的重復元素,移除后續的重復元素。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m = { 1, 2, 2, 2, 3, 4,4, 5 };m.unique( ); // 移除列表中所有值為 2 的元素cout << "m after remove: ";for (int num : m) {cout << num << " ";}cout << endl;return 0;
}
?
6.4. reverse
void reverse();
?函數用于將列表中的元素逆序排列。
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m = { 1, 2,3,4, 5 };m.reverse( ); // 移除列表中所有值為 2 的元素cout << "m after remove: ";for (int num : m) {cout << num << " ";}cout << endl;return 0;
}
?7.list的迭代器失效
迭代器失效即迭代器所指向的節點的無效,即該節點被刪除了。因為list的底層結構為帶頭結點的雙向循環鏈表,因此在list中進行插入時是不會導致list的迭代器失效的,只有在刪除時才會失效,并且失效的只是指向被刪除節點的迭代器,其他迭代器不會受到影響。
當使用?std::list
?進行刪除操作時,可能會導致迭代器失效。下面是一個示例:
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m = { 1, 2, 3, 4, 5 };auto it = m.begin();++it; // Move the iterator to the second elementm.erase(it); // Erase the second elementfor (auto n : m) {cout << n << " ";}return 0;
}
在上面的示例中,當我們在第二個元素位置處使用?erase
?函數刪除元素后,迭代器?it
?就會失效,因為它指向的元素已經被刪除。如果我們嘗試使用失效的迭代器,可能會導致未定義的行為
要修正這個問題,可以使用?erase
?函數的返回值,它會返回一個指向下一個有效元素的迭代器:
#include<iostream>
#include<list>
using namespace std;int main() {list<int> m = { 1, 2, 3, 4, 5 };auto it = m.begin();++it; // Move the iterator to the second elementit=m.erase(it); // Erase the second elementfor (auto n : m) {cout << n << " ";}return 0;
}
本文章借鑒了「愛學習的魚佬」的原創文章,原文在下面鏈接
原文鏈接:https://blog.csdn.net/kingxzq/article/details/132225841