C++ std::Set＜std::pair＞的實(shí)現(xiàn)示例

更新時(shí)間：2025年10月21日 09:17:24 作者：全體目光向我看齊

本文主要介紹了C++ std::Set＜std::pair＞的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1)std::set的三個(gè)關(guān)鍵特性

元素自動(dòng)排序：std::set 始終按嚴(yán)格弱序（默認(rèn) std::less<Key> 的字典序）維持有序，常見操作（插入、查找、上下界）復(fù)雜度均為 O(log N)。
元素不允許重復(fù)：比較器認(rèn)為“等價(jià)”的元素不能共存（即 !(a<b) && !(b<a) 為真時(shí)視為等價(jià)）。
基于紅黑樹實(shí)現(xiàn)：標(biāo)準(zhǔn)庫通常采用紅黑樹；因此“有序 + 查找高效”是它相對(duì) unordered_set 的顯著特征。

2) 關(guān)于比較：Timestamp與std::unique_ptr<int>能否比較？

Timestamp：你給出的成員是 private int secondsFromEpoch。要參與排序，必須為 Timestamp 提供可用的嚴(yán)格弱序比較（通常實(shí)現(xiàn) operator< 或在比較器內(nèi)訪問一個(gè) getter()）。
std::unique_ptr<int>：
- 標(biāo)準(zhǔn)提供了與同類 unique_ptr 的關(guān)系運(yùn)算符（<、<=、>、>=、==、!=），其比較語義是按底層指針地址比較（實(shí)現(xiàn)上等價(jià)于 std::less<int*>{}(p.get(), q.get())）。
- 注意：這不是按指向的“整數(shù)值”比較，而是按地址。如果你的業(yè)務(wù)語義是“同時(shí)間戳 + 指針指向的值也相等才算相等/有序”，地址比較可能不符合預(yù)期。
- 結(jié)論：可以比較，但“比較的是地址而非內(nèi)容”。

字典序：std::pair<A,B> 的默認(rèn) < 比較是先比較 first，若相等再比較 second。因此在 std::set<std::pair<Timestamp, std::unique_ptr<int>>> 中：

先比較 Timestamp；
Timestamp 相等時(shí)，再比較 unique_ptr<int> 的地址。

3) 自定義透明比較器（heterogeneous lookup）

直接用 pair<Timestamp, unique_ptr<int>> 做鍵會(huì)遇到查找難題：

你不能構(gòu)造一個(gè)臨時(shí) unique_ptr<int> 作為查找鍵的第二分量（會(huì)產(chǎn)生錯(cuò)誤的所有權(quán)，臨時(shí)對(duì)象析構(gòu)時(shí)會(huì)delete 它指向的地址，造成雙重釋放風(fēng)險(xiǎn)）。
正確姿勢(shì)是用透明比較器支持“用 (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。請(qǐng)先看類型與比較器。

#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（按字典序：先時(shí)間戳，再指針地址）
    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)容器，可無拷貝插入僅移動(dòng)類型（如 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));   // 與上一個(gè)可共存：時(shí)間戳相同但地址不同
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)造臨時(shí) 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) 按時(shí)間戳做范圍/等值查找

// 所有 timestamp == 100 的區(qū)間：
auto rng = s.equal_range(Timestamp{100}); // 依賴我們?cè)诒容^器中提供的 (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 的地址）。否則會(huì)破壞紅黑樹不變量。
正確做法：使用 node handle（C++17）進(jìn)行“摘除-修改-再插入”。

1) 修改Timestamp或替換unique_ptr（地址會(huì)變）

// 找到一個(gè)元素
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};                  // 改時(shí)間戳
    nh.value().second = std::make_unique<int>(555);     // 新指針（地址變化）
    // 3) 重新插入
    auto [pos, ok] = s.insert(std::move(nh));
    // ok==false 表示與現(xiàn)有元素等價(jià)（違反唯一性），插入失敗
}

2) 僅更新指向?qū)ο蟮?ldquo;值”（不改變地址）

如果你不更換 unique_ptr 本身，只是修改它指向的 int 的數(shù)值（地址不變），就不會(huì)影響排序，可在常量迭代器上做“邏輯修改”前需要去除 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 迭代器）。

簡(jiǎn)化起見，建議：提取 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) 按時(shí)間戳范圍刪除
s.erase(s.lower_bound(Timestamp{100}), s.lower_bound(Timestamp{130}));

5) 典型陷阱與建議

臨時(shí) unique_ptr 作為查找鍵：千萬不要用 find({ts, std::unique_ptr<int>(raw)}) 查找，臨時(shí) unique_ptr 析構(gòu)時(shí)會(huì) delete raw，導(dǎo)致雙重釋放。請(qǐng)使用透明比較器 + 原始指針地址的異質(zhì)查找。
修改鍵值破壞有序性：在容器中直接改 Timestamp 或把 unique_ptr 換成另一塊地址，都會(huì)破壞樹的排序假設(shè)。務(wù)必用 extract→修改→insert。
語義核對(duì)：unique_ptr 的比較是按地址而非按“指向內(nèi)容”。如果你想讓“同一 Timestamp + 相同內(nèi)容（例如 *ptr）才算相等，需要自定義比較器改成按 *ptr 值比較（并處理空指針）。
標(biāo)準(zhǔn)版本：
- C++17 起：有 node_handle、更明確的對(duì)僅移動(dòng)鍵（如 unique_ptr）的支持。強(qiáng)烈建議使用 C++17+。
- 透明比較器用法在 C++14 就可行（is_transparent 習(xí)慣用法），但與 node handle 結(jié)合最順暢的是 C++17+。

6) 小結(jié)（要點(diǎn)清單）

std::set：自動(dòng)排序、唯一性、紅黑樹、O(log N)。
pair<Timestamp, unique_ptr<int>> 的默認(rèn)字典序比較可用：先 Timestamp，再指針地址。
由于 unique_ptr 是僅移動(dòng)類型：用 emplace/insert(std::move)；查找應(yīng)使用透明比較器 + 原始指針地址的異質(zhì)查找，不要構(gòu)造臨時(shí) unique_ptr。
更新鍵請(qǐng)走 extract→修改→insert；修改指向?qū)ο髢?nèi)容不改變地址，一般不破壞排序。
若你的業(yè)務(wù)語義不是“按地址”，請(qǐng)自定義比較器（例如比較 *ptr 的值，或僅比較 Timestamp）。
建議 C++17+（為 node_handle 與僅移動(dòng)鍵的良好支持）。

完整最小示例（可直接參考）

#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};               // 改鍵(時(shí)間戳)
        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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: