C++實現list增刪查改模擬的示例代碼
更新時間：2023年12月26日 09:29:04 作者：小宇成長錄
本文主要介紹了C++實現list增刪查改模擬,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
前言
本篇博客采用SGI版本，同時考慮到看到此篇博客大部分為初學者，為此博主僅僅給出有用片段。C++:list增刪查改模擬實現就是用C++復寫雙鏈表，非常簡單。難點主要在迭代器實現
一、list底層雙鏈表驗證、節(jié)點構造
1.1 list底層數據結構
list底層使用什么數據結構來實現的呢？我們先來看看SGI庫中l(wèi)ist的成員函數和初始化吧。
我們發(fā)現list實現中，只有node一個成員變量。構造函數構造出一個頭尾相連的哨兵位。同時驗證了list底層是一個帶哨兵位的雙鏈表。
1. 2 節(jié)點構造
節(jié)點和雙鏈表一樣有三個成員：節(jié)點數據、指向前一個節(jié)點(prev)、指向后一個節(jié)點(next)。
//節(jié)點
template<class T>
struct List_node
{
T _data;
List_node<T>* _prev;
List_node<T>* _next;
List_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};
小tips:
- 我們這里類名和庫中一樣(List_node)，后續(xù)在其他類中使用時在typedef。
- 這里類名使用struct而不是class原因在于struct默認訪問權限為公有，后續(xù)其他類只都需要大量使用。如果使用class需要使用大量友元類，過于繁瑣。
二、迭代器封裝實現（重點、難點）
2.1 前置說明
- 我們知道迭代器的最大用途便是遍歷數據。但何時停在，迭代器指向空間存儲數據時是什么…導致我們需要使用!=、++、*等操作。但自定義類型是無法支持使用這些操作符的。為此給出的解決辦法是：封裝加運算符重載。
- 迭代器使用上分為普通迭代器和const迭代器（還分為單向迭代器、雙向迭代器和隨機訪問迭代器）。其中一種最簡單的實現方式就是實現兩個類。但。。。我們知道兩個迭代器的不同之處在于const迭代器無法修改數據，只是j相關借口（這里有*、->）不同而已便實現兩個類未免過于“小題大做”。
所以接下來我們來看看庫中是如何巧妙的解決這個問題吧！
2.2 迭代器實現
前置說明中以及解決了如何實現一個類達到目的。接下來的實現過于簡單就不單獨說明了。
//迭代器封裝
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef List_node<T> Node;//節(jié)點類名重命名
//由于迭代器實現中,如++、--等重載函數返回值類型為__list_iterator，名字過長,這里我們重命名self意味自身
typedef __list_iterator<T,Ref, Ptr> self;
Node* _node;//成員變量
__list_iterator(Node* node)//構造出一個節(jié)點
:_node(node)
{}
//前置++
self& operator++()
{
_node = _node->_next;
return *this;
}
//前置--
self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//后置--
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
//解引用操作符重載
Ref operator*()
{
return _node->_data;
}
//用于訪問迭代器指向對象中存儲的是自定義類型
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
三、list實現
3.1 基本框架
list模擬中，我們和庫中一樣，給出一個頭節(jié)點_head、_size兩個成員變量。同時我們將節(jié)點、迭代器進行重命名。迭代器重命名不是單純圖方便，更重要的是提供統一接口(例如sting、vector、set等接口都一樣)，屏蔽底層的變量和成員函數屬性，實現過程和差異。
//list模擬實現
template<class T>
class List
{
typedef List_node<T> Node;
public:
//迭代器重命名，提供統一的接口，屏蔽底層實現細節(jié)和差異
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
Node* _head;//頭節(jié)點
int _size;
};
3.2 迭代器和const迭代器
下面是begin()、end()指向一個有效雙線表的位置。
實現：
const_iterator begin()const
{
//return const_iterator(_head->_next);或
return _head->_next;//單參數類型支持隱式類型轉換
}
const_iterator end()const
{
return _head;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
3.2 構造函數、析構函數、拷貝構造、賦值重載
3.2.1 構造函數
構造函數的實現和開頭中看到的一樣：構造函數中調用一個函數（empty_Init）來是實現。empty_Init()用來完成初始化。（empty_Init()函數后續(xù)其他接口也要調用）
//初始化
void empty_Init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//無參構造
List()
{
empty_Init();
}
3.2.2 析構函數
析構函數我們調用一個clear函數來將數據全部清空，在將_head變量釋放。
//析構函數
~List()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
3.2.3 拷貝構造
拷貝構造時首先要初始化出一個節(jié)點，然后將需要拷貝的數據依次尾插即可（尾插接口后續(xù)給出實現）
//拷貝構造
List(const List<T>& It)
{
empty_Init();
for (auto e : It)
{
push_back(e);
}
}
3.2.4 賦值重載
賦值重載有很多方式。比較簡單的參數我們直接傳值，然后將待賦值的變量和傳值傳參省生成的臨時變量的數據進行交換即可。
void swap(const List<T>& It)
{
std::swap(_head, It._head);
}
//賦值重載
List<T>& operator=(const List<T> It)
{
swap(It);
return *this;
}
3.3 任意位置插入、任意位置刪除、尾插、尾刪、頭插、頭刪
3.3.1任意位置插入
首先new出待插入節(jié)點newnode，然后將pos前一個節(jié)點prev、newnode、pos相連。最后++_size即可。
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
_size++;
return newnode;
}
3.3.2任意位置插入刪除
將待刪除數據的前后節(jié)點先保存起來，然后將刪除pos處節(jié)點，再將前后節(jié)點連接起來。最后–_size即可。
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
delete cur;
prev->_next = next;
next->_prev = prev;
_size--;
return next;
}
3.3.3 尾插、尾刪、頭插、頭刪
尾插、尾刪、頭插、頭刪都是復用任意位置插入、任意位置刪除接口。
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
四、list功能完善
4.1 迭代器operator->()
我們先來看看下面這段代碼對嗎？
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test_list3()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
cout<<*it<<" ";
++it;
}
cout << endl;
}
由于list沒有重載<<，所以對存儲的是自定義類型之間訪問會編譯報錯。
那我們重載下<<運算符不就行了嗎？很不幸的是C++庫在list中不支持<<，很大原因也在于編譯器不知到我們如何取數據
所以對于自定義類型我們可以先解引用在去訪問成員，也可以在迭代器中重載operator->()函數。但需要注意的是編譯器隱藏了一個->，具體原生行為如下：
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
,_a2(a2)
{}
int _a1;
int _a2;
};
void test_list3()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1<<" "<<(*it)._a2 << endl;
cout << it->_a1 << " " << it->_a2 << endl;
//上面編譯器訪問成員變量的真正行為如下：
//cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;
++it;
}
cout << endl;
}
4.2 打印數據
//大多數情況模板是class還是typename是一樣的，但當有未實例化模板時，必須使用typename
//template<typename T>
void print_list(const list<T>& lt)
{
// list<T>未實例化的類模板，編譯器不能去他里面去找
// 編譯器就無法list<T>::const_iterator是內嵌類型，還是靜態(tài)成員變量
// 前面加一個typename就是告訴編譯器，這里是一個類型，等list<T>實例化
// 再去類里面去取
typename list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
優(yōu)化：上面打印數據是針對list，下面是針對容器的。
// 模板(泛型編程)本質，本來應該由我們干的活交給編譯器
template<typename Container>
void print_container(const Container& con)
{
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
五·、所有代碼以及測試用例
推薦：giteeC++:list增刪查改模擬實現代碼（最終版本、感覺版本?。。。?/a>
到此這篇關于C++實現list增刪查改模擬的文章就介紹到這了,更多相關C++ list增刪查改 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
SQLite是一種輕量級的嵌入式數據庫,可以利用SQLiteSDK執(zhí)行數據庫的增刪改查操作,本文主要介紹了C++通過SQLiteSDK增刪改查,具有一定的參考價值,感興趣的可以了解一下2025-03-03
QWidget類是所有用戶界面對象的基類,被稱為基礎窗口部件,下面這篇文章主要給大家介紹了關于QT中大部分部件如何使用的相關資料,需要的朋友可以參考下2022-06-06
這篇文章主要為大家詳細介紹了C++使用string的大數乘法運算，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-09-09
ReSharperC++是為c/c++開發(fā)者打造的一款實用Visual Studio擴展插件，這款插件旨在提升開發(fā)者的效率，今天給大家分享這款軟件的激活方法，需要C++ ReSharper2021激活碼的朋友參考下本文2021-06-06
這篇文章主要介紹了C++中this指針用法詳解及實例的相關資料,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了C++ 標準模板庫 STL 順序容器詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
Ubuntu20.04安裝使用jsoncpp、json-c庫的方法實例
這篇文章主要給大家介紹了關于Ubuntu20.04安裝使用jsoncpp、json-c庫的相關資料,文中通過代碼介紹的非常詳細,對大家的學習或者工作就有一定的參考借鑒價值,需要的朋友可以參考下2024-04-04
這篇文章主要介紹了C語言 棧的表示和實現詳細介紹的相關資料,需要的朋友可以參考下2016-12-12
本文主要介紹了淺談C++反向迭代器的設計，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
這篇文章主要為大家介紹了Qt中是如何實現通用數據庫請求的，文中的示例代碼講解詳細，對我們學習Qt有一定幫助，感興趣的小伙伴可以了解一下2022-03-03