天天看點

c++/c常用數組結構和哈希結構定義vector定義方法哈希初始化undered_map C++ 用法舉例undered_map 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,輸出的結果為:

c++/c常用數組結構和哈希結構定義vector定義方法哈希初始化undered_map C++ 用法舉例undered_map C 用法舉例

若把unordered_map換成map,輸出的結果為:

c++/c常用數組結構和哈希結構定義vector定義方法哈希初始化undered_map C++ 用法舉例undered_map C 用法舉例

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;
}
           

繼續閱讀