unordered_map介绍

unordered_map 是关联容器，含有带唯一键的键(key;it->first)-值(value;it->second) pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序，而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问，因为一旦计算哈希，则它准确指代元素所放进的桶。

Hashtable和bucket

由于unordered_map内部采用的hashtable的数据结构存储，所以，每个特定的key会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable是可能存在冲突的（多个key通过计算映射到同一个位置），在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的（像桶子一样，可以装多个元素）。

在这里插入图片描述

函数使用

1.成员函数(构造函数，赋值运算)

函数功能说明
unordered_map() : unordered_map( size_type(/implementation-defined/) )默认构造函数，构造空容器。
template< class InputIt > unordered_map( InputIt first, InputIt last,size_type bucket_count,const Hash& hash,const Allocator& alloc ) : unordered_map(first, last, bucket_count, hash, key_equal(), alloc) {}列表构造函数，构造拥有范围 [first, last) 的内容的容器。
unordered_map( const unordered_map& other );复制构造函数。
unordered_map( unordered_map&& other );移动构造函数。用移动语义构造拥有 other 内容的容器。
unordered_map( std::initializer_list<value_type> init,size_type bucket_count,const Allocator& alloc ) : unordered_map(init, bucket_count,Hash(), key_equal(), alloc) {}范围构造函数，构造拥有 initializer_list init 内容的容器，同 unordered_map(init.begin(), init.end()) 。参数
unordered_map& operator**=**( const unordered_map& other );复制赋值运算符。以 other 的副本替换内容。
unordered_map& operator**=**( unordered_map&& other );移动赋值运算符。用移动语义以 other 的内容替换内容（即从 other 移动 other 中的数据到此容器中）。
unordered_map& operator**=**( std::initializer_list<value_type> ilist );以 initializer_list ilist 所标识者替换内容。

实现

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    // 默认构造函数：空 unordered_map
    unordered_map<int, string> m1;

    // 列表构造函数
    unordered_map<int, string> m2 = { {1,"This"},{2,"is"} };

    // 复制构造函数
    unordered_map<int, string> m3 = m2;

    // 移动构造函数
    unordered_map<int, string> m4 = move(m3);

    // 范围构造函数
    unordered_map<int, string> m5(m3.begin(), m3.end());


    return 0;
}

在这里插入图片描述

2.迭代器（begin();cbegin();end();cend()）

迭代器功能说明
iterator begin() ;返回指向 unordered_map 首元素的迭代器。若 unordered_map 为空，则返回的迭代器将等于 end() 。
const_iterator cbegin() const ;返回指向 unordered_map 首元素的迭代器。若 unordered_map 为空，则返回的迭代器将等于 end() 。
iterator end() ;返回指向 unordered_map 末元素后一元素的迭代器。此元素表现为占位符；试图访问它导致未定义行为。
const_iterator cend() const;返回指向 unordered_map 末元素后一元素的迭代器。此元素表现为占位符；试图访问它导致未定义行为。
在这里插入图片描述
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"} };
    
    
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first <<"  " <<it->second << endl;
    }


    return 0;
}

在这里插入图片描述

3.容量(empty();size();max_size() 😉

函数功能
bool empty() const ;检查容器是否无元素，即是否 begin() == end() 。
size_type size() const ;返回容器中的元素数，即 std::distance(begin(), end()) 。
size_type max_size() const ;返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end()) 。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"} };
    
    
    cout << "m1.empty():" << m1.empty() << endl;
    cout << "m1.size():" << m1.size() << endl;
    cout << "m1.max_size():" << m1.max_size() << endl;


    return 0;
}

在这里插入图片描述

3.修改器(clear;insert;insert_or_assign;emplace;emplace_hint;try_emplace;erase;swap;extract;merge)

函数功能
void clear() ;从容器擦除所有元素。此调用后 size() 返回零。
std::pair<iterator,bool> insert( const value_type& value );插入 value 。
iterator insert( const_iterator hint, value_type&& value )插入 value ，以 hint 为应当开始搜索的位置的非强制建议。
template< class InputIt >
void insert( InputIt first, InputIt last );插入来自范围 [first, last) 的元素。
void insert( std::initializer_list<value_type> ilist );插入来自 initializer_list ilist 的元素。
template
std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);若等价于 k 的键已存在于容器中，则赋值 std::forward(obj) 给对应于键 k 的 mapped_type 。若键不存在，则如同用 insert 插入从 value_type(k, std::forward(obj)) 构造的新值。
template< class… Args >
std::pair<iterator,bool> emplace( Args&&… args );容器中无拥有该关键的元素，则插入以给定的 args 原位构造的新元素到容器。
template <class… Args>
iterator emplace_hint( const_iterator hint, Args&&… args );插入新元素到容器，以 hint 为应当放置新元素位置的建议。原位构造元素，即不进行复制或移动操作。
template <class… Args>
pair<iterator, bool> try_emplace(const key_type& k, Args&&… args);若容器中已存在等价于 k 的关键，则不做任何事。
iterator erase( iterator pos );移除位于 pos 的元素
iterator erase( const_iterator first, const_iterator last );移除范围 [first; last) 中的元素，它必须是 *this 中的合法范围。
size_type erase( const key_type& key );移除键等价于 key 的元素（如果存在一个）。
template< class K >
size_type erase( K&& x );移除键比较等价于值 x 的元素（如果存在一个）。
void swap( unordered_map& other );将内容与 other 的交换。不在单独的元素上调用任何移动、复制或交换操作。
node_type extract( const_iterator position );解链含 position 所指向元素的结点并返回占有它的结点柄。
node_type extract( const key_type& k );若容器拥有元素而其关键等于 x ，则从容器解链该元素并返回占有它的结点柄。
template<class H2, class P2>
void merge( std::unordered_map<Key, T, H2, P2, Allocator>& source );试图提取（“接合”） source 中每个元素，并用 *this 的散列函数与键相等谓词插入到 *this 。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"} };
    unordered_map<int, string> m2;
    m1.insert({ 5,"three" });
    m1.insert_or_assign(6,"windows" );
    m1.emplace(7, "u盘");
    m1.try_emplace(8, "u盘");

    cout << "m1----------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }

    m1.erase(m1.begin());
    cout << "m1----------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }
    m1.swap(m2);
    cout << "m1----------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }
    cout << "m2----------" << endl;
    for (auto it = m2.begin(); it != m2.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }
    

    return 0;
}

在这里插入图片描述

4.查找(at;operator[];count; find;contains;equal_range;)

函数功能
T& at( const Key& key );返回到拥有等于 key 的关键的元素被映射值的引用。
T& operator[]( const Key& key );返回到映射到等于 key 的键的值的引用，若这种键不存在则进行插入。
T& operator[]( Key&& key );返回到映射到等于 key 的键的值的引用，若这种键不存在则进行插入。
size_type count( const Key& key ) const;返回拥有比较等于指定参数 key 的关键的元素数，因为此容器不允许重复故为 1 或 0 。
template< class K >
size_type count( const K& x ) const;返回键比较等价于指定参数 x 的元素数。
iterator find( const Key& key );寻找键等于 key 的的元素。
bool contains( const Key& key ) const;检查容器中是否有键等价于 key 的元素。若有这种元素则为 true ，否则为 false 。
std::pair<iterator,iterator> equal_range( const Key& key );返回容器中所有键等于 key 的元素范围。范围以二个迭代器定义，指向所需范围的首元素，
std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;返回容器中所有键等于 key 的元素范围。范围以二个迭代器定义，指向范围的尾后一位元素。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"},{1,"summer"} };

    cout << "m1----------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }

    string x = m1.at(1);
    cout << "m1.at(1): " << x << endl;

    m1[1] = "paper";//更新既存值
    m1[6] = "water";//插入新值

    cout << "m1.count(1): " << m1.count(1) << endl;
    
    auto it = m1.find(2);
    cout << it->first << "-->" << it->second << endl;

    auto range = m1.equal_range(1);
    for (it = range.first; it != range.second; ++it) 
    {
        std::cout << it->first << "--->"<< it->second << '\n';
    }

    cout << "m1----------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }
       

    return 0;
}

在这里插入图片描述
补充find()函数用法

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    unordered_map<int, int> map;
    map.insert({ 4,1 });
    map.insert({ 5,1 });
    map.insert({ 6,2 });

    if (map.find(5) != map.end())
    {
        cout << "success";
    }

    return 0;
}

5.桶接口(begin;cbegin;end;cend;bucket_count;max_bucket_count;bucket_size;bucket)

桶接口功能
local_iterator begin( size_type n );返回指向下标为 n 的桶首元素的迭代器。
const_local_iterator cbegin( size_type n ) const;返回指向下标为 n 的桶首元素的迭代器。
local_iterator end( size_type n );返回后随下标为 n 的桶的最后元素的元素的迭代器。
const_local_iterator cend( size_type n ) const;返回后随下标为 n 的桶的最后元素的元素的迭代器。
size_type bucket_count() const;返回容器中的桶数。
size_type max_bucket_count() const;返回容器由于系统或库实现限制的能保有的最大桶数。
size_type bucket_size( size_type n ) const;返回下标为 n 的桶中的元素数。
size_type bucket( const Key& key ) const;返回关键 key 的桶的下标。始终会在此桶中找到关键等于 key 的元素（若存在）。返回值仅对 bucket_count() 返回相同值的容器实例合法。若 bucket_count() 为零则行为未定义。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"},{5,"summer"} };

    int n = m1.bucket_count();//返回桶数
    cout << "m1.bucket_count():  " << n << endl;
       
    for (int i = 0; i < n; i++)
    {
        cout << "bucket[" << i << "]" << ".size()" << m1.bucket_size(i) << "contains: ";
        for (auto it = m1.begin(i); it != m1.end(i); it++)
        {
            cout << "[" << it->first << "-->" << it->second << "]";
        }
        cout << endl;
    }

    cout << "1 in the bucket" << m1.bucket(1) << endl;

    return 0;
}

在这里插入图片描述

6.哈希策略(load_factor;max_load_factor;rehash;reserve)

哈希策略功能
float load_factor() const;返回每个桶元素的平均数，即 size() 除以 bucket_count() 。
float max_load_factor() const;管理最大加载因子（每个桶的平均元素数）。返回最大加载因子。
void max_load_factor( float ml );管理最大加载因子（每个桶的平均元素数）。设置最大加载因子为 ml 。
void rehash( size_type count );设置桶数为 count 并重哈希容器，即考虑桶总数已改变，再把元素放到适当的桶中。
void reserve( size_type count );设置桶数为适应至少 count 个元素，而不超出最大加载因子所需的数，并重哈希容器，即考虑桶数已更改后将元素放进适合的桶。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"},{5,"summer"} };

    int n = m1.bucket_count();//返回桶数
    cout << "m1.bucket_count():  " << n << endl;
       
    for (int i = 0; i < n; i++)
    {        
        cout << "buckst's load_factor:(每个桶的平均元素数量) " << m1.load_factor() <<"  ";
        cout << "bucket[" << i << "]" << ".size():" << m1.bucket_size(i) << "contains: ";

        for (auto it = m1.begin(i); it != m1.end(i); it++)
        {
            cout << "[" << it->first << "-->" << it->second << "]";
        }
        cout << endl;
    }

    cout << "1 in the bucket" << m1.bucket(1) << endl;

    m1.rehash(16);
    for (int i = 0; i < n; i++)
    {
        cout << "buckst's load_factor:(每个桶的平均元素数量) " << m1.load_factor() << "  ";
        cout << "bucket[" << i << "]" << ".size()：" << m1.bucket_size(i) ;

        
        cout << endl;
    }

    return 0;
}

在这里插入图片描述

7.观察器(hash_function;key_eq)

观察期功能说明
hasher hash_function() const;返回对关键哈希的函数。
key_equal key_eq() const;返回比较关键相等性的函数。

8.非成员函数(operator==;std::swap;erase_if;)

非成员函数功能
template< class Key, class T, class Hash, class KeyEqual, class Allocator >bool operator==( const std::unordered_map<Key,T,Hash,KeyEqual,Allocator>& lhs,const std::unordered_map<Key,T,Hash,KeyEqual,Allocator>& rhs );比较二个无序容器的内容。若下列条件成立则二个无序容器 lhs 与 rhs 相等：lhs.size() ==== rhs.size()从 lhs.equal_range(lhs_eq1) 获得的每组等价元素 [lhs_eq1, lhs_eq2) 拥有在另一容器中从 rhs.equal_range(rhs_eq1) 获得的对应等价元素组 [rhs_eq1, rhs_eq2) ，且它们拥有下列属性：std::distance(lhs_eq1, lhs_eq2) == == std::distance(rhs_eq1, rhs_eq2) 。std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true 。
template< class Key, class T, class Hash, class KeyEqual, class Alloc >void swap( std::unordered_map<Key,T,Hash,KeyEqual,Alloc>& lhs, std::unordered_map<Key,T,Hash,KeyEqual,Alloc>& rhs );为 std::unordered_map 特化 std::swap 算法。交换 lhs 与 rhs 的内容。调用 lhs.swap(rhs) 。
#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    
    unordered_map<int, string> m1 = { {1,"This"},{2,"is"},{3,"an"},{4,"apple"},{5,"summer"} };

    unordered_map<int, string> m2 = { {1,"This"} };


    bool tag = (m1 == m2) ? true : false;
    cout << tag;

    swap(m1, m2);

    cout << "m1---------------" << endl;
    for (auto it = m1.begin(); it != m1.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }
    
    cout << "m2---------------" << endl;
    for (auto it = m2.begin(); it != m2.end(); it++)
    {
        cout << it->first << "-->" << it->second << endl;
    }

    return 0;
}

在这里插入图片描述

END!!!

# 哈希算法 # 散列表 # 算法
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

avatar GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

avatar GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m

avatar GitCode 开源社区