c++/c常用數組結構和哈希結構定義

c++常用數組結構和哈希結構定義

• vector定義方法
• 哈希初始化
• • 代碼舉例
  • map與unordered_map差別
  • • 需要引入的頭檔案不同
    • 内部實作機理不同
    • 優缺點以及适用處
• undered_map C++ 用法舉例
• undered_map C 用法舉例

vector定義方法

定義初始化9行9列，值為0的3個二維數組

vector<vector<int>> row (9, vector<int>(9,0));
        vector<vector<int>> col (9, vector<int>(9,0));
        vector<vector<int>> box (9, vector<int>(9,0));
           

哈希初始化

代碼舉例

#include <iostream>  
#include <unordered_map>  
#include <map>
#include <string>  
using namespace std;  
int main()  
{  
	//注意：C++11才開始支援括号初始化
    unordered_map<int, string> myMap={{ 5, "張大" },{ 6, "李五" }};//使用{}指派
    myMap[2] = "李四";  //使用[ ]進行單個插入，若已存在鍵值2，則指派修改，若無則插入。
    myMap.insert(pair<int, string>(3, "陳二"));//使用insert和pair插入
  
	//周遊輸出+疊代器的使用
    auto iter = myMap.begin();//auto自動識别為疊代器類型unordered_map<int,string>::iterator
    while (iter!= myMap.end())
    {  
        cout << iter->first << "," << iter->second << endl;  
        ++iter;  
    }  
	
	//查找元素并輸出+疊代器的使用
    auto iterator = myMap.find(2);//find()傳回一個指向2的疊代器
    if (iterator != myMap.end())
	    cout << endl<< iterator->first << "," << iterator->second << endl;  
    system("pause");  
    return 0;  
} 
           

此時用的是unordered_map，輸出的結果為：

若把unordered_map換成map，輸出的結果為：

map與unordered_map差別

需要引入的頭檔案不同

map: #include < map >

unordered_map: #include < unordered_map >

·

内部實作機理不同

map： map内部實作了一個紅黑樹（紅黑樹是非嚴格平衡二叉搜尋樹，而AVL是嚴格平衡二叉搜尋樹），紅黑樹具有自動排序的功能，是以map内部的所有元素都是有序的，紅黑樹的每一個節點都代表着map的一個元素。是以，對于map進行的查找，删除，添加等一系列的操作都相當于是對紅黑樹進行的操作。map中的元素是按照二叉搜尋樹（又名二叉查找樹、二叉排序樹，特點就是左子樹上所有節點的鍵值都小于根節點的鍵值，右子樹所有節點的鍵值都大于根節點的鍵值）存儲的，使用中序周遊可将鍵值按照從小到大周遊出來。

unordered_map: unordered_map内部實作了一個哈希表（也叫散清單，通過把關鍵碼值映射到Hash表中一個位置來通路記錄，查找的時間複雜度可達到O(1)，其在海量資料進行中有着廣泛應用）。是以，其元素的排列順序是無序的。哈希表詳細介紹

優缺點以及适用處

map：

優點：

有序性，這是map結構最大的優點，其元素的有序性在很多應用中都會簡化很多的操作

紅黑樹，内部實作一個紅黑書使得map的很多操作在lgn的時間複雜度下就可以實作，是以效率非常的高

缺點： 空間占用率高，因為map内部實作了紅黑樹，雖然提高了運作效率，但是因為每一個節點都需要額外儲存父節點、孩子節點和紅/黑性質，使得每一個節點都占用大量的空間

适用處：對于那些有順序要求的問題，用map會更高效一些

unordered_map：

優點： 因為内部實作了哈希表，是以其查找速度非常的快

缺點： 哈希表的建立比較耗費時間

适用處：對于查找問題，unordered_map會更加高效一些，是以遇到查找問題，常會考慮一下用unordered_map

總結：

記憶體占有率的問題就轉化成紅黑樹 VS hash表 , 還是unorder_map占用的記憶體要高。

但是unordered_map執行效率要比map高很多

對于unordered_map或unordered_set容器，其周遊順序與建立該容器時輸入的順序不一定相同，因為周遊是按照哈希表從前往後依次周遊的

map和unordered_map的使用

unordered_map的用法和map是一樣的，提供了 insert，size，count等操作，并且裡面的元素也是以pair類型來存貯的。其底層實作是完全不同的，上方已經解釋了，但是就外部使用來說卻是一緻的。

undered_map C++ 用法舉例

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashmap;
        for (int it : nums) {
            hashmap[it]++;
        }
        for (auto [num, count] : hashmap) {
            if (count == 1) {
                return num;
            }
        }
        return 0;
    }
};
           

undered_map C 用法舉例

struct HashTable {
    int key, val;
    UT_hash_handle hh;
};

int singleNumber(int *nums, int numsSize) {
    struct HashTable *hashTable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct HashTable *tmp;
        HASH_FIND_INT(hashTable, &nums[i], tmp);
        if (tmp == NULL) {
            tmp = malloc(sizeof(struct HashTable));
            tmp->key = nums[i];
            tmp->val = 1;
            HASH_ADD_INT(hashTable, key, tmp);
        } else {
            tmp->val++;
        }
    }
    int ans = 0;
    struct HashTable *iter, *tmp;
    HASH_ITER(hh, hashTable, iter, tmp) {
        if (iter->val == 1) {
            ans = iter->key;
            break;
        }
    }
    return ans;
}