【c++進階系列】：map和set的模擬實現(附模擬實現的源碼）

🔥 本文專欄：c++
🌸作者主頁：努力努力再努力wz

在這里插入圖片描述

💪 今日博客勵志語錄：每一次抉擇，都是將未來的自己輕輕推向某個方向

★★★ 本文前置知識：

紅黑樹

原理

那么在上一期博客中，我著重講解了紅黑樹的原理以及如何用代碼來實現紅黑樹，在有了紅黑樹的知識后，我們便又能掌握并且實現stl中的另外兩個容器，其便是set和map，那么set和map的底層結構采取的就是紅黑樹，而set的是key模型的紅黑樹，而map則是key-value模型的紅黑樹

既然set以及map分別對應的是key模型的紅黑樹以及key-value模型的紅黑樹，這里便引出本文的第一個思考點：這里stl的設計者如果實現set以及map的話，那么他是會分別為set和map編寫一份key模型的紅黑樹的代碼和key-value模型的紅黑樹代碼還是說兩者共用一個紅黑樹的代碼？

在揭曉答案之前，我們可以自己先推導一下，首先key模型的紅黑樹以及key-value模型的紅黑樹中對應的節點的定義是不一樣的，那么key模型的紅黑樹節點的數據域則是存儲一個鍵值即可，而key-value模型的紅黑樹則是存儲一個鍵值對，也就是pair

其次就是對于紅黑樹相關操作的函數，比如以insert插入函數為例，那么key模型的紅黑樹的insert函數則是需要獲取一個鍵值，然后拷貝到新插入的節點中，而對于key-value模型的紅黑樹的insert函數來說，其會接收一個鍵值對，也就是pair，然后拷貝到新插入的節點中

所以理論上，我們確實可以分別為set以及map各自分別編寫適應其自身特性的紅黑樹代碼，但是根據上文的分析，我們可以發現，其實set和map底層對應的紅黑樹代碼的邏輯幾乎是相同的，以紅黑樹的insert函數為例，set和map最多就是拷貝到新插入節點中的數據不同，其他邏輯都是一樣的，而對于紅黑樹的節點的定義來說，其同樣就只有存儲的數據域的數據類型不同，其他都是相同的

所以我們沒必要為map和set各自編寫一份代碼，而事實上，stl的設計者也確是沒這么做，而上文所說的場景，也就是map和set底層的紅黑樹的代碼邏輯幾乎相同，唯一不同的就是處理的紅黑樹節點中的數據域的數據類型

而這個場景正是模版所應用的場景：模版只關心代碼的邏輯，而不關心其處理的數據，那么具體處理什么類型的數據，則是由模版的實例化來決定

而模版的核心思想就是代碼復用，所以這里stl的設計者實現map和set的核心思想就是復用同一個紅黑樹的模板類，而復用的這個紅黑樹的模板類，則是key-value模型的紅黑樹

而map和set這種復用已經實現好了的數據結構，而不用我們自己單獨在為map和set重新完整編寫適應其自身特性的一個數據結構的方式，便是我們熟悉的容器適配器模式，包括stl庫中的棧和隊列這兩種容器，也是采取這種方式，直接復用庫中已經實現好的vector和list

既然復用的是key-value模型的紅黑樹模板類，那么這里對于set來說，由于其是key模型，但是為了讓key-value模型的紅黑樹支持set，所以這里將set底層的紅黑樹的這兩個模版參數key和value都實例化為key

但由于map本身就是key-value模型，那么這里是不是意味著map可以直接按照我們最熟悉的方式，也就是key模版參數實例化為鍵值key，而value模版參數則是實例化鍵值key對應的值value

這樣做看似沒有任何問題，但是事實上，由于這里set和map都是復用同一個紅黑樹的模板類，那么對于紅黑樹中某些成員函數來說，就會有影響，代表的就是insert函數，雖然map和set的insert函數的邏輯幾乎相同：其都是先借助二叉搜索樹的左小右大的性質，然后尋找定位到新插入節點的位置以及其父節點，然后再將insert接收到的參數拷貝到創建好的新節點中，而該值對于map則是一個pair<key，val>類型，對于set則是一個key類型，最后一步則是調節平衡，會沿途往上遍歷祖父節點，如果不平衡就變色或者旋轉加變色來調整平衡

但是如果這里對于map來說，其key和value就分隊對應鍵值對的第一個元素和第二個元素的數據類型，那么接下來你將會面對一個問題，就是這里insert函數的原型你該怎么書寫

由于這里map和set都是復用同一套紅黑樹的模板類，意味著這里insert函數需要能夠同時接收key類型的參數以及pair<key，val>類型的參數

有的讀者認為，這里我確實無法僅僅靠一個insert接口來同時接收并且處理兩種數據類型，但我可以通過在紅黑樹的模板類編寫兩個insert成員函數，一個接收key類型的參數，另一個接收pair<key,val>類型的模版參數，那么這兩個成員函數的函數名相同，但參數列表不同，讓它們構成函數重載，到時候根據傳遞的實參確定調用哪個成員函數

理論上，這種實現方式確實可行，但是這里我想說的是，這里實現map和set采取的是代碼的復用的思想，所謂的代碼的復用，其實是一種泛型編程，那么這里作為底層復用的紅黑樹模板類，它是不知道也不會關心上層要處理的數據類型是什么，而如果我們采取上文的方式，是與這里代碼的復用完全相違背的，因為編寫了處理特定數據類型的代碼，而模版的核心思想正是忽略處理的數據類型，只關心代碼的邏輯
所以這里stl的設計者巧妙的將key-value模型的紅黑樹模板類的第二個模版參數，也就是value，將其視作通用數據類型T，將key-value模型的紅黑樹變成key-T模型的紅黑樹

那么這里我在額外補充說明一下我剛才說的話，這里的紅黑樹模板類還是key-value模型，只不過，這里的第二個模版參數不再代表為鍵值key或者鍵值key對應的值val，而是代表一個紅黑樹節點數據域存儲的數據類型，那么對于set來說，其紅黑樹節點中存儲的數據域就是一個鍵，也就是key，那么這里的T就會被實例化為key，而對于map來說，其紅黑樹節點中存儲的數據域則是一個pair，那么這里這里的T會被實例化為pair

而這里的第二個模版參數會被實例化為key或者pair的好處便是解決了上文我說的那個問題，這樣我們讓map和set復用同一個函數接口，比如insert函數，那么這里的insert的函數原型我們就可以寫出：

void insert(const T& p);

那么由于這里紅黑樹的第二個模版參數代表的就是紅黑樹節點中數據域存儲的數據類型，所以這里我們也要對紅黑樹節點的模板類進行一個修改，那么原本的紅黑樹節點的模板類需要兩個模版參數，那么現在其只需要一個模版參數T即可

enum  color
{BLACK,RED
};
template<typename T>
class RBTreeNode
{
public:RBTreeNode<T>* left;RBTreeNode<T>* right;RBTreeNode<T>* parent;T  data;color _col;RBTreeNode():_col(RED), left(nullptr), right(nullptr), parent(nullptr), data(T()){}RBTreeNode(const T& p):_col(RED), left(nullptr), right(nullptr), parent(nullptr), data(p){}
};

而對于insert函數來說，我們就可以只用同一個接口來實現set以及map節點的插入，那么其接收的參數就是T類型的參數，那么該T類型的參數既可以代表一個鍵值key的數據類型，也可以代表pair元組的類型，那么具體什么含義，則是由于上層的實例化來決定：

template<typename key>
class set
{priveate:RBTree<key,key> tree;...................public:void insert(const T& k){tree,insert(k);}
};

對于set來說，這里的第二個模版參數T會被實例化為key，那么這時候set復用底層紅黑樹的insert函數的時候，就只需要傳遞給T類型的參數，然后底層的紅黑樹的inser函數接收到這里的T類型的參數，創建完新節點之后，直接拷貝到新節點即可

對于map來說，這里上層的map類就需要將這里RBTree的第二個模版參數給實例化為pair<key,val>，然后上層在復用底層紅黑樹實現的insert函數，那么給紅黑樹的insert函數傳遞T類型的參數，然后底層的紅黑樹的insert函數直接將T類型的參數給拷貝到新插入的節點當中即可

template<typename key,val>
class map
{private:RBTree<key,std::pair<key,val>> tree;.....public:void insert(const T& k){tree.insert(k);}
}

所以這就是map和set借助第二個模版參數來，從而能讓同一個函數接口來處理不同的數據類型

有的讀者事先知道庫的map和set的insert函數的返回值的話，事實上庫的map和set的insert函數的返回值不是void，而是一個pair元組，那么之所以這里我選擇先寫成void，是因為返回的pair元組的first，也就是第一個元素是一個迭代器，而當前還沒有講解迭代器，會在后文講解，所以這里我先把insert函數的返回值設置為void，然后回在后文會逐漸補充完善map和set類的細節，完善這里的insert函數的實現

但話又說回來了，既然這里我們知道了紅黑樹的第二個模版參數代表紅黑樹節點中數據域存儲的數據類型，當前是set，就將其實例化為鍵值key，如果是map，就將其實例化為鍵值對pair，而這里的紅黑樹是一個key-T模型，意味著這里還有第一個模版參數key，而set和map則會將這第一個模版參數給實例化為各自的鍵的類型

對于set來說，其紅黑樹節點只需要存儲一個鍵值key即可，那么這里set將第二個模版參數T已經實例化為鍵值key，但這里第一個模版參數其也會被實例化為鍵值key，那么既然這里的key-T模型的紅黑樹的兩個模版參數都會被實例化同一個鍵值的數據類型，這樣是否會顯得有點冗余呢

而對于map來說，其第二個模版參數代表就是一個pair元組，這里既然第二個模版參數會被實例化為元組，那么為什么其也需要紅黑樹的第一個模版參數，將其實例化為鍵值對中的鍵的數據類型？根據上文，insert函數在獲取到T類型的參數，也就是接收到一個pair元組之后，那么就會直接將元組給拷貝到新插入的節點中即可

所以，這里對于set和map來說，那么紅黑樹的第一個模版參數到底有什么作用？那么要解釋清楚它的作用，就和接下來我要講的仿函有關，這里我先埋下一個伏筆

仿函數對象keyofT

這里雖然我們將第二個模版參數設置為了紅黑樹節點的數據域存儲的數據類型，從而可以統一并且維護一個函數接口，其中就包括insert函數，但是對于insert函數，確實這里insert函數能夠同時接收以及處理鍵值以及鍵值對，那么獲取到鍵值以及鍵值對之后，將其直接拷貝到新插入的節點之中

但是這里又會面臨另一個問題，根據insert函數的原理，那么在創建新插入的節點之前，首先需要定位新插入節點的位置以及其父節點，那么這里需要借助二叉搜索樹左小右大的性質，從根節點往下遍歷，每次遍歷都會排除一個子樹，確定往下遍歷的分支，其中就需要新插入的數據的鍵與當前節點的鍵比較

那么如果新插入的數據的鍵比當前遍歷的節點的鍵小就往左分支繼續遍歷，如果比當前節點的鍵大就往右分支繼續遍歷，那么對于set來說，由于其T會被直接實例化為鍵值key，那么set的insert函數接收到T類型的參數p，那么其可以直接用p去與節點的鍵去進行比較，但是對于map來說，那么其會將T實例化為pair類型，那么insert函數接收到T類型的參數p，而這里的T代表的其實是一個pair類型，這里如果我們將參數P還是按之前一樣，直接與節點的鍵去比較:

void insert(const T& p)
{.................Node* cur=root;Node* parent=nullptr;while(cur){if(p<cur->data){cur=cur->left}else if(p>cur->data){cur=cur->right;}else{return;}}..................
}

對于set來說，其沒有任何問題，因為到時候實例化之后的P代表的就是鍵值key，但是對于map來說，其實例化的p代表的是一個pair對象，而pair類一個自定義類型，而pair模板類的內部也確實定義了比較運算符重載函數，但是其比較運算符重載函數的邏輯則是：先比較pair的first元素的大小，如果pair的first的大小相同，那么在比較pair的second的元素的大小

而這里我們只需要比較pair的first，也就是鍵值，不需要比較pair的second，所以這里我們不能用pair自帶的運算符重載函數，而這里map和set都是共用同一個insert函數接口，這里我們也不可能對數據的類型做判斷，編寫這樣的代碼：if(T == key)

首先這里語法上就不通過，其次就算語法上允許，這里也與模版的泛型編程的思想相違背

所以這里我們就得準備一個仿函數，所謂的仿函數，就是在map以及set中定義一個內部類keyofT，然后這個內部類中定義了一個()運算符重載函數，而map的keyofT的()運算符重載函數的邏輯則是會接收一個T類型的參數，而這里的T會被實例化為pair類型，然后接收到pair對象之后，直接返回pair對象的first即可，而對于set的()運算符重載函數的邏輯則是接收一個T類型的參數，這里的T會被實例化為鍵值key類型，然后直接返回這里接收到的參數即可

template<typename key,typename val>
class map
{private:class keofMapT{public:const key& operator()(const T& p){return p.first;}};RBtree<key,std::pair<key,val>,keyofMapT> tree;public:.......................................
};
template<typename key>
class set
{private:class keyofSetT{const key& operator()(const T& p){return p;}};RBtree<key,key,keyofSetT> tree;public:.....................................
};

那么有了這里的內部類后，這里復用的底層的紅黑樹的模版類，除了有之前所說的兩個模版參數key和T之外，還得額外定義一個模版參數keyofT,這里的keyofT模版參數代表的就是帶有（)運算符重載函數的內部類類型，那么這里我們就只需要在insert函數中創建一個keyofT對象，也就是仿函數對象，然后再遍歷紅黑樹比較節點時，那么就調用仿函數對象的()運算符重載函數，對于set就直接返回鍵值，對于map就返回的是pair的first元素

template<typename key,typename T,typename keyofT>
class RBtree{private:........public:
void insert(const T& p)
{.............Node* cur = root;
Node* parent = nullptr;
KeyofT returnKey;
while (cur)
{if (returnKey(p) < returnKey(cur->data)){parent = cur;cur = cur->left;}else if (returnKey(p) > returnKey(cur->data)){parent = cur;cur = cur->right;}else{return ;}
}.............................
}..............  
};

所以這種方式，就很好實現了解耦，雖然這里紅黑樹引入了第三個模版參數并且這會在insert函數內部會創建一個仿函數對象，但是對于底層的紅黑樹的insert函數來說，其還是不知道也不關心處理的具體是哪種數據類型，也不知道這里的仿函數對象是map的仿函數對象還是set的

不僅維護了泛型處理的思想，并且正是這里的仿函數對象，能夠讓insert函數支持map的pair對象的比較以及set的鍵值的比較，讓set的比較邏輯和map的比較邏輯分開，實現了解耦

而這里就能解答上文埋下的伏筆，也就是此時紅黑樹的第一個模版參數究竟有什么用，那么就和這里的map和set的內部類定義的()運算符重載函數有關，那么這里()運算符重載函數要返回的是鍵，那么在聲明()運算符重載函數的時候，其中就要聲明返回值的類型，而這里的返回值就是鍵的類型，那么對于set來說，由于其只有一個鍵值，那么這里可以直接用T來作為()運算符重載函數的返回值類型，這是沒問題的

但是對于map來說，假設這里我們沒有第一個模版參數，也就是只有一個模版參數T和一個代表仿函數對象的模版參數keyofT,那么此時你該如何聲明map這里的()運算符重載函數呢？

那么有的讀者認為，這里pair的模板類內部，其將first元素的類型給typedef為了first_type,那么我們可以通過first_type獲取pair對象的first元素的類型

#include<iostream>
using namespace std;
int main()
{cout<<sizeof(pair<int,double>::first_type)<<endl;return 0;
}

在這里插入圖片描述

意味著這里我們可以采取first_type來聲明map的()運算符重載函數的返回值的數據類型：

T.first_type operator()(const T& p);

如果是這么思考的讀者，那么就對模版的實例化過程不太熟悉，那么在模版被實例化之前，那么編譯器會先對模板類以及模版函數進行檢查，其中就包括依賴模版參數的檢查和非依賴模版參數的名稱的查找，那么編譯器在檢查()運算符重載函數的時候，由于還沒有實例化的緣故，編譯器是不知道T的含義，也就是其代表的數據類型，那么其可能代表int，也可能代表pair，正是因為編譯器不知道T的具體含義，所以其不知道T.first_type是否合法，所以這里編譯是無法通過的，而這里之所以需要紅黑樹的一個模版參數，那么其原因及在這里

那么第一個模版參數代表的就是鍵的數據類型，第二個模版參數代表的則是紅黑樹節點數據域存儲的數據類型，那么有了這第一個模版參數之后，我們才能夠正確聲明某些函數的原型，其中就包括這里的()運算符重載函數

迭代器RBTree_iterator

接下來的內容便是完善map和set底層的紅黑樹的最后一個部分，便是迭代器，這里map和set肯定會提供迭代器，因為這里需要訪問容器中的元素，而由于map和set底層都是紅黑樹，所以這里的迭代器本質上其實就是一個指向紅黑樹節點的原生指針，那么我們用迭代器遍歷map和set的容器的時候，采取的就是通過自增以及自減運算符來遍歷整個容器，但是這里map和set底層是一棵紅黑樹，其不像vector那樣，其底層是一個線性并且物理內存連續的動態數組，所以這里就不能利用原生指針的自增以及自減運算符，意味著這里我們需要對紅黑樹的迭代器進行一個封裝，那么封裝的目的就包括重載其原生指針的自增以及自減運算符的行為

所以這里我們得準備一個RBTree_iterator模板類，那么模板類內部就會封裝一個指向節點的原生指針_Node，而由于這里的迭代器有const版本的迭代器和非const版本的迭代器，那么這里要實現const版本和非const版本的迭代器的第一個做法，就是直接分別為const版本的迭代器以及非const版本的迭代器各自編寫一個模板類

而這里由于map和set都是復用同一個紅黑樹模版，那么對于const版本和非const版本的迭代器，最優的方式也是復用同一個模板類，那么通過不同的實例化來得到const版本的迭代器以及非const版本的迭代器，所以這里我們將RBTree_iterator設置了三個模版參數：

template<typename T,typename ptr,typename ref>
class RBtree_iterator
{private:typedef RBTree_Node<T> Node;Node* _Node;.......................  
};

那么這里的第一個模版參數代表的就是紅黑樹節點數據域存儲的數據類型，而第一個模版參數則是代表的指向紅黑樹節點的數據域的指針，第三個參數則代表指向紅黑樹節點的數據域的引用

由于迭代器模擬的就是原生指針，那么意味著這里的迭代器也支持*運算符和-> 運算符，意味著這里RBTree_iterator模板類要重載 *運算符和->運算符，那么 *運算符的作用就是為了訪問紅黑樹節點中的數據域，所以這里的 *運算符就會返回紅黑樹節點中的數據域，其返回值就是紅黑樹節點的數據域的引用

而->運算符則是返回的是紅黑樹節點的數據域的指針

而這里的第二個模版參數以及第三個模版參數分別表示紅黑樹節點的數據域的指針以及引用，所以這里我們可以直接用第二個以及第三個模版參數作為* 運算符重載函數以及-> 運算符重載函數的返回值類型的聲明

ref operator*()
{return _Node->data;
}
ref operator*() const
{return _Node->data;
}
ptr operator->()
{return &_Node->data;
}
ptr operator->() const
{return &_Node->data;
}

當然這里我們也得提供* 運算符和-> 運算符的const版本，而這里我們知道由于* 運算符以及-> 運算符返回就是節點的數據域的指針以及引用，那么意味著我們可以通過*以及->運算符來訪問并且能夠修改紅黑樹節點中的數據域，而const版本的迭代器就是禁止修改迭代器指向的節點中的數據，所以這里對于常量迭代器來說，那么 *以及->返回值就應該是const修飾的指針以及引用，所以這里我們就能夠知道如何得到const版本的迭代器了，那么就是將第二個參數實例化為const T * 并且將第三個參數實例化為const T&，那么就能夠得到const版本的迭代器

template<typename key,typename T,typename keyofT>
class RBTree{
public:typedef RBTree_iterator<T, T*, T&> iterator;typedef RBTree_iterator<T, const T*, const T&> const_iterator;.............};

而接下來就是自增運算符的實現，那么我們知道map和set底層采取的紅黑樹本質是一棵二叉搜索樹，其滿足左小右大的性質，所以這里自增運算符遍歷出來的序列就是有序的，因為其是按照中序遍歷，也就是左-根-右，所以RBTree的begin()函數返回的迭代器的位置就是紅黑樹的左子樹的最左側的節點，也就是整棵樹值鍵值最小的節點作為起始位置

那么這里接下來實現自增運算符的核心就是確定移動的下一個節點的位置，那么在移動之前，我們知道當前迭代器指向的當前節點，其很可能是經過前面的遍歷到達到當前指向的節點，所以這里我們就需要判斷，如果當前迭代器指向的節點，其右子樹存在，那么我們就直接移動到右子樹中的最左側節點

那么這里為什么我們只關心當前迭代器指向節點的右子樹而不關心左子樹呢，是因為如果當前節點有左子樹，那么根據中序遍歷的順序，也就是左-根-右，那么迭代器能夠指向當前節點，一定是已經遍歷完了其左子樹才會指向當前作為局部搜索樹二叉樹的根節點，所以這里我們不需要關心左子樹，那么如果其有右子樹，說明右子樹還沒有被遍歷，所以我們就知道迭代器自增后的下一個位置就是右子樹中的最左節點

但是如果當前節點沒有右子樹，那么意味著當前迭代器指向的節點就是其所處的局部搜索二叉樹的右子樹中的最右側的節點，也就是右子樹中的最大值，說明其所處的局部搜索二叉樹左和根和右子樹都被遍歷完了，那么就得往上回溯，確定當前的局部搜索二叉樹整體是作為上層的根節點的左子樹還是右子樹，那么就得向上回溯，如果當前節點位于父節點的右側，說明當前局部搜索二叉樹整體位于父節點的右子樹，意味著以父節點為根節點的局部二叉搜索樹也被遍歷完，而這里遍歷的時候，我會定義兩個指針分別是cur和parent，此時就讓cur指針移到parent指向的父節點位置，然后parent移到父節點的父節點，繼續重復判斷，如果當前節點位于父節點的左側，說明其父節點的左子樹遍歷完了，那么其parent指向的父節點就是迭代器指向的下一個節點的位置

而如果此時cur都到根節點了，那么說明整棵紅黑樹都被遍歷完了，那么就不用再往上回溯了

self& operator++()
{if (_Node == nullptr){return *this;}if (_Node->right){Node* cur = _Node->right;while (cur->left){cur = cur->left;}_Node = cur;}else{Node* cur = _Node;Node* parent = cur->parent;while (parent && cur == parent->right){cur = parent;parent = cur->parent;}_Node = parent;}return *this;
}

而這里由于自增運算符返回的是一個迭代器，所以這里在RBTree_iterator內部又將迭代器本身typedef取了一個別名，為self：

typedef RBTree_iterator<T, ptr, ref> self;

而這里實現的是前置自增運算符重載函數，而后置自增的話，這是需要準備一個變量來保存之前的位置即可

而自減運算符重載函數則是和自增運算符是對稱的，那么自減運算符的遍歷的順序就是右-根-左，那么原理其實都差不多，只不過這里得判斷當前迭代器指向的節點的左子樹是否存在，如果存在，那么就確認下一個節點就是左子樹的最右節點，不存在，說明當前迭代器指向的節點就是局部二叉搜索樹的左子樹的最左側節點，就需要往上回溯

self& operator--()
{if (_Node == nullptr){return *this;}if (_Node->left){Node* cur = _Node->left;while (cur->right){cur = cur->right;}_Node = cur;}else{Node* cur = _Node;Node* parent = cur->parent;while (parent && cur == parent->left){cur = parent;parent = cur->parent;}_Node = parent;}return *this;
}

最后則是== 運算符重載函數以及!=重載運算符函數，那么其實現的邏輯就是會接收一個迭代器，然后比較迭代器中的封裝的指針是否指向同一個位置，如果指向同一個節點，那么就返回true，反之則返回false

而這里的 == 運算符重載函數以及!=運算符重載函數的后面都采用const修飾，因為這里只是比較而不會涉及到迭代器的指向的修改

bool operator==(const self& it) const
{return _Node == it._Node;
}
bool operator!= (const self& it) const
{return _Node != it._Node;
}

map和set的封裝

有了上文的仿函數對象以及迭代器的知識，那么這里我們就可以封裝紅黑樹RBTree模板類以及迭代器來實現map和set了，首先map和set中就得封裝以及維護一個紅黑樹對象，因為map和set的實現采取的是容器適配器模式，那么其中map和set的各種成員函數的實現則是會復用底層的紅黑樹的成員函數

其次就是迭代器，那么這里map和set也是直接復用底層紅黑樹的迭代器類型，那么對于set來說，那么其是key模型，那么意味著存儲在紅黑樹節點中的鍵是不能被修改的，而我們訪問set以及map容器中的元素就是通過迭代器，所以這里我們就得將set中的iterator和const_iterator都得設置為RBtree中const_iterator的別名，這樣你無論使用的是那種類型的set的迭代器，那么都無法修改紅黑樹節點中存儲的鍵值

template<typename key>
class set{
public:typedef typename RBTree<key, key, KeyofSetT>::const_iterator iterator;typedef typename RBTree<key, key, KeyofSetT>::const_iterator const_iterator;..........
private:class keyofSetT{public:const key& operator(const key& p){return p;}};RBtree<key,key,keyofSetT> tree;
};

而對于map來說，那么map的迭代器則是正常將RBTree中const版本的迭代器typedef定義為map的const版本的迭代器，將RBTree中非const版本的迭代器typedef定義為map的非const版本的迭代器

template<typename key, typename val>
class map
{
private:class KeyofMapT{public:const key& operator()(const std::pair<const key, val>& p){return p.first;}};RBTree<key, std::pair<const key, val>, KeyofMapT> tree;
public:typedef typename RBTree<key, std::pair<const key, val>, KeyofMapT>::iterator iterator;typedef typename RBTree<key, std::pair<const key, val>, KeyofMapT>::const_iterator const_iterator;.............................
};

但是這里要注意的就是，雖然我們可以用map的迭代器去訪問map容器中的元素，甚至去修改map容器中的元素，但是要注意的就是這里修改只能修改元組中的second，而不能修改元組中的first，而這里map不能采取set那樣的做法，也就是將RBTree中的const_iterator都設置為map的iterator和const_iterator,那么采取這種方式的話，那么就會導致map既不能修改元組中的first，也不能修改元組中的second

所以這里采取的做法就是將實例化的pair中的first元素的屬性給設置為const，那么采取這種做法，雖然我們可以通過迭代器訪問到pair中的const元素，但是我們如果嘗試修改它，那么在編譯階段就會報錯，所以這種方式是一個更合理的方式

insert函數

那么既然知道了紅黑樹的迭代器之后，那么我們就可以完善我們紅黑樹的insert函數以及find函數了，那么事實上，紅黑樹的insert函數的返回值并不是void，而是一個元組，那么元組的第一個元素就是一個迭代器，第二個元素則是一個bool值，那么如果插入失敗，也就是紅黑樹已經有該鍵值的節點，返回的元組的第一個元素就是指向紅黑樹當前已存在該鍵值的節點的迭代器，然后第二個元素設置為false

而如果插入成功，那么返回的元素的第一個元素就是指向新插入的節點的迭代器，然后第二個元素設置為true

	std::pair<iterator, bool> insert(const T& p){if (root == nullptr){root = new Node(p);root->_col = BLACK;return std::make_pair(iterator(root), true);}Node* cur = root;Node* parent = nullptr;KeyofT returnKey;while (cur){if (returnKey(p) < returnKey(cur->data)){parent = cur;cur = cur->left;}else if (returnKey(p) > returnKey(cur->data)){parent = cur;cur = cur->right;}else{return std::make_pair(iterator(cur), false);}}cur = new Node(p);Node* newnode = cur;if (returnKey(p) < returnKey(parent->data)){parent->left = cur;cur->parent = parent;}else{parent->right = cur;cur->parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->parent;if (parent == grandfather->left){Node* uncle = grandfather->right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->parent;}else{if (cur == parent->left){RotationR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}else{RotationL(parent);RotationR(grandfather);grandfather->_col = RED;cur->_col = BLACK;break;}}}else{Node* uncle = grandfather->left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->parent;}else{if (cur == parent->right){RotationL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}else{RotationR(parent);RotationL(grandfather);grandfather->_col = RED;cur->_col = BLACK;break;}}}}root->_col = BLACK;return std::make_pair(iterator(newnode), true);}

那么對于上層封裝紅黑樹的map類來說，那么直接復用底層實現好的insert函數即可

std::pair<iterator, bool> insert(const std::pair<const key, val>& p)
{return tree.insert(p);
}

但是對于set來說，那么這里會有一個小坑，因為這里set類將iterator和const_iterator都設置為了RBTree的const_iterator的類型的別名，那么這里上層的set的insert函數的返回值，第一個元素的聲明雖然是iterator類型，但事實上其是一個const_iterator類型，而這里底層調用紅黑樹的insert函數的時候，那么其返回的是RBTree_iterator<T,T*,T&>類型，那么這里返回到上層的set的insert函數中的時候，在由set中的insert函數再返回到外部的函數調用處，由于這里set的insert函數要返回的元組中的第一個元素的類型是一個RBTree_iterator<T,const T *,const T&>

那么這里底層的insert函數返回RBtree_iterator<T,T*,T&>是無法轉化為RBTree_iterator<T,const T *,const T&>，所以這里編譯器會報一個類型轉化的錯誤

那么要解決這個問題，那么我們就只能利用隱式類型轉化，也就是將非const版本的迭代器類型轉化為const版本的迭代器類型，那么要實現隱式類型轉化，我們就得在RBTree-iterator模板類中定義一個接收非const版本迭代器的單參數的構造函數

所以這里我在RBTree_iterator中將非const版本的迭代器typedef為了iterator：

template<typename T,typename ptr,typename ref>
class RBTree_iteratro{private:
typedef RBTreeNode<T> Node;
typedef RBTree_iterator<T, ptr, ref> self;
typedef RBTree_iterator<T, T*, T&> iterator;
Node* _Node;.......................................................................
};

然后這里在編寫一個接收非const版本的迭代器的構造函數：

	RBTree_iterator(const iterator& p):_Node(p._Node){}

但是這里還沒有結束，那么編寫完該構造函數的時候，事實上，你去實際運行，發現編譯還是無法通過，原因就是這里const版本的迭代器和非const版本的迭代器，雖然他們都是來自同一個模板類，但是一旦實例化之后，實例化生成的const版本的迭代器的類和非const版本的迭代器的類是屬于兩個不同的類，而這里的_Node成員變量是私有的，所以會報一個無法訪問另一個類的私有的成員變量的編譯錯誤

所以這里就需要我們定義一個共有的getNode接口，那么該接口就是返回當前迭代器中封裝的指向紅黑樹節點的指針，那么該接口后面要被const修飾，因為這里構造函數接收的參數前面是被const修飾了，這里我們在構造函數內部調用該接口來初始化當前迭代器的成員變量

RBTree_iterator(const iterator& p):_Node(p.getNode())
{}
Node* getNode() const
{return _Node;
}

那么該構造函數如果當前是一個const版本的迭代器，并且其接收的是一個const版本的迭代器對象，那么此時就會變成拷貝構造函數，而如果接收到是非const版本的迭代器對象，那么其就是構造函數，那么這樣set就可以直接復用底層的insert函數了

std::pair<iterator, bool> insert(const key& p)
{return tree.insert(p);
}

begin/end函數

那么這里map和set的底層的begin和end函數都是復用底層紅黑樹實現的begin和end函數，這里就注意底層紅黑樹的begin和end函數的實現，那么begin函數則是首先遍歷紅黑樹的左子樹，得到紅黑樹的左子樹最左側的節點，然后返回指向給節點的迭代器，而end函數則是返回指向空節點的迭代器即可，注意begin和end都要提供const版本和非const版本

template<typename key,typename T,typename keyofT>
class RBTree
{public:  
const_iterator begin() const
{if (root == nullptr){return end();}Node* cur = root;while (cur->left){cur = cur->left;}return const_iterator(cur);
}
iterator end()
{return iterator(nullptr);
}
const_iterator end() const
{return const_iterator(nullptr);
}........................
};

上層：

	iterator begin(){return tree.begin();}const_iterator begin() const{return tree.begin();}iterator end(){return tree.end();}

那么這里我們實現begin函數則是直接遍歷得到紅黑樹左子樹的最左側節點，而實際上庫的實現和這里有所不同，那么對于庫來說，那么整棵樹的根節點的指向父節點的指針不是指向nullptr，而是指向一個哨兵為節點header，庫的底層實現的紅黑樹，是維護一個帶有哨兵位節點的紅黑樹，那么這里的哨兵位節點的父節點指針則是指向整棵樹的根節點

而哨兵位節點的左指針則是指向紅黑樹的左子樹的最左側的節點，而右指針則是指向紅黑樹的右子樹的最右側的節點，那么這里實現begin的時候，由于有哨兵位節點header的存在，那么直接解引用header的左指針即可得到左子樹的最左側節點，那么不用往下遍歷，那么這樣看似提高了效率，但是對于帶有哨兵節點的紅黑樹來說，那么其插入和刪除的實現就變得復雜，因為這里插入和刪除會涉及到旋轉，那么旋轉玩之后，還要將旋轉后的左子樹的最左側節點以及最右側節點與哨兵節點header連接，那么可以采取庫的實現方式，那么也可以采取我這種，直接遍歷得到begin要指向的左子樹的最左節點

find函數

對于map和set的find函數還是復用紅黑樹底層的find函數，其中紅黑樹底層的find函數則是會接收一個鍵，然后利用二叉搜索樹左小右大的性質，來遍歷二叉樹，看是否有該鍵值的節點存在，如果找到，就返回指向該節點的迭代器，如果沒找到就返回end()，其中find函數也支持const版本和非const版本

iterator find(const key& k)
{KeyofT returnKey;Node* cur = root;while (cur){if (k < returnKey(cur->data)){cur = cur->left;}else if (k > returnKey(cur->data)){cur = cur->right;}else{return iterator(cur);}}return end();
}
const_iterator find(const key& k) const
{KeyofT returnKey;Node* cur = root;while (cur){if (k < returnKey(cur->data)){cur = cur->left;}else if (k > returnKey(cur->data)){cur = cur->right;}else{return const_iterator(cur);}}return end();
}

那么對于上層來說，直接復用即可


iterator find(const key& k)
{return tree.find(k);
}
const_iterator find(const key& k) const
{return tree.find(k);
}

[]運算符重載函數

那么對于map來說，這里還需要額外定義一個[]運算符重載函數，因為這里map支持用[]訪問紅黑樹中特定鍵值的節點，并且可以修改其key對應的值，那么這里[]運算符重載函數的返回值就是指向元組的第二個元素的引用，那么其實現原理，就是利用insert函數的特性

因為[]運算符重載函數的行為就是如果該鍵存在，那么可以修改該鍵對應的值，如果不存在，相當于新插入了該鍵對應的節點，只不過其對應的值設置為默認值，這個行為正符合insert函數的特性，因為insert函數如果發現紅黑樹中已經有該鍵的節點存在，那么會返回一個元組，其中元組的first就是指向已存在節點的迭代器，不存在就插入，并且返回一個元組，其中元組的first就是指向新插入節點的迭代器

val& operator[](const key& k)
{auto p = tree.insert(std::make_pair(k, val()));return p.first->second;
}

源碼

myset.h:

#pragma once
#include"RBTree.h"namespace wz
{template<typename key>class set{private:class KeyofSetT{public:const key& operator()(const key& p){return p;}};my_std::RBTree<key, key, KeyofSetT> tree;public:typedef typename my_std::RBTree<key, key, KeyofSetT>::const_iterator iterator;typedef typename my_std::RBTree<key, key, KeyofSetT>::const_iterator const_iterator;std::pair<iterator, bool> insert(const key& p){return tree.insert(p);}iterator find(const key& k){return iterator(tree.find(k));}const_iterator find(const key& k) const{return tree.find(k);}const_iterator begin() const{return tree.begin();}const_iterator end() const{return tree.end();}};
}

mymap.h:

#pragma once
#include"RBTree.h"namespace wz
{template<typename key, typename val>class map{private:class KeyofMapT{public:const key& operator()(const std::pair<const key, val>& p){return p.first;}};my_std::RBTree<key, std::pair<const key, val>, KeyofMapT> tree;public:typedef typename my_std::RBTree<key, std::pair<const key, val>, KeyofMapT>::iterator iterator;typedef typename my_std::RBTree<key, std::pair<const key, val>, KeyofMapT>::const_iterator const_iterator;std::pair<iterator, bool> insert(const std::pair<const key, val>& p){return tree.insert(p);}iterator find(const key& k){return tree.find(k);}const_iterator find(const key& k) const{return tree.find(k);}iterator begin(){return tree.begin();}const_iterator begin() const{return tree.begin();}iterator end(){return tree.end();}const_iterator end() const{return tree.end();}val& operator[](const key& k){auto p = tree.insert(std::make_pair(k, val()));return p.first->second;}};
}

RBTree.h

#pragma once
namespace my_std {enum  color{BLACK,RED};template<typename T>class RBTreeNode{public:RBTreeNode<T>* left;RBTreeNode<T>* right;RBTreeNode<T>* parent;T  data;color _col;RBTreeNode():_col(RED), left(nullptr), right(nullptr), parent(nullptr), data(T()){}RBTreeNode(const T& p):_col(RED), left(nullptr), right(nullptr), parent(nullptr), data(p){}};template<typename T, typename ptr, typename ref>class  RBTree_iterator{private:typedef RBTreeNode<T> Node;typedef RBTree_iterator<T, ptr, ref> self;typedef RBTree_iterator<T, T*, T&> iterator;Node* _Node;public:RBTree_iterator():_Node(nullptr){}RBTree_iterator(Node* ptr):_Node(ptr){}RBTree_iterator(const iterator& p):_Node(p.getNode()){}Node* getNode() const{return _Node;}ref operator*(){return _Node->data;}ref operator*() const{return _Node->data;}ptr operator->(){return &_Node->data;}ptr operator->() const{return &_Node->data;}self& operator++(){if (_Node == nullptr){return *this;}if (_Node->right){Node* cur = _Node->right;while (cur->left){cur = cur->left;}_Node = cur;}else{Node* cur = _Node;Node* parent = cur->parent;while (parent && cur == parent->right){cur = parent;parent = cur->parent;}_Node = parent;}return *this;}self& operator--(){if (_Node == nullptr){return *this;}if (_Node->left){Node* cur = _Node->left;while (cur->right){cur = cur->right;}_Node = cur;}else{Node* cur = _Node;Node* parent = cur->parent;while (parent && cur == parent->left){cur = parent;parent = cur->parent;}_Node = parent;}return *this;}bool operator==(const self& it) const{return _Node == it._Node;}bool operator!= (const self& it) const{return _Node != it._Node;}};template<typename key, typename T, typename KeyofT>class RBTree{private:typedef RBTreeNode<T> Node;Node* root;void RotationL(Node* parent){Node* cur = parent->right;Node* curleft = cur->left;Node* pparent = parent->parent;parent->parent = cur;parent->right = curleft;cur->parent = pparent;cur->left = parent;if (curleft)curleft->parent = parent;if (pparent){if (pparent->left == parent){pparent->left = cur;}else{pparent->right = cur;}}else{root = cur;}}void RotationR(Node* parent){Node* cur = parent->left;Node* curright = cur->right;Node* pparent = parent->parent;parent->parent = cur;parent->left = curright;cur->right = parent;if (curright)curright->parent = parent;cur->parent = pparent;if (pparent){if (pparent->left == parent){pparent->left = cur;}else{pparent->right = cur;}}else{root = cur;}}void copy(Node*& parent1, Node* const& parent2){if (parent2 == nullptr){parent1 = nullptr;return;}parent1 = new Node(parent2->data);parent1->_col = parent2->_col;copy(parent1->left, parent2->left);copy(parent1->right, parent2->right);if (parent1->left){parent1->left->parent = parent1;}if (parent1->right){parent1->right->parent = parent1;}}void destroyTree(Node* parent){if (parent == nullptr){return;}destroyTree(parent->left);destroyTree(parent->right);delete parent;}bool checkBlacknum(Node* parent, int num, int basic){if (parent == nullptr){if (num != basic){return false;}return true;}if (parent->_col == BLACK){num++;}return checkBlacknum(parent->left, num, basic) && checkBlacknum(parent->right, num, basic);}bool checkRed(Node* parent){if (parent == nullptr){return true;}if (parent == root && parent->_col != BLACK){return false;}if (parent->_col == RED && parent->parent->_col == RED){return false;}return checkRed(parent->left) && checkRed(parent->right);}bool isbalanced(Node* parent){if (parent == nullptr){return true;}if (parent == root && parent->_col != BLACK){return false;}int basic = 0;Node* cur = parent;while (cur){if (cur->_col == BLACK){basic++;}cur = cur->left;}if (checkBlacknum(parent, 0, basic) == false){return false;}if (checkRed(parent) == false){return false;}return isbalanced(parent->left) && isbalanced(parent->right);}public:typedef RBTree_iterator<T, T*, T&> iterator;typedef RBTree_iterator<T, const T*, const T&> const_iterator;RBTree():root(nullptr){}RBTree(const T& p):root(new Node(p)){root->_col = BLACK;}RBTree(const RBTree<key, T, KeyofT>& p){copy(root, p.root);}~RBTree(){destroyTree(root);}std::pair<iterator, bool> insert(const T& p){if (root == nullptr){root = new Node(p);root->_col = BLACK;return std::make_pair(iterator(root), true);}Node* cur = root;Node* parent = nullptr;KeyofT returnKey;while (cur){if (returnKey(p) < returnKey(cur->data)){parent = cur;cur = cur->left;}else if (returnKey(p) > returnKey(cur->data)){parent = cur;cur = cur->right;}else{return std::make_pair(iterator(cur), false);}}cur = new Node(p);Node* newnode = cur;if (returnKey(p) < returnKey(parent->data)){parent->left = cur;cur->parent = parent;}else{parent->right = cur;cur->parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->parent;if (parent == grandfather->left){Node* uncle = grandfather->right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->parent;}else{if (cur == parent->left){RotationR(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}else{RotationL(parent);RotationR(grandfather);grandfather->_col = RED;cur->_col = BLACK;break;}}}else{Node* uncle = grandfather->left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->parent;}else{if (cur == parent->right){RotationL(grandfather);grandfather->_col = RED;parent->_col = BLACK;break;}else{RotationR(parent);RotationL(grandfather);grandfather->_col = RED;cur->_col = BLACK;break;}}}}root->_col = BLACK;return std::make_pair(iterator(newnode), true);}iterator begin(){if (root == nullptr){return end();}Node* cur = root;while (cur->left){cur = cur->left;}return iterator(cur);}const_iterator begin() const{if (root == nullptr){return end();}Node* cur = root;while (cur->left){cur = cur->left;}return const_iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator end() const{return const_iterator(nullptr);}iterator find(const key& k){KeyofT returnKey;Node* cur = root;while (cur){if (k < returnKey(cur->data)){cur = cur->left;}else if (k > returnKey(cur->data)){cur = cur->right;}else{return iterator(cur);}}return end();}const_iterator find(const key& k) const{KeyofT returnKey;Node* cur = root;while (cur){if (k < returnKey(cur->data)){cur = cur->left;}else if (k > returnKey(cur->data)){cur = cur->right;}else{return const_iterator(cur);}}return end();}bool Isbalanced(){return isbalanced(root);}};
}

main.cpp:

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include "mymap.h"
#include "myset.h"
void test_map() {std::cout << "===== Testing map =====" << std::endl;wz::map<std::string, int> wordCount;// 測試空mapassert(wordCount.begin() == wordCount.end());std::cout << "Empty map test passed." << std::endl;// 測試插入auto result1 = wordCount.insert(std::make_pair("apple", 5));assert(result1.second == true); // 插入成功assert(result1.first != wordCount.end());auto result2 = wordCount.insert(std::make_pair("banana", 3));assert(result2.second == true);auto result3 = wordCount.insert(std::make_pair("apple", 10)); // 重復插入assert(result3.second == false); // 插入失敗assert(result3.first->second == 5); // 值未改變std::cout << "Insert test passed." << std::endl;// 測試遍歷和順序std::vector<std::string> keys;for (auto it = wordCount.begin(); it != wordCount.end(); ++it) {keys.push_back(it->first);}assert(keys.size() == 2);assert(keys[0] == "apple");assert(keys[1] == "banana");std::cout << "Traversal test passed." << std::endl;// 測試operator[]wordCount["orange"] = 8; // 新鍵wordCount["apple"] = 7;assert(wordCount["apple"] == 7);assert(wordCount["banana"] == 3);assert(wordCount["orange"] == 8);assert(wordCount["grape"] == 0); // 自動創建std::cout << "Operator[] test passed." << std::endl;// 測試查找auto it1 = wordCount.find("apple");assert(it1 != wordCount.end());assert(it1->second == 7);auto it2 = wordCount.find("mango");assert(it2 == wordCount.end());std::cout << "Find test passed." << std::endl;// 測試const mapconst auto& constMap = wordCount;auto cit = constMap.find("banana");assert(cit != constMap.end());assert(cit->second == 3);// 測試const迭代器遍歷int count = 0;for (auto it = constMap.begin(); it != constMap.end(); ++it) {count++;}assert(count == 4); // apple, banana, orange, grapestd::cout << "Const map test passed." << std::endl;// 測試大量數據wz::map<int, std::string> numberMap;for (int i = 0; i < 1000; i++) {numberMap[i] = "Number " + std::to_string(i);}// 驗證順序int prev = -1;for (const auto& kv : numberMap) {assert(kv.first > prev);prev = kv.first;}assert(prev == 999);std::cout << "Large data test passed." << std::endl;std::cout << "All map tests passed!\n" << std::endl;}
void test_set() {std::cout << "===== Testing set =====" << std::endl;wz::set<int> numbers;// 測試空setassert(numbers.begin() == numbers.end());std::cout << "Empty set test passed." << std::endl;// 測試插入auto result1 = numbers.insert(5);assert(result1.second == true);auto result2 = numbers.insert(10);assert(result2.second == true);auto result3 = numbers.insert(5); // 重復插入assert(result3.second == false);std::cout << "Insert test passed." << std::endl;// 測試遍歷和順序std::vector<int> values;for (auto it = numbers.begin(); it != numbers.end(); ++it) {values.push_back(*it);}assert(values.size() == 2);assert(values[0] == 5);assert(values[1] == 10);std::cout << "Traversal test passed." << std::endl;// 測試查找auto it1 = numbers.find(5);assert(it1 != numbers.end());assert(*it1 == 5);auto it2 = numbers.find(15);assert(it2 == numbers.end());std::cout << "Find test passed." << std::endl;// 測試const setconst auto& constSet = numbers;auto cit = constSet.find(10);assert(cit != constSet.end());assert(*cit == 10);// 測試const迭代器遍歷int count = 0;for (auto it = constSet.begin(); it != constSet.end(); ++it) {count++;}assert(count == 2);std::cout << "Const set test passed." << std::endl;// 測試大量數據wz::set<int> largeSet;for (int i = 0; i < 1000; i++) {largeSet.insert(i);}// 驗證順序int prev = -1;for (int num : largeSet) {assert(num > prev);prev = num;}assert(prev == 999);// 驗證所有值都存在for (int i = 0; i < 1000; i++) {assert(largeSet.find(i) != largeSet.end());}assert(largeSet.find(1000) == largeSet.end());std::cout << "Large data test passed." << std::endl;std::cout << "All set tests passed!\n" << std::endl;
}void test_edge_cases() {std::cout << "===== Testing edge cases =====" << std::endl;// 測試空容器的迭代器wz::map<std::string, int> emptyMap;for (auto it = emptyMap.begin(); it != emptyMap.end(); ++it) {assert(false); // 不應該執行到這里}wz::set<int> emptySet;for (auto it = emptySet.begin(); it != emptySet.end(); ++it) {assert(false); // 不應該執行到這里}std::cout << "Empty container iteration test passed." << std::endl;// 測試字符串鍵wz::map<std::string, std::string> stringMap;stringMap["hello"] = "world";stringMap["foo"] = "bar";stringMap["abc"] = "def";std::vector<std::string> keys;for (const auto& kv : stringMap) {keys.push_back(kv.first);}assert(keys.size() == 3);assert(keys[0] == "abc");assert(keys[1] == "foo");assert(keys[2] == "hello");std::cout << "String key test passed." << std::endl;}
int main() {test_map();test_set();test_edge_cases();std::cout << "All tests passed!" << std::endl;return 0;
}