list的常用接口

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名申請、雅安服務器托管、營銷軟件、網站建設、迎澤網站維護、網站推廣。文章目錄

• list的常用接口
• 一、list的介紹
• 二、list的使用
• • 1.list的構造
  • 2.迭代器的使用
  • • 2.1.begin和end
    • 2.2.rbegin和rend
    • 2.3.范圍for
    • 2.4.迭代器的分類
  • 3.list的元素訪問函數
  • • 3.1.front和back
  • 4.list的容量操作函數
  • • 4.1.empty
    • 4.2.size和max_size
  • 5.list修改的相關函數
  • • 5.1.push_front和pop_front
    • 5.2.push_back和pop_back
    • 5.3.insert和erase
    • 5.3.clear和resize
    • 5.4.swap
  • 6.list的其他操作函數
  • • 6.1.sort
    • 6.2.splice
    • 6.3.move和move_if
    • 6.4.unique和merge
    • 6.5.reverse
  • 7.list與vector對比

一、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的使用 1.list的構造

構造函數	接口說明
list()	構造空的list
list (size_type n, const value_type& val = value_type())	構造的list中包含n個值為val的元素
list (const list& x)	拷貝構造函數
list (InputIterator first, InputIterator last)	用[first, last)區間中的元素構造list

• list()

listlt1;

• list (size_type n, value_type& val = value_type())

listlt2(4， 1);//構造4個值為1的元素

• list (const list& x)

listlt3(lt2);//用lt2拷貝構造lt3

• list (InputIterator first, InputIterator last)

//1、用l2的[begin(), end()）左閉右開的區間構造lt4
listlt4(lt2.begin(), lt2.end());
//2、以數組為迭代器區間構造lt5
int array[] = {1,2,3,4 };
listlt5(array, array + sizeof(array) / sizeof(int));

---

2.迭代器的使用

函數聲明	接口說明
begin	返回第一個元素的迭代器
end	返回最后一個元素下一個位置的迭代器
rbegin	返回第一個元素的reverse_iterator,即end位置
rend	返回最后一個元素下一個位置的reverse_iterator,即begin位置

2.1.begin和end

begin是返回第一個元素的迭代器，end是返回最后一個元素下一個位置的迭代器。可以通過迭代器進行元素訪問：

void list_test1()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list::iterator it = lt.begin();
	while (it != lt.end()) //不能用it< lt.end()
	{cout<< *it<< " ";
		it++;
	}
	cout<< endl;
}

• 注意：begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動。

2.2.rbegin和rend

和先前學到的string類似，rbegin的第一個元素為尾部end位置，rend返回的是begin的位置。

void list_test1()
{listlt(4, 1);
	list::reverse_iterator rit = lt.rbegin();
    //或者用auto自動識別類型：auto rit = lt.rbegin();
	while (rit != lt.rend()) 
	{cout<< *it<< " "; // 1 1 1 1
		it++;
    }
}

• 注意：rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動。

2.3.范圍for

范圍for的底層就是迭代器實現的，利用其也可進行元素訪問：

void list_test1()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for(auto e : lt)
   	{cout<< e<< " ";
	}
	cout<< endl;
}

2.4.迭代器的分類

1. 單向迭代器：只能++，不能–。比如單鏈表、哈希表等。
2. 雙向迭代器：既能++也能–。比如雙向鏈表。
3. 隨機訪問迭代器：既能++、–；又能+、-。比如vector、string。
4. 迭代器是內嵌類型（內部類或定義在類里）

---

3.list的元素訪問函數

函數聲明	接口聲明
front	返回list第一個節點中值的引用
back	返回list最后一個節點中值的引用

3.1.front和back

front返回第一個元素，back返回最后一個元素

void list_test2()
{listlt;
	for (int i = 1; i<= 4; i++)
	{lt.push_back(i);//1 2 3 4
	}
	cout<< lt.front()<< endl;//1
	cout<< lt.back()<< endl; //4
}

---

4.list的容量操作函數

函數聲明	接口說明
empty	檢測list是否為空，是返回true，不是返回false
size	返回list中有效節點的個數
max_size	返回list中的大數據

4.1.empty

empty判斷list是否為空

void list_test2()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	
    if(lt.empty())
        cout<< "list empty"<< endl;
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    if(lt.empty())
       	cout<< "list empty"<< endl;
}

4.2.size和max_size

size用來獲取list的元素個數，max_size用來獲取list的大元素個數。

void list_test2()
{list lt(5, 1);   
	cout<< lt.size()<< endl;// 5
    cout<< lt.max_size()<< endl; // 返回鏈表長度大值
}

---

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中的有效數據
resize	為list開辟空間同時進行初始化

5.1.push_front和pop_front

push_front即頭插，pop_front即頭刪。

void list_test3()
{listlt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);

	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	lt.pop_front();
	lt.pop_front();
    
    for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;
}

5.2.push_back和pop_back

push_back即尾插，pop_back即尾刪。

void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	lt.pop_back();
	lt.pop_back();
	lt.pop_back();
	lt.pop_back();
    
    if(lt.empty())
        cout<< "list empty"<< endl;
}

5.3.insert和erase

list中的insert支持下列三種插入方式：

1. 在指定位置插入一個值為val的元素
2. 在指定位置插入n個值為val的元素
3. 在指定位置插入一段左閉右開的迭代器區間

void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	list::iterator pos = find(lt.begin(), lt.end(), 2);
	//1、在3的位置插入值20
	lt.insert(pos, 20);
	for (auto e : lt)
    {cout<< e<< " ";//1 20 2 3 4
	}
	cout<< endl;

	//2、在3的位置插入3個30
	pos = find(lt.begin(), lt.end(), 3);
	lt.insert(pos, 3, 30);
	for (auto e : lt)
    {cout<< e<< " ";//1 20 2 30 30 30 3 4
	}		
	cout<< endl;

	//3、在7的位置插入迭代器區間
	pos = find(lt.begin(), lt.end(), 20);
	listlt2(3, 0);
	lt.insert(pos, lt2.begin(), lt2.end());
	for (auto e : lt)
    {cout<< e<< " ";//1 0 0 0 20 2 30 30 30 3 4
	}
    cout<< endl;
}

erase支持下列兩種刪除方式：

1. 刪除在指定迭代器位置的元素

2. 刪除指定迭代器區間的元素

void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
	list::iterator pos = find(lt.begin(), lt.end(), 2);
    
	//1、刪除2位置的元素
	lt.erase(pos);
	for (auto e : lt)
    {cout<< e<< " ";//1 3 4 5 6     
	}	
	cout<< endl;
    
	//2、刪除4到list末尾的所有元素
	pos = find(lt.begin(), lt.end(), 4);
	lt.erase(pos, lt.end());
	for (auto e : lt)
    {cout<< e<< " ";//1 3    
	}
}

注意：這里的find使用的是算法庫里面的，list并未提供find算法。

5.3.clear和resize

clear用來清空list中的有效數據。

void list_test4()
{listlt(5, -1);
	for (auto e : lt)
    {cout<< e<< " ";//-1 -1 -1 -1 -1
	}
	cout<< endl;
	lt.clear();
	for (auto e : lt)
    {cout<< e<< " ";//空        
    }
}

resize擴容并初始化分為兩種：

如果 n 小于當前容器大小，則內容將減少到其前n個元素，刪除超出的元素（并銷毀它們）。

如果 n 大于當前容器大小，則通過在末尾插入所需數量的元素來擴展內容，以達到n的大小。如果指定了 val，則新元素將初始化為 val ，否則，它們將被值初始化為0 或者 匿名對象。

void list_test4()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
    resize(5);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5
    }
    cout<< endl;
    
    resize(8, 10);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5 10 10 10
    }
    cout<< endl;
    
    resize(10);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5 10 10 10 0 0
    }
    cout<< endl;
}

5.4.swap

swap用于交換兩個list的內容。

void list_test4()
{listlt1(5, 1);
	listlt2(3, 2);
	lt2.swap(lt1);
	for (auto e : lt1)
	 {cout<< e<< " "; //2 2 2   
	 }
	cout<< endl;

	for (auto d : lt2)
 	{cout<< d<< " "; //1 1 1 1 1     
 	}
}

6.list的其他操作函數

函數聲明	接口說明
sort	對list進行排序
unique	刪除list中的重復元素
splice	將元素從一個list剪切到另一個list
move	刪除具有特定值的元素
move_if	刪除滿足條件的元素
merge	合并排序list
reverse	反轉list元素的順序

6.1.sort

list中的sort函數默認排升序。

void list_test5()
{listlt;
	lt.push_back(2);
	lt.push_back(23);
	lt.push_back(6);
	lt.push_back(14);
	lt.push_back(10);
	lt.push_back(100);

	lt.remove(100);
	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;
	// list 雙向循環鏈表提供
	lt.sort();
	// algorithm 算法庫提供
	//sort(lt.begin(), lt.end()); 報錯
	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	//迭代器功能分類
	// 1.單向 ++
	// 2.雙向 --
	// 3.隨機 ++ -- + - ——>vector、string
}

注意：

list單獨提供排序是因為它不能用算法庫中的排序。算法庫中的排序是一個快排，需要滿足三數取中以及傳遞隨機訪問迭代器，list并不能滿足，所以不適用。而list自己提供的排序的底層是歸并排序，但是它本身提供的排序比較慢，如果數據量較小，那效率還可以，但是如果數據量很大，我們寧愿把list中的數據尾插到vector中使用算法庫中的快排，再拷貝回list中，也不會使用自身的歸并排序。

測試一：vector使用算法庫中的sortVSlist自身的sort

// N個數據需要排序，vector+ 算法sort  list+ sort
void test_op1()
{srand((unsigned int)time(0));
	const int N = 1000000;
	vectorv;
	v.reserve(N);
	listlt1;

	for (int i = 0; i< N; ++i)
	{auto e = rand();
		v.push_back(e);
		lt1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	//sort(lt2.begin(), lt2.end());
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

測試二：list先把數據拷貝到vector，再排序，排序完成后，再將數據拷貝回list所用時間VSlist使用自身的sort所用時間

void test_op2()
{srand((unsigned int)time(0));
	const int N = 10000000;
	vectorv;
	v.reserve(N);

	listlt1;
	listlt2;
	for (int i = 0; i< N; ++i)
	{auto e = rand();
		//v.push_back(e);
		lt1.push_back(e);
		//lt2.push_back(e);
	}

	// 拷貝到vector排序，排完以后再拷貝回來
	int begin1 = clock();
	for (auto e : lt1)
	{v.push_back(e);
	}
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto& e : lt1)
	{//e = v[i++];
		lt2.push_back(e);
	}
	int end1 = clock();

	int begin2 = clock();
	//sort(lt2.begin(), lt2.end());
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

6.2.splice

splice將元素從一個list剪切到另一個list，被剪切的list沒有元素了。

void list_test6()
{listlt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);

	listlt2;
	lt2.push_back(1);
	lt2.push_back(2);
	lt2.push_back(3);
	lt2.push_back(4);

	auto it = lt2.begin();
	++it; // 迭代器下標為2
	lt2.splice(it, lt1); // 把lt1的元素轉移到lt2迭代器下標為2的位置
	for (auto e : lt2)
	{cout<< e<< " "; // 1 10 20 30 2 3 4
	}
	cout<< endl;
    for(auto e : lt1)
    {cout<< e<< " "; // 空
    }
}

6.3.move和move_if

move作用是從容器中刪除所有與 val 相等的元素。這將調用這些對象的析構函數，并通過刪除的元素數來減小容器大小。

void list_test6()
{listlt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
    lt1.push_back(2);
    
	lt1.move(2);
    for(auto e : lt1)
    {cout<< e<< " "; // 1 3 4
    }
    cout<< endl;
}

move_if作用是移除滿足條件的元素。這將調用這些對象的析構函數，并通過刪除的元素數來減小容器大小。

// 是否為偶數
bool is_even(const int& value)
{return (value % 2) == 0;
}
// 是否為奇數
struct is_odd {bool operator() (const int& value)
  {  return (value % 2) == 1;
  }
};

int main ()
{int arr[]= {15,36,7,17,20,39,4,1};
  	listlt1 (arr, arr+8);  // 15 36 7 17 20 39 4 1
    
  	lt1.remove_if (is_even);    
    
 	for(auto e : lt1)
    {cout<< e<< " "; // 15 36 7 17 39 1
    }
    cout<< endl;
    
  	lt1.remove_if (is_odd());  
    for(auto e : lt1)
    {cout<< e<< " "; // 空
    }
    cout<< endl; 
 	return 0;
}

6.4.unique和merge

unique是刪除list中的重復元素。

void list_test5()
{listlt;
 listlt;
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(6);
	lt.push_back(23);
	lt.push_back(10);
	lt.push_back(3);
 lt.push_back(10);
	lt.sort();
	lt.unique();
	for (auto e : lt)
 {cout<< e<< " ";//2 3 6 10 23
 }
}

• 注意：要想對list進行真正的去重，必須先排序。

merge的作用是合并兩個鏈表，并且這兩個鏈表必須是有序的。

void list_test6()
{listlt1;
	lt1.push_back(10);
	lt1.push_back(30);
	lt1.push_back(20);

	listlt2;
	lt2.push_back(3);
	lt2.push_back(2);
	lt2.push_back(1);
	lt2.push_back(4);

 lt1.sort();
 lt2.sort();
 lt1.merge(lt2);

 for(auto e : lt1)
 { cout<< e<< " "; // 1 2 3 4 10 20 30 
	}
 cout<< endl;

6.5.reverse

reverse的作用是反轉list中元素的順序。

void list_test6()
{listlt1;
    for(int i = 1; i<= 5; i++)
    {lt1.push_back(i);
	}
    reverse(lt1);
    for(auto e : lt1)
    {cout<< e<< " "; // 5 4 3 2 1
	}
    cout<< endl;
}

---

7.list與vector對比

	vector	list
底層結構	動態順序表，一段連續空間	帶頭結點的雙向循環鏈表
隨機訪問	支持隨機訪問，訪問某個元素效率O(1)	不支持隨機訪問，訪問某個元素效率O(N)
插入和刪除	任意位置插入和刪除效率低，需要搬移元素，時間復雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導致效率更低	任意位置插入和刪除效率高，不需要搬移元素，時間復雜度為O(1)
空間利用率	底層為連續空間，不容易造成內存碎片，空間利用率高，緩存利用率高	底層節點動態開辟，小節點容易造成內存碎片，空間利用率低，緩存利用率低
迭代器	原生態指針	對原生態指針(節點指針)進行封裝
迭代器失效	在插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導致重新擴容，致使原來迭代器失效，刪除時，當前迭代器需要重新賦值否則會失效	插入元素不會導致迭代器失效，刪除元素時，只會導致當前迭代器失效，其他迭代器不受影響
使用場景	需要高效存儲，支持隨機訪問，不關心插入刪除效率	大量插入和刪除操作，不關心隨機訪問

---

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章標題：【C++】STL——list的常用接口-創新互聯
文章路徑：http://www.js-pz168.com/article14/csgdde.html

成都網站建設公司_創新互聯，為您提供云服務器、做網站、定制網站、網站改版、App設計、網站維護

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯