C++ std::Set＜std::pair＞的實(shí)現(xiàn)示例
更新時間：2025年10月21日 09:17:24 作者：全體目光向我看齊
本文主要介紹了C++ std::Set＜std::pair＞的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
1)std::set的三個關(guān)鍵特性
- 元素自動排序：
std::set始終按嚴(yán)格弱序（默認(rèn)std::less<Key>的字典序）維持有序，常見操作（插入、查找、上下界）復(fù)雜度均為 O(log N)。 - 元素不允許重復(fù)：比較器認(rèn)為“等價”的元素不能共存（即
!(a<b) && !(b<a)為真時視為等價）。 - 基于紅黑樹實(shí)現(xiàn)：標(biāo)準(zhǔn)庫通常采用紅黑樹；因此“有序 + 查找高效”是它相對
unordered_set的顯著特征。
2) 關(guān)于比較：Timestamp與std::unique_ptr<int>能否比較？
Timestamp：你給出的成員是 private int secondsFromEpoch。要參與排序，必須為 Timestamp 提供可用的嚴(yán)格弱序比較（通常實(shí)現(xiàn) operator< 或在比較器內(nèi)訪問一個 getter()）。
std::unique_ptr<int>：
- 標(biāo)準(zhǔn)提供了與同類 unique_ptr 的關(guān)系運(yùn)算符（<、<=、>、>=、==、!=），其比較語義是按底層指針地址比較（實(shí)現(xiàn)上等價于 std::less<int*>{}(p.get(), q.get())）。
- 注意：這不是按指向的“整數(shù)值”比較，而是按地址。如果你的業(yè)務(wù)語義是“同時間戳 + 指針指向的值也相等才算相等/有序”，地址比較可能不符合預(yù)期。
- 結(jié)論：可以比較，但“比較的是地址而非內(nèi)容”。
字典序：std::pair<A,B> 的默認(rèn) < 比較是先比較 first，若相等再比較 second。因此在 std::set<std::pair<Timestamp, std::unique_ptr<int>>> 中：
- 先比較 Timestamp；
- Timestamp 相等時，再比較 unique_ptr<int> 的地址。
3) 自定義透明比較器（heterogeneous lookup）
直接用 pair<Timestamp, unique_ptr<int>> 做鍵會遇到查找難題：
- 你不能構(gòu)造一個臨時 unique_ptr<int> 作為查找鍵的第二分量（會產(chǎn)生錯誤的所有權(quán)，臨時對象析構(gòu)時會delete 它指向的地址，造成雙重釋放風(fēng)險）。
- 正確姿勢是用透明比較器支持“用 (Timestamp, const int*) 這類異質(zhì)鍵進(jìn)行查找”，從而無需構(gòu)造 unique_ptr。
透明比較器（具備 using is_transparent = void;）允許 set.find / erase / lower_bound 等直接用可比較但類型不同的鍵（如 const int*）進(jìn)行 O(log N) 查找。
4) CRUD 規(guī)范做法（C++17+）
下述代碼塊分別演示 Create/Read/Update/Delete。請先看類型與比較器。
#include <set>
#include <memory>
#include <utility>
#include <optional>
#include <iostream>
// ========== 1) 可排序的 Timestamp ==========
class Timestamp {
int secondsFromEpoch_; // 私有
public:
explicit Timestamp(int s = 0) : secondsFromEpoch_(s) {}
int seconds() const noexcept { return secondsFromEpoch_; }
// 定義嚴(yán)格弱序（僅按秒比較）
friend bool operator<(const Timestamp& a, const Timestamp& b) noexcept {
return a.secondsFromEpoch_ < b.secondsFromEpoch_;
}
};
// 方便書寫
using Key = std::pair<Timestamp, std::unique_ptr<int>>;
// ========== 2) 透明比較器：支持 pair<Timestamp, unique_ptr<int>>
// 以及 (Timestamp, const int*) 這種異質(zhì)鍵的比較與查找 ==========
struct PairCmp {
using is_transparent = void; // 啟用異質(zhì)查找
// 基本：pair vs pair（按字典序：先時間戳，再指針地址）
bool operator()(const Key& a, const Key& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second.get(), b.second.get());
}
// 異質(zhì)：pair vs (Timestamp, const int*)
bool operator()(const Key& a, const std::pair<Timestamp, const int*>& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second.get(), b.second);
}
bool operator()(const std::pair<Timestamp, const int*>& a, const Key& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second, b.second.get());
}
// 也可追加只按 Timestamp 的異質(zhì)比較（用于范圍查詢）
bool operator()(const Key& a, const Timestamp& t) const noexcept {
return a.first < t;
}
bool operator()(const Timestamp& t, const Key& b) const noexcept {
return t < b.first;
}
};
using PairSet = std::set<Key, PairCmp>;
A. Create（插入）
std::set是節(jié)點(diǎn)容器，可無拷貝插入僅移動類型（如unique_ptr）。- 用
emplace/insert，傳右值/用std::make_unique。
PairSet s;
// 1) 直接 emplace（推薦）
s.emplace(Timestamp{100}, std::make_unique<int>(42));
s.emplace(Timestamp{100}, std::make_unique<int>(7)); // 與上一個可共存：時間戳相同但地址不同
s.emplace(Timestamp{120}, std::make_unique<int>(99));
// 2) 先構(gòu)造 Key 再 move
Key k{ Timestamp{130}, std::make_unique<int>(123) };
s.insert(std::move(k)); // k.second 置空
要點(diǎn)：
- 如果你希望“相同
Timestamp只允許一條記錄”，就不要把unique_ptr納入比較；而應(yīng)改用“僅比較Timestamp”的比較器（見 §7 變體方案）。
B. Read（查詢/遍歷）
1) 按（Timestamp, 指針地址）精確查找
利用透明比較器，避免構(gòu)造臨時
unique_ptr。
Timestamp t{100};
const int* addr = /* 已知的底層指針地址，如 it->second.get() */;
auto it = s.find(std::pair<Timestamp, const int*>{t, addr});
if (it != s.end()) {
std::cout << "found value=" << *(it->second) << "\n";
}
2) 按時間戳做范圍/等值查找
// 所有 timestamp == 100 的區(qū)間：
auto rng = s.equal_range(Timestamp{100}); // 依賴我們在比較器中提供的 (Key, Timestamp) 重載
for (auto it = rng.first; it != rng.second; ++it) {
// 這些元素的 it->first.seconds() 都是 100
}
// 所有 timestamp 在 [100, 130)：
for (auto it = s.lower_bound(Timestamp{100}); it != s.lower_bound(Timestamp{130}); ++it) {
// ...
}
3) 遍歷（有序）
for (const auto& [ts, ptr] : s) {
std::cout << ts.seconds() << " -> " << (ptr ? *ptr : -1) << "\n";
}
C. Update（更新）
重要原則：std::set 中的元素作為“鍵”不可就地修改其影響排序的部分（包括 Timestamp 與 unique_ptr 的地址）。否則會破壞紅黑樹不變量。
正確做法：使用 node handle（C++17）進(jìn)行“摘除-修改-再插入”。
1) 修改Timestamp或替換unique_ptr（地址會變）
// 找到一個元素
auto it = s.lower_bound(Timestamp{100});
if (it != s.end() && it->first.seconds() == 100) {
// 1) extract 節(jié)點(diǎn)，容器不再管理平衡關(guān)系中的該節(jié)點(diǎn)
auto nh = s.extract(it); // node_handle，擁有該 pair 的完整所有權(quán)
// 2) 修改 key 內(nèi)容（注意：任何影響排序的字段都只能在 node 中修改）
nh.value().first = Timestamp{105}; // 改時間戳
nh.value().second = std::make_unique<int>(555); // 新指針（地址變化）
// 3) 重新插入
auto [pos, ok] = s.insert(std::move(nh));
// ok==false 表示與現(xiàn)有元素等價（違反唯一性），插入失敗
}
2) 僅更新指向?qū)ο蟮?ldquo;值”（不改變地址）
如果你不更換 unique_ptr 本身，只是修改它指向的 int 的數(shù)值（地址不變），就不會影響排序，可在常量迭代器上做“邏輯修改”前需要去除 const：
- 標(biāo)準(zhǔn)不允許通過
const_iterator直接修改元素；但你可以用const_cast<int&>(*ptr)或?qū)⒌鬓D(zhuǎn)換為非常量迭代器（C++23 提供了const_iterator到iterator的mutable_iterator轉(zhuǎn)換；更通用辦法是先通過查找得到非 const 迭代器）。
簡化起見，建議：提取 node 后修改再插回，語義最清晰。
D. Delete（刪除）
// 1) 迭代器刪除
if (!s.empty()) {
s.erase(s.begin());
}
// 2) 按異質(zhì)鍵刪除（Timestamp + 地址）
Timestamp t{100};
const int* addr = /*...*/;
s.erase(std::pair<Timestamp, const int*>{t, addr});
// 3) 按時間戳范圍刪除
s.erase(s.lower_bound(Timestamp{100}), s.lower_bound(Timestamp{130}));
5) 典型陷阱與建議
臨時
unique_ptr作為查找鍵：千萬不要用find({ts, std::unique_ptr<int>(raw)})查找，臨時unique_ptr析構(gòu)時會delete raw，導(dǎo)致雙重釋放。請使用透明比較器 + 原始指針地址的異質(zhì)查找。修改鍵值破壞有序性：在容器中直接改
Timestamp或把unique_ptr換成另一塊地址，都會破壞樹的排序假設(shè)。務(wù)必用extract→修改→insert。語義核對：
unique_ptr的比較是按地址而非按“指向內(nèi)容”。如果你想讓“同一Timestamp+ 相同內(nèi)容（例如*ptr）才算相等，需要自定義比較器改成按*ptr值比較（并處理空指針）。標(biāo)準(zhǔn)版本：
- C++17 起：有
node_handle、更明確的對僅移動鍵（如unique_ptr）的支持。強(qiáng)烈建議使用 C++17+。 - 透明比較器用法在 C++14 就可行（
is_transparent習(xí)慣用法），但與 node handle 結(jié)合最順暢的是 C++17+。
- C++17 起：有
6) 小結(jié)（要點(diǎn)清單）
std::set：自動排序、唯一性、紅黑樹、O(log N)。pair<Timestamp, unique_ptr<int>>的默認(rèn)字典序比較可用：先Timestamp，再指針地址。- 由于
unique_ptr是僅移動類型：用emplace/insert(std::move)；查找應(yīng)使用透明比較器 + 原始指針地址的異質(zhì)查找，不要構(gòu)造臨時unique_ptr。 - 更新鍵請走
extract→修改→insert；修改指向?qū)ο髢?nèi)容不改變地址，一般不破壞排序。 - 若你的業(yè)務(wù)語義不是“按地址”，請自定義比較器（例如比較
*ptr的值，或僅比較Timestamp）。 - 建議 C++17+（為
node_handle與僅移動鍵的良好支持）。
完整最小示例（可直接參考）
#include <set>
#include <memory>
#include <utility>
#include <iostream>
class Timestamp {
int secondsFromEpoch_;
public:
explicit Timestamp(int s = 0) : secondsFromEpoch_(s) {}
int seconds() const noexcept { return secondsFromEpoch_; }
friend bool operator<(const Timestamp& a, const Timestamp& b) noexcept {
return a.secondsFromEpoch_ < b.secondsFromEpoch_;
}
};
using Key = std::pair<Timestamp, std::unique_ptr<int>>;
struct PairCmp {
using is_transparent = void;
bool operator()(const Key& a, const Key& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second.get(), b.second.get());
}
bool operator()(const Key& a, const std::pair<Timestamp, const int*>& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second.get(), b.second);
}
bool operator()(const std::pair<Timestamp, const int*>& a, const Key& b) const noexcept {
if (a.first < b.first) return true;
if (b.first < a.first) return false;
return std::less<const int*>{}(a.second, b.second.get());
}
bool operator()(const Key& a, const Timestamp& t) const noexcept { return a.first < t; }
bool operator()(const Timestamp& t, const Key& b) const noexcept { return t < b.first; }
};
using PairSet = std::set<Key, PairCmp>;
int main() {
PairSet s;
// Create
auto [it1, ok1] = s.emplace(Timestamp{100}, std::make_unique<int>(42));
auto [it2, ok2] = s.emplace(Timestamp{100}, std::make_unique<int>(7));
s.emplace(Timestamp{120}, std::make_unique<int>(99));
// Read: find by (Timestamp, raw pointer)
const int* addr = it1->second.get();
auto it = s.find(std::pair<Timestamp, const int*>{Timestamp{100}, addr});
if (it != s.end()) {
std::cout << "Found ts=" << it->first.seconds() << " val=" << *it->second << "\n";
}
// Read: range by timestamp
std::cout << "ts==100:\n";
for (auto p = s.lower_bound(Timestamp{100}); p != s.upper_bound(Timestamp{100}); ++p) {
std::cout << " " << p->first.seconds() << " -> " << *p->second << "\n";
}
// Update: extract -> modify -> insert
if (it2 != s.end()) {
auto nh = s.extract(it2); // 取出節(jié)點(diǎn)
nh.value().first = Timestamp{105}; // 改鍵(時間戳)
nh.value().second = std::make_unique<int>(555); // 換指針(地址變)
s.insert(std::move(nh)); // 重新插入
}
// Delete: by heterogeneous key
s.erase(std::pair<Timestamp, const int*>{Timestamp{100}, addr});
// 遍歷
for (const auto& [ts, ptr] : s) {
std::cout << ts.seconds() << " -> " << (ptr ? *ptr : -1) << "\n";
}
}
到此這篇關(guān)于C++ std::Set＜std::pair＞的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)C++ std::Set＜std::pair＞內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了C++11 上下文關(guān)鍵字的具體實(shí)踐，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
VC中實(shí)現(xiàn)GB2312、BIG5、Unicode編碼轉(zhuǎn)換的方法
這篇文章主要介紹了VC中實(shí)現(xiàn)GB2312、BIG5、Unicode編碼轉(zhuǎn)換的方法,該功能非常實(shí)用,需要的朋友可以參考下2014-07-07
C/C++淺析鄰接表拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)
這篇文章主要介紹了C/C++對于鄰接表拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)，鄰接表是圖的一種鏈?zhǔn)酱鎯Ψ椒?，其?shù)據(jù)結(jié)構(gòu)包括兩部分：節(jié)點(diǎn)和鄰接點(diǎn)2022-07-07
回調(diào)函數(shù)就是一個通過函數(shù)指針調(diào)用的函數(shù)。如果你把函數(shù)的指針（地址）作為參數(shù)傳遞給另一個函數(shù)，當(dāng)這個指針被用為調(diào)用它所指向的函數(shù)時，我們就說這是回調(diào)函數(shù)2013-10-10
C++實(shí)現(xiàn)完整功能的通訊錄管理系統(tǒng)詳解
來了來了，通訊錄管理系統(tǒng)踏著七彩祥云飛來了，結(jié)合前面的結(jié)構(gòu)體知識和分文件編寫方法，我總結(jié)并碼了一個帶菜單的通訊錄管理系統(tǒng)，在這篇文章中將會提到C的清空屏幕函數(shù)，嵌套結(jié)構(gòu)體具體實(shí)現(xiàn)，簡單且充實(shí)，跟著我的思路，可以很清晰的解決這個項目2022-05-05
C++?qsort函數(shù)排序與冒泡模擬實(shí)現(xiàn)流程詳解
qsort是一個庫函數(shù),基于快速排序算法實(shí)現(xiàn)的一個排序的函數(shù),下面這篇文章主要給大家介紹了關(guān)于C語言qsort()函數(shù)使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-10-10
關(guān)于C++中sort()函數(shù)的用法,你搞明白了沒
這篇文章主要介紹了關(guān)于C++中sort()函數(shù)的用法,并通過三種方法介紹了按降序排列的實(shí)現(xiàn)代碼，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03
今天小編就為大家分享一篇opencv3/C++繪制幾何圖形實(shí)例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡單迷宮游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
在C++的Template中我們經(jīng)?？梢砸姷绞褂胻ypename來定義類型名稱,更加具體的我們就在接下來為大家詳解C++的模板中typename關(guān)鍵字的用法,需要的朋友可以參考下:2016-06-06