5
C++进阶（unordered_set+unordered_map模拟实现） - 一只少年AAA
source link: https://www.cnblogs.com/yzsn12138/p/17004154.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
unordered_set
- unordered_set是以无特定顺序存储唯一元素的容器，并且允许根据它们的值快速检索单个元素，是一种K模型。
- 在unordered_set中，元素的值同时是它的key，它唯一地标识它。键值是不可变的，因unordered_set中的元素不能在容器中修改一次 ，但是可以插入和删除它们。
- 在内部，unordered_set中的元素不是按任何特定顺序排序的（无序），而是根据它们的哈希值组织成桶，以允许直接通过它们的值快速访问单个元素，时间复杂度可以达到O(1)。
- unordered_set容器比set容器更快地通过它们的key访问单个元素，尽管它们通常对于通过其元素的子集进行范围迭代的效率较低。
- 容器中的迭代器至少是单向迭代器。
unordered_set<string> uset;//构造函数
unordered_set<string> uset2(++uset.begin(),uset.end());//，如果不想全部拷贝，可以使用 unordered_set 类模板提供的迭代器，在现有 unordered_set 容器中选择部分区域内的元素，为新建 unordered_set 容器初始化
unordered_set ( const unordered_set& ust );//拷贝构造
容量和大小
empty();//若容器为空，则返回 true；否则 false
size();//返回当前容器中存有元素的个数
begin();//返回指向容器中第一个元素的正向迭代器
end();//返回指向容器中最后一个元素之后位置的正向迭代器
cbegin();//和begin()功能相同，只不过其返回的是const类型的正向迭代器
cend();//和end()功能相同，只不过其返回的是const类型的正向迭代器
元素的访问和查找
find(key);//查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果end()方法返回的迭代器）
count(key);//在容器中查找值为 key 的元素的个数
equal_range(key);//返回一个pair对象，其包含2个迭代器，用于表明当前容器中值为key的元素所在的范围
元素的插入和删除
emplace();//向容器中添加新元素，效率比insert()方法高
emplace_hint();//向容器中添加新元素，效率比 nsert()方法高
insert();//向容器中添加新元素
erase();//删除指定元素
clear();//清空容器，即删除容器中存储的所有元素
swap();//交换2个 unordered_set 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等
实例演示：
void test_unordered_set()
{
unordered_set<int> us;
set<int> s;
int arr[] = { 4,2,3,1,6,8,9,3 };
for (auto e : arr)
{
us.insert(e);
s.insert(e);
}
unordered_set<int>::iterator usit = us.begin();
set<int>::iterator sit = s.begin();
cout << "unordered_set:" << endl;
while (usit != us.end())
{
cout << *usit << " ";
++usit;
}
cout << endl;
cout << "set:" << endl;
while (sit != s.end())
{
cout << *sit << " ";
++sit;
}
cout << endl;
}
unordered_map
- unordered_map是存储<key, value>键值对（KV模型）的关联式容器，其允许通过keys快速的索引到与其对应的value。
- 在unordered_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
- 在内部，unordered_map没有对<key, value>按照任何特定的顺序排序（无序）, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
- unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_map实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
- 它的迭代器是一个单向迭代器。
unordered_map<string,string> umap//构造函数： 可以不初始化地构造，也可以用一个容器的迭代器去构造
unordered_map ( const unordered_map& ump );//拷贝构造
容量和大小
empty();//判断容器是否为空,，若容器为空，则返回 true；否则 false
size();//返回容器中的元素个数
begin();//返回指向容器中第一个键值对的正向迭代器
end();//返回指向容器中最后一个键值对之后位置的正向迭代器
cbegin();//和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对
cend();//和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对
元素的访问和查找
operator[key];//该模板类中重载了 [] 运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值。注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对
at(key);//返回容器中存储的键 key 对应的值，如果key不存在，则会抛出 out_of_range 异常
find(key);//查找以key为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果end()方法返回的迭代器）
元素的插入和删除
emplace();//向容器中添加新键值对，效率比 insert()方法高
emplace_hint();//向容器中添加新键值对，效率比insert()方法高
insert();//向容器中添加新键值对
erase();//删除指定键值对
clear();//清空容器，即删除容器中存储的所有键值对
swap();//交换2个unordered_map容器存储的键值对，前提是必须保证这2个容器的类型完全相等
void test_unordered_map()
{
unordered_map<int, int> um;
map<int, int> m;
int arr[] = { 4,2,3,1,6,8,9,3 };
for (auto e : arr)
{
um.insert(make_pair(e, e));
m.insert(make_pair(e, e));
}
unordered_map<int, int>::iterator umit = um.begin();
map<int, int>::iterator mit = m.begin();
cout << "unordered_map:" << endl;
while (umit != um.end())
{
cout << umit->first << ":" << umit->second << endl;
++umit;
}
cout << "map:" << endl;
while (mit != m.end())
{
cout << mit->first << ":" << mit->second << endl;
++mit;
}
}
unordered_map和unordered_set的实现
这里我们用上一篇的博客中的哈希桶来封装出unordered_map和unordered_set两个容器
哈希桶代码：HashTable.h文件
#pragma once
#include<iostream>
#include<vector>
using namespace std;
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
//仿函数，获取key值
template<class K, class V>
struct KeyOfValue
{
const K& operator()(const K& key)
{
return key;
}
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
namespace CLOSE_HASH
{
//闭散列，需要三种状态
enum State
{
EMPTY,
EXITS,
DELETE
};
//定义节点
template <class T>
struct HashData
{
//这里的data对象是匿名对象转化的，被const修饰不能修改，就是传参的关系，你传入了一个对象
//被const修饰，就代表传入的那个对象不能被修改，你自己的内容还是可以修改的
HashData(const T& data = T(), const State& state = EMPTY)
: data(data)
, state(state){}
T data;
State state;
};
//哈希表
template<class K, class T, class KOFV>
class HashTable
{
typedef HashData<T> HashData;
public:
HashTable(size_t capacity = 10)
: table(capacity)
, size(0)
{}
size_t getNextPrime(size_t num)
{
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
//返回比那个数大的下一个质数
if (primeList[i] > num)
{
return primeList[i];
}
}
//如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量
return primeList[PRIMECOUNT - 1];
}
//除留余数法
size_t HashFunc(const K& key)
{
return key % table.size();
}
//插入元素
bool Insert(const T& data)
{
/*
1.首先要判断是否需要增容，当装填因子>0.7的时候增容（装填因子 = 数据个数/哈希表大小）
2.创建一个新表，把旧表的元素重新放到新表当中，因为表的大小发生变化，所以数据在旧表中的位置和新表的位置不一样，需要重新调整
3.利用swap将两个表进行交换，函数结束的时候，旧表被自动析构
4.增容之后，插入元素，采用线性探测，插入元素
*/
KOFV kofv;
if (size * 10 / table.size() >= 7)//增容
{
//增容的大小按照别人算好的近似两倍的素数来增，这样效率更高，也可以直接2倍或者1.5倍。
//使用了vector默认的有参构造函数vector(size_type n, const value_type& val = value_type())//有参构造用n个val构造并初始化容器
//const value_type& val = value_type()这段代码是匿名对象类型转换
vector<HashData> newTable(getNextPrime(size));
for (size_t i = 0; i < table.size(); i++)
{
//将旧表中的元素映射到新表当中
if (table[i].state == EXITS)
{
int index = HashFunc(kofv(table[i].data));
while (newTable[index].state == EXITS)
{
//不可能存在重复元素，因为旧表中不可能有重复元素
index++;
if (index == newTable.capacity())
{
index = 0;
}
}
newTable[index]=table[i];
}
}
table.swap(newTable);//交换两个表
}
//用哈希函数计算出映射的位置
size_t index = HashFunc(kofv(data));
//int start = index;
//int i = 1;
while (table[index].state == EXITS)
{
if (table[index].data == data)
return false;
// 二次探测
/*index = start + pow(i, 2);
index %= _tables.size();
++i;*/
++index;
// 走到末尾置0
if (index == table.size())
index = 0;
}
// DELETE和EMPTY的位置都可以插入数据
table[index].data = data;
table[index].state = EXITS;
++size;
return true;
}
//查找元素
HashData* Find(const K& key)
{
KOFV kofv;
size_t index = HashFunc(key);
int start = index;
while (table[index].state != EMPTY)
{
if (kofv(table[index].data) == key)
{
if (table[index].state == EXITS)
{
return &table[index];
}
// table[index].state == DELETE
else
{
//表示你要找的元素已经被删除了
return nullptr;
}
}
++index;
if (index == table.size())
index = 0;
// 找完一遍没有就退出 这里其实是不必要的，这里面一定有空的位置，所以一定会退出
if (index == start)
{
return nullptr;
}
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
//找到了，进行删除
if (ret != nullptr)
{
ret->state = DELETE;
size--;
return true;
}
else
{
//没找到
return false;
}
}
private:
vector<HashData> table;
int size = 0;
};
void TestHashTable1()
{
HashTable<int, int, KeyOfValue<int, int>> ht;
// HashTable<int, pair<int, int>, KeyOfValue<int, int>> ht;
int arr[] = { 10,20,14,57,26,30,49,72,43,55,82 };
for (auto e : arr)
{
if (e == 72)
{
int a = 0;
}
ht.Insert(e);
}
for (auto e : arr)
{
ht.Erase(e);
}
}
void TestHashTable2()
{
HashTable<int, pair<int, int>, KeyOfValue<int, int>> ht;
int arr[] = { 15,23,57,42,82,26,30,49,72,43,55 };
for (auto e : arr)
{
ht.Insert(make_pair(e, e));
}
/*for (auto e : arr)
{
ht.Erase(e);
}*/
}
}
namespace OPEN_HASH
{
template<class T>
struct HashNode
{
HashNode(const T&data):data(data),next(nullptr){}
T data;
HashNode<T>* next;
};
template<class K>
struct _Hash
{
// 大多树的类型就是是什么类型就返回什么类型
const K& operator()(const K& key)
{
return key;
}
};
// 特化string
template<>
struct _Hash<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
// 把字符串的所有字母加起来 hash = hash*131 + key[i]
for (size_t i = 0; i < key.size(); ++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
//前置声明
template<class K, class T, class KOFV, class Hash = _Hash<K>>
class HashBucket;
//迭代器的实现
template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
struct HashBucket_Iterator
{
typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
typedef HashNode<T> Node;
typedef HashBucket<K, T, KOFV, Hash> HashBucket;
Node* node;
HashBucket* _phb;
HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
//操作符重载
Ref operator*()
{
return node->data;
}
Ptr operator->()
{
return &node->data;
}
Self& operator++()
{
if (node->next)
{
node = node->next;
return *this;
}
else
{
KOFV kofv;
size_t index = _phb->HashFunc(kofv(node->data));
for (size_t i = index + 1; i < _phb->tables.size(); ++i)
{
if (_phb->tables[i])
{
node = _phb->tables[i];
return *this;
}
}
node = nullptr;
return *this;
}
}
bool operator==(const Self& self) const
{
return node == self.node
&& _phb == self._phb;
}
bool operator!=(const Self& self) const
{
return !this->operator==(self);
}
};
template<class K, class T, class KOFV, class Hash>
class HashBucket
{
typedef HashNode<T> Node;
friend struct HashBucket_Iterator<K, T, T&, T*, KOFV, Hash>;
public:
typedef HashBucket_Iterator<K, T, T&, T*, KOFV, Hash> iterator;
size_t getNextPrime(size_t num)
{
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
//返回比那个数大的下一个质数
if (primeList[i] > num)
{
return primeList[i];
}
}
//如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量
return primeList[PRIMECOUNT - 1];
}
//除留余数法
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key) % tables.size();
}
iterator begin()
{
for (size_t i = 0; i < tables.size(); ++i)
{
if (tables[i] != nullptr)
return iterator(tables[i], this);// 哈希桶的第一个节点
}
return end();// 没有节点返回最后一个迭代器
}
iterator end()
{
return iterator(nullptr, this);
}
~HashBucket()
{
Clear();
}
void Clear()
{
for (size_t i = 0; i < tables.size(); ++i)
{
Node* cur = tables[i];
while (cur)
{
Node* next = cur->next;
delete cur;
cur = next;
}
}
}
pair<iterator, bool> Insert(const T& data)
{
KOFV kofv;
//负载因子为1就增容
if (size == tables.size())
{
vector<Node*> newTable(getNextPrime(size));
for (size_t i = 0; i < tables.size(); i++)
{
Node* prev = nullptr;
Node* cur = tables[i];
//把一个位置的所有节点转移，然后换下一个位置
while (cur)
{
//记录下一个节点的位置
Node* next = cur->next;
size_t index = HashFunc(kofv(cur->data));
//把cur连接到新表上
cur->next = newTable[index];
newTable[index] = cur;
//cur会发生变化，需要提前记录next
cur = next;
}
}
tables.swap(newTable);
}
size_t index = HashFunc(kofv(data));
// 先查找该条链表上是否有要插入的元素
Node* cur = tables[index];
while (cur)
{
if (kofv(cur->data) == kofv(data))
return make_pair(iterator(cur, this), false);
cur = cur->next;
}
// 插入数据，选择头插（也可以尾插）
Node* newnode = new Node(data);
newnode->next = tables[index];
tables[index] = newnode;
++size;
return make_pair(iterator(newnode, this), true);
}
iterator Find(const K& key)
{
KOFV kofv;
int index = HashFunc(key) ;
Node* cur = tables[index];
while (cur)
{
if (key == kofv(cur->data))
{
return iterator(cur, this);
}
cur = cur->next;
}
return iterator(nullptr);
}
bool Erase(const K& key)
{
KOFV kofv;
int index = HashFunc(key) ;
Node* prev = nullptr;
Node* cur = tables[index];
while (cur)
{
if (key == kofv(cur->data))
{
// 删第一个节点时
if (prev == nullptr)
{
tables[index] = cur->next;
}
else
{
prev->next = cur->next;
}
size--;
delete cur;
return true;
}
prev = cur;
cur = cur->next;
}
return false;
}
private:
vector<Node*> tables;
int size = 0;
};
void TestHashBucket2()
{
HashBucket<int, int, KeyOfValue<int, int>> ht;
int arr[] = { 15,23,57,42,82,26,30,49,72,43,55 };
for (auto e : arr)
{
ht.Insert(e);
}
for (auto e : arr)
{
HashBucket<int, int, KeyOfValue<int, int>>::iterator it = ht.begin();
while (it != ht.end())
{
cout << *it << " ";
++it;
}
cout << endl;
ht.Erase(e);
}
}
void TestHashBucket3()
{
HashBucket<string, string, KeyOfValue<string, string>> ht;
ht.Insert("solleHas");
ht.Insert("apple");
ht.Insert("sort");
ht.Insert("pass");
ht.Insert("cet6");
HashBucket<string, string, KeyOfValue<string, string>>::iterator it = ht.begin();
while (it != ht.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
改造哈希表
这里用的是哈希桶来封装unordered_map和unordered_set两个容器
const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
template<class T>
struct HashNode
{
HashNode(const T&data):data(data),next(nullptr){}
T data;
HashNode<T>* next;
};
template<class K>
struct _Hash
{
// 大多树的类型就是是什么类型就返回什么类型
const K& operator()(const K& key)
{
return key;
}
};
// 特化string
template<>
struct _Hash<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
// 把字符串的所有字母加起来 hash = hash*131 + key[i]
for (size_t i = 0; i < key.size(); ++i)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
template<class K, class T, class KOFV, class Hash>
class HashBucket
{
private:
vector<Node*> tables;
int size = 0;// 记录表中的数据个数
};
为了让哈希表能够跑起来，我们这里实现一个迭代器的操作
迭代器的框架： 这里有两个成员，一个是节点指针，还有一个是哈希表的指针，只要就是为了方便实现迭代器++遍历哈希表的操作。模板参数列表的前四个主要是为了实现普通迭代器和const迭代器，第五个参数就是为了获得T中的key值，是一个仿函数（前几篇博客都有提到过），最后一个模板参数是哈希函数，为了构造出哈希表指针而存在
template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
struct HashBucket_Iterator
{
typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
typedef HashNode<T> Node;
typedef HashBucket<K, T, KOFV, Hash> HashBucket;
Node* node;
HashBucket* _phb;
HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
}
迭代器基本操作的实现：
//迭代器的实现
template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
struct HashBucket_Iterator
{
typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
typedef HashNode<T> Node;
typedef HashBucket<K, T, KOFV, Hash> HashBucket;
Node* node;
HashBucket* _phb;
HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
//操作符重载
Ref operator*()
{
return node->data;
}
Ptr operator->()
{
return &node->data;
}
Self& operator++()
{
if (node->next)
{
node = node->next;
return *this;
}
else
{
KOFV kofv;
size_t index = _phb->HashFunc(kofv(node->data));
for (size_t i = index + 1; i < _phb->tables.size(); ++i)
{
if (_phb->tables[i])
{
node = _phb->tables[i];
return *this;
}
}
node = nullptr;
return *this;
}
}
bool operator==(const Self& self) const
{
return node == self.node
&& _phb == self._phb;
}
bool operator!=(const Self& self) const
{
return !this->operator==(self);
}
};
哈希表内部改造：
template<class K, class T, class KOFV, class Hash>
class HashBucket
{
typedef HashNode<T> Node;
friend struct HashBucket_Iterator<K, T, T&, T*, KOFV, Hash>;
public:
typedef HashBucket_Iterator<K, T, T&, T*, KOFV, Hash> iterator;
size_t getNextPrime(size_t num)
{
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
//返回比那个数大的下一个质数
if (primeList[i] > num)
{
return primeList[i];
}
}
//如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量
return primeList[PRIMECOUNT - 1];
}
//除留余数法
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key) % tables.size();
}
iterator begin()
{
for (size_t i = 0; i < tables.size(); ++i)
{
if (tables[i] != nullptr)
return iterator(tables[i], this);// 哈希桶的第一个节点
}
return end();// 没有节点返回最后一个迭代器
}
iterator end()
{
return iterator(nullptr, this);
}
~HashBucket()
{
Clear();
}
void Clear()
{
for (size_t i = 0; i < tables.size(); ++i)
{
Node* cur = tables[i];
while (cur)
{
Node* next = cur->next;
delete cur;
cur = next;
}
}
}
};
封装unordered_map和unordered_set
unordered_set.h头文件
#pragma once
#include"HashTable.h"
using namespace OPEN_HASH;
namespace Simulation
{
template<class K, class Hash = _Hash<K>>
class unordered_set
{
struct SetKeyOfValue
{
const K& operator()(const K& key)
{
return key;
}
};
// 告诉编译器这只是一个类型
typedef HashBucket<K, K, SetKeyOfValue, Hash> HashBucket;
public:
// 告诉编译器这只是一个类型
typedef typename HashBucket::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K& kv)
{
return _ht.Insert(kv);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
private:
HashBucket _ht;
};
void test_unordered_set1()
{
unordered_set<int> s;
s.insert(3);
s.insert(2);
s.insert(1);
s.insert(2);
s.insert(4);
s.erase(3);
for (auto e : s)
{
cout << e << endl;
}
}
void test_unordered_set2()
{
unordered_set<string> s;
s.insert("sort");
s.insert("pass");
s.insert("cet6");
s.insert("pass");
s.insert("cet6");
s.erase("sort");
for (auto& e : s)
{
cout << e << endl;
}
}
}
unordered_map.h头文件
#pragma once
#include"HashTable.h"
using namespace OPEN_HASH;
namespace Simulation
{
template<class K, class V, class Hash = _Hash<K>>
class unordered_map
{
struct MapKeyOfValue
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef HashBucket<K, pair<K, V>, MapKeyOfValue, Hash> HashBucket;
public:
// 告诉编译器这只是一个类型
typedef typename HashBucket::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashBucket _ht;
};
void test_unordered_map1()
{
unordered_map<int, int> um;
um.insert(make_pair(1, 1));
um.insert(make_pair(3, 3));
um.insert(make_pair(2, 2));
um.insert(make_pair(4, 4));
for (auto& e : um)
{
cout << e.first << ":" << e.second << endl;
}
/*unordered_map<int, int>::iterator it = um.begin();
++it;
cout << it->first << endl;*/
}
void test_unordered_map2()
{
unordered_map<string, string> um;
um.insert(make_pair("string", "字符串"));
um.insert(make_pair("sort", "排序"));
um.insert(make_pair("pass", "通过"));
um.insert(make_pair("program", "程序"));
for (auto& e : um)
{
cout << e.first << ":" << e.second << endl;
}
/*unordered_map<int, int>::iterator it = um.begin();
++it;
cout << it->first << endl;*/
}
void test_unordered_map3()
{
unordered_map<string, int> countMap;
string strArr[] = { "香蕉","香蕉" ,"水蜜桃","西瓜","苹果","西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };
for (auto& e : strArr)
{
countMap[e]++;
}
countMap["芒果"] = 10;
for (auto& e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
}
}
typedef详解
搞懂了c++创始人写的< the design and evolution of cpp >中的下面这个例子, 有助于你理解typdef:
typedef int P();
typedef int Q();
class X {
static P(Q); // 等价于static int Q(), Q在此作用域中不再是一个类型
static Q(P); // 等价于static int Q(int ()), 定义了一个名为Q的function
};
隐藏技能：typedef 定义的新类型, 使用时可以省略括号
typedef int NUM;
NUM a = 10; // 也可写成`NUM(a) = 10;`
NUM(b) = 12; // 也可写成`NUM b = 12;`
官方定义
初次接触此类typedef用法的程序员直观上理解这个例子比较困难, 我们来看一下typedef的官方定义:
Typedef does not work like typedef [type] [new name]. The [new name] part does not always come at the end.
You should look at it this way: if [some declaration] declares a variable, typedef [same declaration] would define a type
看我标黑的这句话, 总结一下就是: 任何声明变量的语句前面加上typedef之后，原来是变量的都变成一种类型。不管这个声明中的标识符号出现在中间还是最后
举个例子：
初级：
typedef int x; // 定义了一个名为x的int类型
typedef struct { char c; } s; // 定义名为s的struct类型
typedef int *p; //定义了一个名为p的指针类型, 它指向int (中文描述指针好累)
高级：（注意标识符不一定在最后）
typedef int A[]; // 定义一个名为A的int数组的类型
typedef int f(); // 定义一个名为f, 参数为空, 返回值为int的函数类型
typedef int g(int); // 定义一个名为g, 含一个int参数, 返回值为int的函数类型
这时候我们回头看一开始的那个例子：
typedef int P();
static P(Q);
这样就比较好理解了吧，typedef定义了一个名叫P，参数为空，返回值是int的函数类型，根据我上面介绍的隐藏技能，P(Q)就等价于P Q，声明Q是一个返回值为int
这玩意有什么用呢?
我们都知道C++语言里, 函数都是先声明后使用的(除非在使用之前定义), 看以下例子:
#include <iostream>
#include <stdio.h>
#include <string>
typedef int P(); // 简单的
typedef void Q(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true); // 复杂的
class X {
public:
P(eat_shit); // 等价于声明`int eat_shit();`
Q(bullshit); // 等价于声明`void bullshit(int *p, const string& s1, const string& s2, size_t size, bool is_true);`
};
int main() {
X *xx;
printf("shit ret: %d\n", xx->eat_shit());
int a[] = {1, 3, 4, 5, 7};
xx->bullshit(a, "foo", "bar", sizeof(a)/sizeof(int), true);
}
int X::eat_shit() {
return 888;
}
void X::bullshit(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true) {
std::cout << "s1: " << s1 << ", s2: " << s2 << ", size: " << size << std::endl;
printf("elems:\n");
for(int i = 0; i < size; i++) {
printf("%d %s", *p++, (i == size-1) ? "" : ",");
}
printf("\n");
}
总结:
- type (var)(...); // 变量名var与结合，被圆括号括起来，右边是参数列表。表明这是函数指针
- type (var)[]; //变量名var与结合，被圆括号括起来，右边是[]运算符。表示这是数组指针
- type (*var[])...; // 变量名var先与[]结合，说明这是一个数组（至于数组包含的是什么，由旁边的修饰决定）
typename详解
"typename"是一个C++程序设计语言中的关键字。当用于泛型编程时是另一术语"class"的同义词。这个关键字用于指出模板声明（或定义）中的非独立名称（dependent names）是类型名，而非变量名
typename 的作用就是告诉 c++ 编译器，typename 后面的字符串为一个类型名称，而不是成员函数或者成员变量，这个时候如果前面没有 typename，编译器没有任何办法知道 T::LengthType 是一个类型还是一个成员名称(静态数据成员或者静态函数)，所以编译不能够通过。
举个例子：假设你现在要针对某一种容器设定一个操作函数
template <class T>
void func (){
T::iteartor * testpt;
}
看到这段代码的时候我们大多数情况下都是可以看出来，这一段代码中的操作是定义了一个容器的迭代器指针类型的变量。但是模版是在编译期间展开的，只有在模版实例化的时候编译器才可以推导出其类型。这段代码对于编译器来说很有可能产生错误的理解，因为我们能快速的根据iteartor是一个迭代器想到这是定义了一个变量，但是对于编译器来说，它怎么会知道一定知道T::iteartor一定是一个迭代器类型，或者一定知道这是一个类型？因为能表示成这样形式的代码有三种情况：
- 在T作用域中存在一个iteartor的静态变量
- 在T作用域中存在一个iteartor的静态成员函数
- 是T类型的成员变量
以上三种含义均可以表示成例子中的样子，编译器怎么知道这是哪一种。在实践过程中，编译器会直接对testpt报错，而且在模板实例化之前，完全没有办法来区分它们，这绝对是滋生各种bug的温床。这时C++标准委员会再也忍不住了，与其到实例化时才能知道到底选择哪种方式来解释以上代码，委员会决定引入一个新的关键字，这就是typename
typename真正的用途
编译期间模版的推导有一个这样的规则：如果解析器在template推导期间遇到了嵌套从属名称，那么不指定他为一个类型，解析器就一定不会把它当成一个类型。
什么是嵌套从属类型？
事实上类型T::const_iterator依赖于模板参数T， 模板中依赖于模板参数的名称称为从属名称（dependent name）， 当一个从属名称嵌套在一个类里面时，称为嵌套从属名称（nested dependent name）。 其实T::const_iterator还是一个嵌套从属类型名称（nested dependent type name）。嵌套从属名称是需要用typename声明的，其他的名称是不可以用typename声明的。
总结：嵌套从属名称是需要用typename声明的，其他的名称是不可以用typename声明的
T::iteartor这种，这也就是为什么编译器会对testpt报错的原因。那要怎样指定testpt为一个类型，这就回到了开头的那个问题，我们可以这样解决
template <class T>
void func (){
typename T::iteartor * testpt;
}
加上了typename之后我们就可以知道T::iteartor是一个类型，编译器也可以根据这个进行类型推导了
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK