STL容器之unordered

文章目录

STL容器之unordered_map类
- 1、unordered_map
- - 1.1、unordered_map介绍
  - 1.2、unordered_map的使用
  - - 1.2.1、unordered_map的常见构造
    - 1.2.2、unordered_map的迭代器
    - 1.2.3、unordered_map的容量
    - 1.2.4、unordered_map的增删查
    - 1.2.5、unordered_map的桶操作
- 2、unordered_multimap
- 3、unordered_map的底层结构
- 4、unordered_set的模拟实现
- - 4.1、改造哈希表（链表法）
  - 4.2、MyUnordered_Map类的构成

STL容器之unordered_map类

1、unordered_map

1.1、unordered_map介绍

unordered_map的文档介绍

unordered_map是以不特定顺序存储独特元素的容器，并允许根据其值快速检索单个元素。

在unordered_map中，键值通常用于唯一标识元素，而映射值是具有与此键关联内容的对象(pair<K,V>)。键是不可变的。键和映射值的类型可能不同。

在内部，unordered_map中的元素没有按任何特定顺序排序，而是根据其哈希值组织成桶，以便通过其值直接快速访问单个元素（平均时间复杂度恒定）。

unordered_map容器比map容器更快地通过其键访问单个元素，但是它通常在遍历元素子集的范围迭代方面效率较低。

unordered_map实现了直接访问运算符（运算符[]），它允许使用其键值作为参数直接访问映射值。

容器中的迭代器至少是前向iterators。

1.2、unordered_map的使用

1.2.1、unordered_map的常见构造

(constructor )函数名称接口说明
unordered_map ( size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() ) 构造空的unordered_map
unordered_map ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() ) 用[first,last)迭代区间构造unordered_map
unordered_map ( const unordered_map& ump ) unordered_map的拷贝构造
void test_um1() {
     unordered_map<int, int> um;
     int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};

     for (auto e: a) {
           um.insert(make_pair(e, e));
     }
     for (auto e: um) {
           cout << e.first << ":" << e.second << endl;
     }
     cout << "=======================" << endl;
 
    unordered_map<int, int> um1(um.begin(), um.end());
     for (auto e: um1) {
         cout << e.first << ":" << e.second << endl;
       }
     cout << "=======================" << endl;
 
     unordered_map<int, int> um2(um1);
    for (auto e: um2) {
         cout << e.first << ":" << e.second << endl;
     }
   
 }

(constructor )函数名称	接口说明
unordered_map ( size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() )	构造空的unordered_map
unordered_map ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() )	用[first,last)迭代区间构造unordered_map
unordered_map ( const unordered_map& ump )	unordered_map的拷贝构造

1.2.2、unordered_map的迭代器

函数名称	接口说明
begin()+end()	获取第一个元素位置的iterator和获取最后一个元素的后一个位置的iterator
cbegin()+cend()	获取第一个元素位置的const_iterator和获取最后一个元素的后一个位置的const_iterator

void test_um2() {
     unordered_map<int, int> um;
     int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};
     for (auto e: a) {
           um.insert(make_pair(e, e));
     }
     unordered_map<int, int>::iterator it = um.begin();
     while (it != um.end()) {
           cout << it->first << ":" << it->second << endl;
           ++it;
     }
 
    cout << "=======================" << endl;
 
    unordered_map<int, int>::const_iterator cit = um.cbegin();
 
     while (cit != um.cend()) {
           cout << cit->first << ":" << cit->second << endl;
           ++cit;
     }
 }

1.2.3、unordered_map的容量

函数名称	接口说明
empty	判断当前unordered_map是否为空
size	获取unordered_map的元素个数

void test_um3() {
   unordered_map<int, int> um;
   int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};
   for (auto e: a) {
          um.insert(make_pair(e, e));
   }
   cout << um.empty() << endl;
   cout << um.size() << endl;

   um.clear();
   cout << um.empty() << endl;
   cout << um.size() << endl;
}

1.2.4、unordered_map的增删查

函数名称	接口说明
insert	在unordered_map中插入pair<key,value>键值对，如果插入成功，返回<key插入位置,true>，插入失败说明unordered_map中已经有key，返回<key在unordered_map的位置,false>
erase	删除unordered_map中pos位置的元素，或者删除值为val的元素
swap	交换两个unordered_map的元素
clear	将unordered_map的元素置空
find	返回unordered_map中值为x的元素位置
count	返回unordered_map中值为x的元素个数
operator[]	访问key元素的映射值value，如果key不存在，则插入pair<key,V()>并返回V();如果key存在，则返回对应的value

void test_um4() {
    unordered_map<int, int> um;
    int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};
    for (auto e: a) {
          um.insert(make_pair(e, e));
    }
    for (auto e: um) {
          cout << e.first << ":" << e.second << endl;
    }
    cout << "========================" << endl;
    um.erase(1);
    um.erase(2);

    auto pos = um.find(11);
    um.erase(pos);
    for (auto e: um) {
        cout << e.first << ":" << e.second << endl;
      }
    cout << "========================" << endl;

    unordered_map<int, int> um1;
    um1.insert(make_pair(100, 100));
    um1.swap(um);
    cout << "um:";
    for (auto e: um) {
        cout << e.first << ":" << e.second << endl;
    }
  
    cout << "um1:";
    for (auto e: um1) {
        cout << e.first << ":" << e.second << endl;
    }

      cout << "========================" << endl;

    cout << um1.count(5) << endl;
    cout << um1.count(1) << endl;
    cout << "========================" << endl;

    um1.clear();
    cout << "um:";
    for (auto e: um) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << "um1:";
    for (auto e: um1) {
          cout << e.first << ":" << e.second << endl;
    }

}

1.2.5、unordered_map的桶操作

函数名称	接口说明
bucket_count	返回unordered_map中的桶的个数
bucket_size	返回第n个桶中元素的个数
bucket	返回元素k在哪个桶

void test_um5() {
    unordered_map<int, int> um;
    int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};
    for (auto e: a) {
        um.insert(make_pair(e, e));
    }

    cout << um.bucket_count() << endl;
    cout << um.bucket_size(1) << endl;
    cout << um.bucket(11) << endl;
}

2、unordered_multimap

这个其实就和map和multimap一样，就是比unordered_map多了一个可以存重复值的特性。

演示一下：

void test_umm1() {
       unordered_multimap<int, int> ummp;
       int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};
       for (auto e: a) {
           ummp.insert(make_pair(e, e));
       }

       for (auto e: ummp) {
           cout << e.first << ":" << e.second << endl;
       }
       cout << endl;
}

3、unordered_map的底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

unordered_map和unordered_set一样，底层都是用的哈希表，都是用的链表法。

想了解底层结构可以看STL容器之unordered_set类这篇文章

4、unordered_set的模拟实现

以下我们自己模拟实现的时候，unordered_set的模拟实现我们使用MyUnordered_Set类用于区分，unordered_map的模拟实现我们使用MyUnordered_Map类用于区分。

4.1、改造哈希表（链表法）

结点的结构体需要修改一下，之前我们存的是pair<K,V>，但MyUnordered_Set是存K的，因此我们模版参数设置为一个参数T，MyUnordered_Set调用就是K，MyUnordered_Map调用就是pair<K,V>。

template<class T>
struct HashNode {
 typedef HashNode<T> Node;

 Node *_next;
 T _data;

 HashNode(const T &data) : _data(data), _next(nullptr) {}

};

哈希表需要增加一个模版参数：取Key的仿函数，因为MyUnordered_Set插入的是K，但是MyUnordered_Map插入的是pair<K,V>，我们需要从pair<K,V>中取出K。因此插入也要改成bool Insert(const T &data){}。

这个仿函数分别放在MyUnordered_Set和MyUnordered_Map的类中，用来传给哈希表。

MyUnordered_Set类中：

struct MapKeyOfT {
     K operator()(const pair<K, V> &kv) {
         return kv.first;
     }
};

MyUnordered_Map类中：

struct MapKeyOfT {
     K operator()(const pair<K, V> &kv) {
         return kv.first;
     }
};

因此当前改造后的哈希表为：

template<class T>
struct HashNode {
 typedef HashNode<T> Node;

 Node *_next;
 T _data;

 HashNode(const T &data) : _data(data), _next(nullptr) {}

};

template<class K>
struct HashFunc {
 size_t operator()(const K &key) {
     return (size_t) key;
 }
};

template<>
struct HashFunc<string> {
 size_t operator()(const string &str) {
     size_t hash = 0;
     for (auto e: str) {
         hash += e;
         e *= 131;
     }
     return hash;
 }
};

template<class K, class T, class KeyOfT, class Hash>
class HashTable {
 typedef HashNode<T> Node;
public:

 ~HashTable() {
     for (int i = 0; i < _tables.size(); ++i) {
         _tables[i] = nullptr;
     }
 }

 HashTable(size_t size = 10) {
     _tables.resize(size, nullptr);// 各结点初始化为空
 }

 Node* Find(const K &key) {
     Hash hs;
     KeyOfT kot;
     // 先算出映射到哪里
     int hashi = hs(key) % _tables.size();
     Node *cur = _tables[hashi];
     while (cur) {
         if (kot(cur->_data) == key) {
             return cur;
         }
         cur = cur->_next;
     }
     return nullptr; // 没找到
 }

 bool Erase(const K &key) {
     Hash hs;
     KeyOfT kot;
     iterator ret = Find(key);
     if (ret != end()) {
         int hashi = hs(key) % _tables.size();
         Node *cur = _tables[hashi];
         Node *prev = nullptr;
         while (cur) {
             if (kot(cur->_data) == key) {
                 if (prev == nullptr)
                     _tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中
                 else
                     prev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个

                 delete cur; // 删除该结点并退出循环
                 break;
             }
             prev = cur;
             cur = cur->_next;
         }
         --_n;
         return true;
     } else {
         return false;
     }
 }

 bool Insert(const T &data) {

     Hash hs;
     KeyOfT kot;
     if (Find(kot(data)))
         return false;// 找到了
     if (_n == _tables.size()) {
         // 扩容
         vector<Node *> newTables;
         newTables.resize(2 * _tables.size(), nullptr);
         for (int i = 0; i < _tables.size(); ++i) {
             Node *cur = _tables[i];
             while (cur) {
                 Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点
                 // 映射到新表位置
                 int hashi = hs(kot(cur->_data)) % newTables.size();
                 // 插入到新表位置
                 Node *newcur = newTables[hashi];
                 if (newcur) {
                     // 当前表中的结点不为空，则头插并链接
                     cur->_next = newcur;
                     newTables[hashi] = cur;
                 } else {
                     // 当前表中的结点为空，则新结点直接放到这个表中
                     newTables[hashi] = cur;
                     cur->_next = nullptr;// 新插入的cur的_next不一定是空
                 }
                 cur = next;// 继续往下找
             }
         }
         _tables.swap(newTables);
     }

     // 先算出映射到哪里
     int hashi = hs(kot(data)) % _tables.size();
     Node *cur = _tables[hashi];
     Node *newnode = new Node(data);
     if (cur) {
         // 当前表中的结点不为空，则头插并链接
         newnode->_next = cur;
         _tables[hashi] = newnode;
     } else {
         // 当前表中的结点为空，则新结点直接放到这个表中
         _tables[hashi] = newnode;
     }
     ++_n;
     return true;
 }

private:
 vector<Node *> _tables;
 size_t _n = 0;
};

还需要增加迭代器，用来遍历哈希表。

// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {

 typedef HashNode<T> Node;
 typedef HashTable<K, T, KeyOfT, Hash> HT;
 typedef __HTIterator<K, T, KeyOfT, Hash> Self;

 Node *_node;
 HT *_ht;

 __HTIterator(Node *node, HT *ht) : _node(node), _ht(ht) {}


 T &operator*() {
     return _node->_data;
 }

 T *operator->() {
     return &_node->_data;
 }

 Self &operator++() {
     if (_node->_next) {
         // 当前结点还有后继结点
         _node = _node->_next;
     } else {
         // 当前桶走完了
         KeyOfT kot;
         Hash hs;

         // 先算出当前在哪个哈希桶
         int hashi = hs(kot(_node->_data)) % _ht->_tables.size();
         ++hashi;// 走到下一个桶

         while (hashi < _ht->_tables.size()) {
             if (_ht->_tables[hashi]) {
                 //  这个桶有结点
                 _node = _ht->_tables[hashi];
                 break;
             } else
                 ++hashi;// 这个桶没有有结点
         }

         if (hashi == _ht->_tables.size()) {
             // 走到最后了，没找到下一个位置
             _node = nullptr;
         }

     }
     return *this;
 }

 bool operator!=(const Self &s) {
     return s._node != _node;
 }
};

改造后的哈希表（终极版）：这里的插入的返回值由bool变为了pair<iterator,bool>，和官方保持一致。

template<class T>
struct HashNode {
 typedef HashNode<T> Node;

 Node *_next;
 T _data;

 HashNode(const T &data) : _data(data), _next(nullptr) {}

};

template<class K>
struct HashFunc {
 size_t operator()(const K &key) {
     return (size_t) key;
 }
};

template<>
struct HashFunc<string> {
 size_t operator()(const string &str) {
     size_t hash = 0;
     for (auto e: str) {
         hash += e;
         e *= 131;
     }
     return hash;
 }
};


// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {

 typedef HashNode<T> Node;
 typedef HashTable<K, T, KeyOfT, Hash> HT;
 typedef __HTIterator<K, T, KeyOfT, Hash> Self;

 Node *_node;
 HT *_ht;

 __HTIterator(Node *node, HT *ht) : _node(node), _ht(ht) {}


 T &operator*() {
     return _node->_data;
 }

 T *operator->() {
     return &_node->_data;
 }

 Self &operator++() {
     if (_node->_next) {
         // 当前结点还有后继结点
         _node = _node->_next;
     } else {
         // 当前桶走完了
         KeyOfT kot;
         Hash hs;

         // 先算出当前在哪个哈希桶
         int hashi = hs(kot(_node->_data)) % _ht->_tables.size();
         ++hashi;// 走到下一个桶

         while (hashi < _ht->_tables.size()) {
             if (_ht->_tables[hashi]) {
                 //  这个桶有结点
                 _node = _ht->_tables[hashi];
                 break;
             } else
                 ++hashi;// 这个桶没有有结点
         }

         if (hashi == _ht->_tables.size()) {
             // 走到最后了，没找到下一个位置
             _node = nullptr;
         }

     }
     return *this;
 }

 bool operator!=(const Self &s) {
     return s._node != _node;
 }
};

template<class K, class T, class KeyOfT, class Hash>
class HashTable {
 friend __HTIterator<K, T, KeyOfT, Hash>;// 为了能访问_tables
 typedef HashNode<T> Node;
public:

 typedef __HTIterator<K, T, KeyOfT, Hash> iterator;

 iterator begin() {
     for (int i = 0; i < _tables.size(); ++i) {
         if (_tables[i])
             return iterator(_tables[i], this);// 从左找到第一个哈希桶的第一个结点
     }
     return end();
 }

 iterator end() {
     return iterator(nullptr, this);
 }

 ~HashTable() {
     for (int i = 0; i < _tables.size(); ++i) {
         _tables[i] = nullptr;
     }
 }

 HashTable(size_t size = 10) {
     _tables.resize(size, nullptr);// 各结点初始化为空
 }

 iterator Find(const K &key) {
     Hash hs;
     KeyOfT kot;
     // 先算出映射到哪里
     int hashi = hs(key) % _tables.size();
     Node *cur = _tables[hashi];
     while (cur) {
         if (kot(cur->_data) == key) {
             return iterator(cur, this);
         }
         cur = cur->_next;
     }
     return iterator(nullptr, this); // 没找到
 }

 bool Erase(const K &key) {
     Hash hs;
     KeyOfT kot;
     iterator ret = Find(key);
     if (ret != end()) {
         int hashi = hs(key) % _tables.size();
         Node *cur = _tables[hashi];
         Node *prev = nullptr;
         while (cur) {
             if (kot(cur->_data) == key) {
                 if (prev == nullptr)
                     _tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中
                 else
                     prev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个

                 delete cur; // 删除该结点并退出循环
                 break;
             }
             prev = cur;
             cur = cur->_next;
         }
         --_n;
         return true;
     } else {
         return false;
     }
 }

 pair<iterator, bool> Insert(const T &data) {

     Hash hs;
     KeyOfT kot;
     iterator it = Find(kot(data));
     if (it != end())
         return make_pair(it, false);// 找到了
     if (_n == _tables.size()) {
         // 扩容
         vector<Node *> newTables;
         newTables.resize(2 * _tables.size(), nullptr);
         for (int i = 0; i < _tables.size(); ++i) {
             Node *cur = _tables[i];
             while (cur) {
                 Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点
                 // 映射到新表位置
                 int hashi = hs(kot(cur->_data)) % newTables.size();
                 // 插入到新表位置
                 Node *newcur = newTables[hashi];
                 if (newcur) {
                     // 当前表中的结点不为空，则头插并链接
                     cur->_next = newcur;
                     newTables[hashi] = cur;
                 } else {
                     // 当前表中的结点为空，则新结点直接放到这个表中
                     newTables[hashi] = cur;
                     cur->_next = nullptr;// 新插入的cur的_next不一定是空
                 }
                 cur = next;// 继续往下找
             }
         }
         _tables.swap(newTables);
     }

     // 先算出映射到哪里
     int hashi = hs(kot(data)) % _tables.size();
     Node *cur = _tables[hashi];
     Node *newnode = new Node(data);
     if (cur) {
         // 当前表中的结点不为空，则头插并链接
         newnode->_next = cur;
         _tables[hashi] = newnode;
     } else {
         // 当前表中的结点为空，则新结点直接放到这个表中
         _tables[hashi] = newnode;
     }
     ++_n;
     return make_pair(iterator(_tables[hashi], this), true);
 }

private:
 vector<Node *> _tables;
 size_t _n = 0;
};

4.2、MyUnordered_Map类的构成

其实就是套了一层哈希表，多了一个MapKeyOfT用来传给哈希表的模版参数。

#include "HashTable_Bucket.h"

template<class K, class V, class Hash = HashFunc<K>>
class MyUnordered_Map {
    struct MapKeyOfT {
        K operator()(const pair<K, V> &kv) {
            return kv.first;
        }
    };

public:

    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;

    iterator begin() {
        return _hs.begin();
    }

    iterator end() {
        return _hs.end();
    }

    pair<iterator, bool> insert(const pair<K, V> &kv) {
        return _hs.Insert(kv);
    }

    bool erase(const K &key) {
        return _hs.Erase(key);
    }

    iterator find(const K &key) {
        return _hs.Find(key);
    }

    V &operator[](const K &key) {
        pair<iterator, bool> ret = insert(make_pair(key, V()));
        return ret.first->second;
    }

private:
    HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _hs;
};