前言

前面我們已經(jīng)學(xué)習(xí)了string和vector的模擬實(shí)現(xiàn)和使用，相信對于容器的模擬實(shí)現(xiàn)和使用的能力已經(jīng)上升一定的水平，今天我們要學(xué)習(xí)的是list的模擬實(shí)現(xiàn)，List的模擬實(shí)現(xiàn)和string和vector其實(shí)沒有本質(zhì)的區(qū)別，只是在list的模擬實(shí)現(xiàn)過程中，list的迭代器和string和vector有所不同，這是我們實(shí)現(xiàn)List的模擬實(shí)現(xiàn)中需要重點(diǎn)掌握的，今天學(xué)習(xí)的List本質(zhì)就是一個(gè)帶頭雙向循環(huán)鏈表。

一、關(guān)于list

1. 簡介

list本質(zhì)就是一個(gè)帶頭雙向循環(huán)鏈表，支持在任何位置以O(shè)(1)的時(shí)間進(jìn)行插入和刪除。

2. 成員類型

看到上圖，我們一定要知道迭代器的類型：list中的迭代器的類型是雙向迭代器，其他的迭代器類型好還有：單向迭代器，隨機(jī)迭代器。

• 單向迭代器：只支持單向遍歷訪問的迭代器，只支持++，不支持–
• 雙向迭代器：支持雙向訪問容器的迭代器，同時(shí)支持++和–
• 隨機(jī)迭代器：支持隨機(jī)訪問容器的迭代器，同時(shí)支持++，–，+，-

二、默認(rèn)成員函數(shù)

1. 構(gòu)造函數(shù)

1. list()

• 使用代碼

void test_list1()
{// 無參構(gòu)造函數(shù)list<int> lt1;// 創(chuàng)建一個(gè)存儲int的list對象list<char> lt2;// 創(chuàng)建一個(gè)存儲char的list對象list<double> lt3;// 創(chuàng)建一個(gè)存儲double的list對象list<string> lt4;// 創(chuàng)建一個(gè)存儲string的list對象
}

2. list(size_t n,const T& val = T())和list(InputIterator first,InputIterator last)

• 使用代碼：

void test_list2()
{// 用n個(gè)值來構(gòu)造Listlist<int> lt1(3, 6);// 用3個(gè)6來構(gòu)造一個(gè)list對象// 使用一段迭代器區(qū)間來構(gòu)造string s2("hello list::list(InputIterator first,InputIterator last)");vector<char> v2(s2.begin(), s2.end());list<char> lt2(v2.begin(), v2.end());// 遍歷// 使用迭代器進(jìn)行遍歷// 遍歷lt1cout << "lt1:" << endl;list<int>::iterator lit1 = lt1.begin();while (lit1 != lt1.end()){cout << *lit1 << " ";lit1++;}cout << endl;// 遍歷lt2cout << "lt2:" << endl;list<char>::iterator lit2 = lt2.begin();while (lit2 != lt2.end()){cout << *lit2 << " ";lit2++;}cout << endl;// 使用范圍for進(jìn)行遍歷cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto& e : lt2){cout << e << " ";}cout << endl;}

運(yùn)行結(jié)果：

2. 拷貝構(gòu)造函數(shù)

拷貝構(gòu)造函數(shù)和前面的容器樣子還是差不多

void test_list3()
{string s("hello list(const list<char>& lt)");list<char> lt1(s.begin(), s.end());list<char> lt2(lt1);cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;cout << "lt2" << endl;for (auto& e : lt2){cout << e << " ";}cout << endl;
}

運(yùn)行結(jié)果：

3. 析構(gòu)函數(shù)

4. 賦值運(yùn)算符重載函數(shù)

• 使用代碼：

void test_list4()
{string s("hello list<char>& operator=(const list<char>& lt)");list<char> lt(s.begin(), s.end());list<char> lt1;lt1 = lt;// 調(diào)用賦值運(yùn)算符重載函數(shù)cout << "lt:" << endl;for (auto& e : lt){cout << e << " ";}cout << endl;cout << "lt1:" << endl;for (auto& e : lt1){cout << e << " ";}cout << endl;}

運(yùn)行結(jié)果：

三、迭代器

1. 普通對象的正向迭代器

• 使用代碼：

void test_list5()
{string s("hello list<char>::iterator begin() and end()");list<char> lt(s.begin(), s.end());list<char>::iterator lit = lt.begin();while (lit != lt.end()){cout << *lit << " ";lit++;}cout << endl;
}

運(yùn)行結(jié)果：

2. const對象的正向迭代器

• 使用代碼：

void test_list6()
{string s("hello list<char>::const_iterator begin() and end()");const list<char> lt(s.begin(), s.end());list<char>::const_iterator lit = lt.begin();while (lit != lt.end()){cout << *lit << " ";lit++;}cout << endl;
}

運(yùn)行結(jié)果：

3. 普通對象的反向迭代器

使用代碼：

void test_list7()
{string s("hello list<char>::reverse_iterator begin() and end()");list<char> lt(s.begin(), s.end());list<char>::reverse_iterator lit = lt.rbegin();while (lit != lt.rend()){cout << *lit << " ";lit++;}cout << endl;
}

4. const對象的反向迭代器

四、容量接口

1. empty()

2. size()

五、元素訪問接口

1. front()

2. back()

六、修改接口

1. push_front()

2. pop_front()

3. push_back()

4. pop_back()

5. insert()

6.erase()