# list
用於處理頻繁刪除、插入導致 TLE 的題目
簡單的想就是更快速的 vector
# 標頭檔
#include<list> |
# 構造器 && 初始化
- 默認構造器：empty container constructor
- 批量構造器：fill constructor
- 複製構造器：copy constructor
#include<list> | |
#include<iostream> | |
using namespace std; | |
void print(list<int> temp) | |
{ | |
cout<<endl; | |
for(auto x: temp) | |
cout<<x<<" "; | |
cout<<endl; | |
} | |
int main(){ | |
list<int> list1; // 默認構造器 | |
list<int> list2{1,2}; // 默認構造器 | |
list<int> list3(6,10); // 批量構造器 | |
list<int> list4(list2); // 複製構造器 | |
print(list2); | |
print(list3); | |
print(list4); | |
} |
輸出
1 2
10 10 10 10 10 10 //六個10
10 10 10 10 10
1 2
# push_back && pop_back
list 最常用的成員函數，在尾部插入和刪除
# push_front && pop_front
list 常用的成員函數，在首部插入和刪除
# assign
int main(){
list<int> test;
test.assign(2,3); //批量構造，構造兩個值為 3 的 element
print(test);
test.assign(2,8); //會覆蓋原有值
print(test);
}
輸出
3 3
8 8
# insert
在指定位置插入一個或多個值
| 重載函數 | 形参 |
|---|---|
| 插入單個值 [1] | iterator insert (const_iterator position, const value_type& val); |
| 多個重複值 [2] | iterator insert (const_iterator position, size_type n, const value_type& val) |
| range (3) | iterator insert (const_iterator position, InputIterator first, InputIterator last) |
int main(){ | |
list<int> test(2,8); | |
list<int> test1(test); | |
test.insert(test.begin(),3); //[1] | |
print(test); | |
auto ite =test.insert(test.begin(),test1.begin(),test1.end());//[3] | |
print(test); | |
cout<<*ite<<endl; //insert 返回指針地址 | |
} |
輸出
3 8 8
8 8 3 8 8
8
# erase
刪除指定位置的值
| 重載函數 | 形參 |
|---|---|
| single | iterator erase (const_iterator position) |
| range | iterator erase (const_iterator first, const_iterator last) |
int main(){ | |
list<int> test; | |
test.assign(4,3); // 批量構造，構造兩個值為 3 的 element | |
test.push_back(66); | |
cout<<"initial element\n"; | |
print(test); | |
test.erase(test.end()-1); // 刪除尾部元素，注意不要越界 | |
print(test); | |
test.erase(test.begin(),test.end()-2);// 刪除操作依舊複雜度高，容易 TLE | |
print(test); | |
} |
輸出
initial element
3 3 3 3 66
3 3 3 3
3 3
# empty
如果 list 為空， empty 返回 true ;
# size
返回 list 容器元素個數
# emplace && emplace_back && emplace_front
C++11 的新特性，在幾乎所有的容器中都插入了這一函數，這一函數功能類似於 insert , 但是開銷遠小於 insert , 它不產生臨時變數
int main(){ | |
list<pair<int,double>> lis;//vector 中嵌套 pair | |
//back | |
lis.push_back(make_pair(1,1.0));// 常用的構造方式 | |
lis.emplace(lis.end(),1,2.0);//emplace 的構造方式 | |
//front | |
lis.push_front(make_pair(1,1.0));// 常用的構造方式 | |
lis.emplace(lis.begin(),1,2.0);//emplace 的構造方式 | |
} |
方便是方便，但簡單的尾部插入還要寫地址，豈不繁瑣，當然不是，C++11 也提供了 emplace_back 這一函數
lis.emplace_back(1,2.0);//emplace_back 的構造方式，不需寫尾部位址 | |
lis.emplace_front(1,2.0);//emplace_back 的構造方式，不需寫首部位址 |
# resize
更改 list 中 element 個數
int main(){ | |
list <int> lis; | |
// set some initial content: | |
for (int i=1;i<10;i++) lis.push_back(i); | |
lis.resize(5);// 縮小容量到 5, 尾部多餘的 `element` 被刪除 | |
print(lis); | |
lis.resize(8,100);// 擴容到 8, 用 100 填值 | |
print(lis); | |
lis.resize(12);// 使用 0 填值 | |
print(lis); | |
} |
輸出
1 2 3 4 5
1 2 3 4 5 100 100 100
1 2 3 4 5 100 100 100 0 0 0 0
# clear
刪除 list 中的所有元素，如果有析構函式呼叫各自的析構函數，但是 clear 不刪除 list 的容量，list 的容量是自身佔用的記憶體值，不是其中包含的 element 的具體大小，為了效率考慮， list 分配的記憶體值都是大於或等於已使用的記憶體值
例子
int main(){ | |
list<pair<int,double>> lis;//list 中嵌套 pair | |
lis.push_back(make_pair(1,1.0));// 常用的構造方式 | |
lis.emplace_back(1,2.0);//emplace_back 的構造方式 | |
cout<<lis.capacity()<<" "<<lis.size()<<endl; | |
lis.clear(); | |
cout<<lis.capacity()<<" "<<lis.size()<<endl; | |
} |
輸出
2 2
2 0//容量是不變的
# remove
刪除 list 裡所有指定的值
int main(){ | |
list<int> lis{10,10,20,20,30,30}; // 默認構造器 | |
lis.remove(20); | |
print(lis); | |
} |
輸出
10 10 30 30
# remove_if
刪除 list 中符合條件的值
bool is_odd(int n){ | |
return n%2==1; | |
} | |
int main(){ | |
list<int> lis{1,2,3,4,5,6}; // 默認構造器 | |
lis.remove_if(is_odd); | |
print(lis); | |
} |
輸出
2 4 6
