class template

std::list

前言

• 📄本文內容：C++ STL list
• 📇 所屬專欄：C/C++ | 全面理解C++ STL標準模板庫
• 👤 作者主頁：紫荊魚
• 📆 創作時間：2022-1-3
• 📟 小小提示：文章很長，十分詳細，建議先收藏

🔙回傳目錄（建議收藏）：全面理解C++ STL標準模板庫

0.什么是list

定義：list是序列容器，允許在序列內的任何地方進行恒定時間插入和擦除操作，以及雙向迭代，
串列容器被實作為雙向鏈表；雙向鏈表可以將它們包含的每個元素存盤在不同且不相關的存盤位置，排序是通過與指向它前面元素的鏈接和指向它后面元素的鏈接的每個元素的關聯在內部保持的，

1.list原理

template < class T, class Alloc = allocator<T> > class list;

🎙引數解釋：

1. T：成員型別list::value_type，
2. Alloc：用于定義存盤分配模型的分配器物件的型別，

📜頭檔案：

#include <list>

2.list建構式-定義list

🔎注：(1)(2)(3)(4)為C++98標準，(5)(6)為C++11新標準

(1) 默認建構式

//構造一個空容器，沒有元素，
explicit list(const allocator_type& alloc=allocator_type());

例子：std::list<int> first;

(2) 填充建構式

//構造一個包含n個元素的容器，每個元素都是val的副本（如果提供），
explicit list (size_type n);
         list (size_type n, const value_type& val,
                const allocator_type& alloc =
  		 allocator_type());

例子：std::list<int> second (4,100);

(3) 范圍構造器

//構造一個包含與范圍[first,last)一樣多的元素的容器
//每個元素都從該范圍內的相應元素以相同的順序安放構造，
template <class InputIterator>
		list (InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type());  

例子1：std::list<int> third (second.begin(),second.end());
例子2： int myints[] = {16,2,77,29};
std::list<int> fifth (myints, myints + sizeof(myints) / 
					  sizeof(int) );

(4) 復制建構式（和用分配器復制）

//以相同的順序構造一個容器，其中包含x中每個元素的副本，
list (const list& x);
list (const list& x, const allocator_type& alloc);

例子： std::list<int> fourth (third);

(5) 移動建構式（和分配器一起移動）

//構造一個獲取x元素的容器，
//如果指定了alloc并且與x的分配器不同，則移動元素，
//否則，不會構造任何元素（它們的所有權直接轉移），
//x處于未指定但有效的狀態，
list (list&& x);
list (list&& x, const allocator_type& alloc);

例子：std::list<std::string> words8(std::move(words6));

(6) 初始化串列建構式

//以相同的順序構造一個容器，其中包含il中每個元素的副本，
list (initializer_list<value_type> il,
     const allocator_type& alloc = allocator_type());

例子：std::list<std::string> words10 
{"the", "frogurt", "is", "also", "cursed"};

3.串列list的輸出

🖊注：不能通過計數器+索引[ ]來實作輸出

(1)通過迭代器輸出

//（1）迭代器輸出常用形式
void my_print(std::list<int> &li)
{
	for(std::list<int>::iterator it=li.begin();it!=li.end();it++)
	{
		std::cout<<(*it)<<" ";
	}
	std::cout<<std::endl;
}

//(2)通過auto/typedef/type alias獲得迭代器型別
void my_print(std::list<int> &li)
{
	for (auto i = li.begin(); i != li.end(); i++)
	{
    	std::cout << *i << ' ';
	}
	std::cout<<std::endl;
}

//(3)使用range-base,原理類似（2）
void my_print(std::list<int> &li)
{
	for (auto i : li)
    std::cout << i << ' ';
}

📉以上三種輸出方式輸出結果：

4.list增加和洗掉內容

(1)list::push_back和list::pop_back

//在串列容器的末尾，在其當前最后一個元素之后添加一個新元素，
do {
    std::cin >> myint;
    mylist.push_back (myint);
} while (myint);

//移除串列容器中的最后一個元素，有效地將容器大小減一， 
while (!mylist.empty())
{
   sum+=mylist.back();
   mylist.pop_back();
}

(2)list::push_front 和 list::pop_front

//在串列的開頭插入一個新元素，就在其當前第一個元素之前
mylist.push_front (200);
mylist.push_front (300);

//在串列的開頭洗掉一個元素，就在其當前第一個元素之前
while (!mylist.empty())
{
    std::cout << ' ' << mylist.front();
    mylist.pop_front();
}

(3)list::insert 和list::erase

🪧insert：通過在指定位置的元素之前插入新元素來擴展容器
🪧erase：從串列容器中洗掉單個元素 ( position ) 或一系列元素 ( [first,last) )，

std::list<int> mylist;
std::list<int>::iterator it;

mylist.insert (it,10);    // 1 10 2 3 4                 
mylist.insert (it,2,20);  // 1 10 20 20 2 3 4 5        ^

std::vector<int> myvector (2,30);
mylist.insert (it,myvector.begin(),myvector.end());
// 1 10 20 30 30 20 2 3 4 5

//洗掉it1位置的元素
mylist.erase (it1);
//洗掉[it1,it2)區間的元素
mylist.erase (it1,it2);

5.迭代器

公共成員函式

(1)list::begin 和 list::end

//begin功能：將迭代器回傳到開頭（公共成員函式）
//end功能：回傳迭代器結束（公共成員函式）
for(std::list<int>::iterator it=mylist.begin();
	it != mylist.end(); ++it)

(2)list::rbegin 和 list::rend

🪧rbegin和begin區別： rbegin指向成員end指向的元素之前的元素，即list最后一個元素，
🪧rend和end區別： 指向串列容器中第一個元素之前的理論元素（被認為是它的反向端）
如下圖：

//rbegin功能：回傳反向迭代器以反向開始，
//rend功能：回傳反向迭代器以反向結束，
for (std::list<int>::reverse_iterator rit=mylist.rbegin(); 
	rit!=mylist.rend(); ++rit)
    std::cout << ' ' << *rit;

(3)list::cbegin 和 list::cend

🐈🐈??區別：回傳型別為迭代器

//cbegin功能：回傳指向容器中第一個元素的const_iterator，
//cend功能：回傳指向容器中最后一個元素的 const_iterator
for (auto it = mylist.cbegin(); it != mylist.cend(); ++it)
    std::cout << ' ' << *it;

(4)list::crbegin 和 list::crend

🔎注：結合(2)(3)的特點：反向+迭代器

//回傳一個const_reverse_iterator指向容器中的最后一個元素
//回傳一個const_reverse_iterator指向容器中第一個元素之前的理論元素
for(auto rit=mylist.crbegin(); rit!=mylist.crend();++rit)
    std::cout << ' ' << *rit;

6.list容量Capacity

🔎注：功能直觀，不做解釋

(1)list::empty

//判斷list是否非空，求和
 while (!mylist.empty())
  {
     sum += mylist.front();
     mylist.pop_front();
  }

(2)list::size

//輸出大小size
for (int i=0; i<10; i++) myints.push_back(i);
  std::cout << "1. size: " << myints.size() << '\n';

(3)list::max_size

//如果小于最大size，就繼續resize,resize重置size
if (i<mylist.max_size()) mylist.resize(i);

7.元素訪問函式

(1)list::front 和 list::back

//front:回傳對串列容器中第一個元素的參考
//back:回傳對串列容器中最后一個元素的參考，
mylist.front() -= mylist.back();
std::cout<< mylist.front()<<mylist.back();

8.其他修飾符

(1)list::clear

👻clear：從串列容器中移除所有元素（已銷毀），并保留大小為0的容器，

mylist.clear();

(2)list::resize

👻resize：調整容器大小，使其包含n 個元素，

//n:新容器大小，以元素數表示
//val:如果n大于當前容器大小，則將其內容復制到添加元素的物件，
//如果未指定，則使用默認建構式，
void resize (size_type n, value_type val = value_type());

//例子
mylist.resize(5);
mylist.resize(8,100);
mylist.resize(12);

(3)list::swap

👻swap：交換內容

std::list<int> first (3,100);
std::list<int> second (5,200);

first.swap(second);

(4)list:assign

👻assign：將新內容分配給串列容器，替換其當前內容，并相應地修改其大小，

first.assign (7,100);
second.assign (first.begin(),first.end());

int myints[]={1776,7,4};
first.assign (myints,myints+3);

9.list操作

(1)拼接list::splice

mylist1.splice (it, mylist2);     
mylist2.splice (mylist2.begin(),mylist1, it);// "it" is now invalid.

it = mylist1.begin();
std::advance(it,3); // "it" points now to 30

mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
  

(2)洗掉重復值list::unique

// a binary predicate implemented as a function:
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }

// a binary predicate implemented as a class:
struct is_near {
  bool operator() (double first, double second)
  { return (fabs(first-second)<5.0); }
};

mylist.unique();
mylist.unique (same_integral_part);
mylist.unique (is_near());

(3)排序list::sort

mylist.sort();
mylist.sort(compare_nocase);

// comparison, not case sensitive.
bool compare_nocase (const std::string& first, const std::string& second)
{
  unsigned int i=0;
  while ( (i<first.length()) && (i<second.length()) )
  {
    if (tolower(first[i])<tolower(second[i])) return true;
    else if (tolower(first[i])>tolower(second[i])) return false;
    ++i;
  }
  return ( first.length() < second.length() );
}

10.Python和C++的list比較

從資料結構角度看

• STL: list 雙向鏈表
• Python：list 類似于陣列array

很感謝你的閱讀，如有幫助給個贊吧，謝謝大家！