C++ std::Set＜std::pair＞的实现示例_C/C++

1)std::set的三个关键特性

元素自动排序：std::set 始终按严格弱序（默认 std::less<key> 的字典序）维持有序，常见操作（插入、查找、上下界）复杂度均为 o(log n)。
元素不允许重复：比较器认为“等价”的元素不能共存（即 !(a<b) && !(b<a) 为真时视为等价）。
基于红黑树实现：标准库通常采用红黑树；因此“有序 + 查找高效”是它相对 unordered_set 的显著特征。

2) 关于比较：timestamp与std::unique_ptr<int>能否比较？

timestamp：你给出的成员是 private int secondsfromepoch。要参与排序，必须为 timestamp 提供可用的严格弱序比较（通常实现 operator< 或在比较器内访问一个 getter()）。
std::unique_ptr<int>：
- 标准提供了与同类 unique_ptr 的关系运算符（<、<=、>、>=、==、!=），其比较语义是按底层指针地址比较（实现上等价于 std::less<int*>{}(p.get(), q.get())）。
- 注意：这不是按指向的“整数值”比较，而是按地址。如果你的业务语义是“同时间戳 + 指针指向的值也相等才算相等/有序”，地址比较可能不符合预期。
- 结论：可以比较，但“比较的是地址而非内容”。

字典序：std::pair<a,b> 的默认 < 比较是先比较 first，若相等再比较 second。因此在 std::set<std::pair<timestamp, std::unique_ptr<int>>> 中：

先比较 timestamp；
timestamp 相等时，再比较 unique_ptr<int> 的地址。

3) 自定义透明比较器（heterogeneous lookup）

直接用 pair<timestamp, unique_ptr<int>> 做键会遇到查找难题：

你不能构造一个临时 unique_ptr<int> 作为查找键的第二分量（会产生错误的所有权，临时对象析构时会delete 它指向的地址，造成双重释放风险）。
正确姿势是用透明比较器支持“用 (timestamp, const int*) 这类异质键进行查找”，从而无需构造 unique_ptr。

透明比较器（具备 using is_transparent = void;）允许 set.find / erase / lower_bound 等直接用可比较但类型不同的键（如 const int*）进行 o(log n) 查找。

4) crud 规范做法（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_; }
    // 定义严格弱序（仅按秒比较）
    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*) 这种异质键的比较与查找 ==========
struct paircmp {
    using is_transparent = void; // 启用异质查找

    // 基本：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());
    }

    // 异质：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 的异质比较（用于范围查询）
    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 是节点容器，可无拷贝插入仅移动类型（如 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) 先构造 key 再 move
key k{ timestamp{130}, std::make_unique<int>(123) };
s.insert(std::move(k)); // k.second 置空

要点：

如果你希望“相同 timestamp 只允许一条记录”，就不要把 unique_ptr 纳入比较；而应改用“仅比较 timestamp”的比较器（见 §7 变体方案）。

b. read（查询/遍历）

1) 按（timestamp, 指针地址）精确查找

利用透明比较器，避免构造临时 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 的区间：
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）进行“摘除-修改-再插入”。

1) 修改timestamp或替换unique_ptr（地址会变）

// 找到一个元素
auto it = s.lower_bound(timestamp{100});
if (it != s.end() && it->first.seconds() == 100) {
    // 1) extract 节点，容器不再管理平衡关系中的该节点
    auto nh = s.extract(it);       // node_handle，拥有该 pair 的完整所有权
    // 2) 修改 key 内容（注意：任何影响排序的字段都只能在 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 表示与现有元素等价（违反唯一性），插入失败
}

2) 仅更新指向对象的“值”（不改变地址）

如果你不更换 unique_ptr 本身，只是修改它指向的 int 的数值（地址不变），就不会影响排序，可在常量迭代器上做“逻辑修改”前需要去除 const：

标准不允许通过 const_iterator 直接修改元素；但你可以用 const_cast<int&>(*ptr) 或将迭代器转换为非常量迭代器（c++23 提供了 const_iterator 到 iterator 的 mutable_iterator 转换；更通用办法是先通过查找得到非 const 迭代器）。

简化起见，建议：提取 node 后修改再插回，语义最清晰。

d. delete（删除）

// 1) 迭代器删除
if (!s.empty()) {
    s.erase(s.begin());
}

// 2) 按异质键删除（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 析构时会 delete raw，导致双重释放。请使用透明比较器 + 原始指针地址的异质查找。
修改键值破坏有序性：在容器中直接改 timestamp 或把 unique_ptr 换成另一块地址，都会破坏树的排序假设。务必用 extract→修改→insert。
语义核对：unique_ptr 的比较是按地址而非按“指向内容”。如果你想让“同一 timestamp + 相同内容（例如 *ptr）才算相等，需要自定义比较器改成按 *ptr 值比较（并处理空指针）。
标准版本：
- c++17 起：有 node_handle、更明确的对仅移动键（如 unique_ptr）的支持。强烈建议使用 c++17+。
- 透明比较器用法在 c++14 就可行（is_transparent 习惯用法），但与 node handle 结合最顺畅的是 c++17+。

6) 小结（要点清单）

std::set：自动排序、唯一性、红黑树、o(log n)。
pair<timestamp, unique_ptr<int>> 的默认字典序比较可用：先 timestamp，再指针地址。
由于 unique_ptr 是仅移动类型：用 emplace/insert(std::move)；查找应使用透明比较器 + 原始指针地址的异质查找，不要构造临时 unique_ptr。
更新键请走 extract→修改→insert；修改指向对象内容不改变地址，一般不破坏排序。
若你的业务语义不是“按地址”，请自定义比较器（例如比较 *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);                        // 取出节点
        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";
    }
}

到此这篇关于c++ std::set＜std::pair＞的实现示例的文章就介绍到这了,更多相关c++ std::set＜std::pair＞内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

C++ std::Set＜std::pair＞的实现示例

2025年10月21日 • C/C++ •我要评论