Independent Dog

My EDA life record

STL Map

2017-09-08
C++

在C++基本函式庫中實作紅黑樹(Red Black Tree)和雜湊(Hash)的資料結構分別是
map 和 unordered_map 兩個資料結構在使用上基本上沒有什麼區別，不同的部分只有map 的紅勒樹是可以用iterator尋訪，以及搜尋時間是O(log N) 而unordered_map則不能尋訪但其搜尋時間是
O(1)。

以下就列出建構方式以及常用的物件函式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
///////////////////////////////////
//©NCHU VLSICAD LAB。版權所有
//Author: 鄭景鴻
///////////////////////////////////
#include <iostream>
#include <map>
#include <unordered_map>// c++11後才支援此head file
using namespace std;
class Block
{
public:
	Block(int x, int y):x(x),y(y){};
	Block(){};
	~Block(){};
	int getX(){return x;};
	int getY(){return y;};
private:
	int x,y;
};
int main()
{
	map<int, Block>  t1;//創建一個 key是int,data是Blcok的資料結構。
	map<int, Block*> t2;//創建一個 key是int,data是Blcok*的資料結構。
	
	// 插入
	// Class 一定要有() constructer 應為map的call by value是產生一個空白的物件
	// 並將原本的值assignment到裡面去。
	t1[ 1 ] = Block (3,5);
	t1[ 2 ] = Block (4,6);
	t2[ 1 ] = new Block(3,5);
	//查找
	t1.find(1); // 回傳 key 為 1 的參照要指定尋找的部分是key 還是data
	t1.find(1)->first;// 回傳 key 為 1 之ket參照位置且須注意key為const不得修改變動
	t1.find(1)->second;// 回傳 key 為 1 之data參照位置
	t1.count(1);	//回傳 key 1 之大小(不為0即為存在)
	t1.at(1);	//回傳 key 為 1 之data參照
	//刪除及一些拉哩拉紮的東西
	t1.erase(1);			// 用 key 刪除
	t1.erase(t1.find(2));	// 用參照刪除
	t1.size(); // 回傳t1大小
	return 0;
}

Reference
Map
Unordered_Map

⬅️ Go back