定義于頭檔案 <unordered_set> | template< class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key> > class unordered_set; | (1) | (C++11 起) |
| namespace pmr { template <class Key, class Hash = std::hash<Key>, class Pred = std::equal_to<Key>> using unordered_set = std::unordered_set<Key, Hash, Pred, std::pmr::polymorphic_allocator<Key>>; } | (2) | (C++17 起) |
unordered_set is 是含有 Key 類型唯一對象集合的關聯容器。搜尋、插入和移除擁有平均常數時間複雜度。
在内部，元素并不以任何特别順序排序，而是組織進桶中。元素被放進哪個桶完全依賴其值的哈希。這允許對單獨元素的快速通路，因為哈希一旦，就準确指代元素被放入的桶。
不可修改容器元素（即使通過非 const 疊代器），因為修改可能更改元素的哈希，并破壞容器。
修改器
原位構造元素
std::unordered_set<Key,Hash,KeyEqual,Allocator>::emplace
| template< class... Args > std::pair<iterator,bool> emplace( Args&&... args ); | (C++11 起) |
若容器中無擁有該關鍵的元素，則插入以給定的
args
原位構造的新元素到容器。
細心地使用
emplace
允許在構造新元素的同時避免不必要的複制或移動操作。 準确地以與提供給
emplace
者相同的參數，通過 std::forward<Args>(args)... 轉發調用新元素的構造函數。 即使容器中已有擁有該關鍵的元素，也可能構造元素，該情況下新構造的元素将被立即銷毀。
若因插入發生重哈希，則所有疊代器都被非法化。否則疊代器不受影響。引用不被非法化。重哈希僅若新元素數量大于 max_load_factor()*bucket_count() 才發生。
參數
| args | - | 要轉發給元素構造函數的參數 |
傳回值
傳回由指向被插入元素，或若不發生插入則為既存元素的疊代器，和指代插入是否發生的 bool （若發生插入則為 true ，否則為 false ）。
異常
若任何操作抛出異常，則此函數無效果。
複雜度
平均為均攤常數，最壞情況與容器大小成線性。
使用提示原位構造元素
std::unordered_set<Key,Hash,KeyEqual,Allocator>::emplace_hint
| template <class... Args> iterator emplace_hint( const_iterator hint, Args&&... args ); | (C++11 起) |
插入新元素到容器，以
hint
為放置元素位置的建議。原位構造元素，即不進行複制或移動操作。
準确地以提供給函數的參數相同者，以 std::forward<Args>(args)... 轉發調用元素的構造函數。
若因插入發生重哈希，則所有疊代器都被非法化。否則疊代器不受影響。引用不被非法化。重哈希僅若新元素數量大于 max_load_factor()*bucket_count() 才發生。
參數
| hint | - | 疊代器，用作插入新元素位置的建議 |
| args | - | 轉發給元素構造函數的參數 |
傳回值
指向新插入元素的疊代器。
若因元素已存在而失敗，則傳回指向擁有等價關鍵的既存元素。
異常
若任何操作抛出異常，則此函數無效果（強異常保證）。
複雜度
平均為均攤常數，最壞情況下與容器大小成線性。
交換内容
std::unordered_set<Key,Hash,KeyEqual,Allocator>::swap
| void swap( unordered_set& other ); | (C++11 起) (C++17 前) |
| void swap( unordered_set& other ) noexcept(); | (C++17 起) |
将内容與
other
的交換。不在單個元素上調用任何移動、複制或交換操作。
所有疊代器和引用保持合法。尾後疊代器被非法化。
Hash
和
KeyEqual
對象必須可交換 (Swappable) ，并用非成員
swap
的非限定調用交換它們。
若 std::allocator_traits<allocator_type>::propagate_on_container_swap::value 為 true ，則用非成員 | (C++11 起) |
參數
| other | - | 要與之交換内容的容器 |
傳回值
（無）
異常
任何 | (C++17 前) |
| noexcept 規定： noexcept(std::allocator_traits<Allocator>::is_always_equal::value && std::is_nothrow_swappable<Hash>::value && std::is_nothrow_swappable<key_equal>::value) | (C++17 起) |
複雜度
常數。
調用示例
#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <unordered_set>
#include <time.h>
using namespace std;
struct Cell
{
int x;
int y;
Cell() = default;
Cell(int a, int b): x(a), y(b) {}
Cell &operator +=(const Cell &cell)
{
x += cell.x;
y += cell.y;
return *this;
}
Cell &operator +(const Cell &cell)
{
x += cell.x;
y += cell.y;
return *this;
}
Cell &operator *(const Cell &cell)
{
x *= cell.x;
y *= cell.y;
return *this;
}
Cell &operator ++()
{
x += 1;
y += 1;
return *this;
}
bool operator <(const Cell &cell) const
{
if (x == cell.x)
{
return y < cell.y;
}
else
{
return x < cell.x;
}
}
bool operator >(const Cell &cell) const
{
if (x == cell.x)
{
return y > cell.y;
}
else
{
return x > cell.x;
}
}
bool operator ==(const Cell &cell) const
{
return x == cell.x && y == cell.y;
}
};
struct myCompare
{
bool operator()(const int &a, const int &b)
{
return a < b;
}
};
std::ostream &operator<<(std::ostream &os, const Cell &cell)
{
os << "{" << cell.x << "," << cell.y << "}";
return os;
}
std::ostream &operator<<(std::ostream &os, const std::pair<const int, Cell> &pCell)
{
os << pCell.first << "-" << pCell.second;
return os;
}
struct CHash
{
size_t operator()(const Cell& cell) const
{
size_t thash = std::hash<int>()(cell.x) | std::hash<int>()(cell.y);
// std::cout << "CHash: " << thash << std::endl;
return thash;
}
};
struct CEqual
{
bool operator()(const Cell &a, const Cell &b) const
{
return a.x == b.x && a.y == b.y;
}
};
int main()
{
std::cout << std::boolalpha;
std::mt19937 g{std::random_device{}()};
srand((unsigned)time(NULL));
auto generate = []()
{
int n = std::rand() % 10 + 100;
Cell cell{n, n};
return cell;
};
std::unordered_set<Cell, CHash, CEqual> unordered_set1;
for (size_t index = 0; index < 5; index++)
{
//若容器中無擁有該關鍵的元素，則插入以給定的 args 原位構造的新元素到容器。
std::pair<std::unordered_set<Cell, CHash, CEqual>::iterator, bool> iit
= unordered_set1.emplace(std::rand() % 10 + 100, std::rand() % 10 + 100);
std::cout << "unordered_set1 emplace : " << *iit.first << " " << iit.second << std::endl;
}
std::cout << "unordered_set1: ";
std::copy(unordered_set1.begin(), unordered_set1.end(), std::ostream_iterator<Cell>(std::cout, " "));
std::cout << std::endl;
std::cout << std::endl;
std::unordered_set<Cell, CHash, CEqual> unordered_set2;
for (size_t index = 0; index < 5; index++)
{
//3-4) 插入 value ，以 hint 為應當開始搜尋的位置的非強制建議。
std::unordered_set<Cell, CHash, CEqual>::iterator iit
= unordered_set2.emplace_hint(unordered_set2.cbegin(),
std::rand() % 10 + 100, std::rand() % 10 + 100);
std::cout << "unordered_set2 insert : " << *iit << std::endl;
}
std::cout << "unordered_set2: ";
std::copy(unordered_set2.begin(), unordered_set2.end(), std::ostream_iterator<Cell>(std::cout, " "));
std::cout << std::endl;
std::cout << std::endl;
//将内容與 other 的交換。不在單個元素上調用任何移動、複制或交換操作。
unordered_set2.swap(unordered_set1);
std::cout << "after swap: " << std::endl;
std::cout << "unordered_set1: ";
std::copy(unordered_set1.begin(), unordered_set1.end(), std::ostream_iterator<Cell>(std::cout, " "));
std::cout << std::endl;
std::cout << "unordered_set2: ";
std::copy(unordered_set2.begin(), unordered_set2.end(), std::ostream_iterator<Cell>(std::cout, " "));
std::cout << std::endl;
std::cout << std::endl;
return 0;
}
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)