C++中是否存在等价于Java TreeSet的STL结构及lower、higher方法实现

当然有啦！C++标准库中的std::set就和Java的TreeSet是完全等价的——两者都是基于红黑树实现的有序集合，默认按升序存储元素，而且都支持O(log n)时间复杂度的查找、插入、删除操作，完全能满足你的需求。

针对你需要的lower(i)（返回恰好小于i的元素）和higher(i)（返回恰好大于i的元素）功能，我们可以用std::set的lower_bound和upper_bound方法来实现，下面结合你给出的示例代码一步步说明：

首先先完成集合的初始化：

#include <iostream>
#include <set>

int main() {
    std::set<int> myset;
    for (int i = 1; i < 10; i++) {
        myset.insert(i * 10); // 插入后集合元素为：10,20,30,40,50,60,70,80,90
    }
    int k = 50; // 目标元素，需要获取它的前一个（40）和后一个（60）

1. 获取恰好小于k的元素（对应Java TreeSet的lower(k)） #

std::set::lower_bound(k)会返回第一个不小于k的元素的迭代器，在这个例子里就是指向50的迭代器。我们只需要把这个迭代器往前移动一位，就能得到恰好小于k的元素：

// 实现类似lower(k)的功能
    auto it_less = myset.lower_bound(k);
    if (it_less != myset.begin()) {
        --it_less;
        std::cout << "恰好小于" << k << "的元素是：" << *it_less << std::endl; // 输出40
    } else {
        std::cout << "集合中没有小于" << k << "的元素" << std::endl;
    }

这里要注意判断迭代器是否为begin()，如果是的话说明集合里所有元素都不小于k，没有符合条件的元素。

2. 获取恰好大于k的元素（对应Java TreeSet的higher(k)） #

std::set::upper_bound(k)直接返回第一个大于k的元素的迭代器，刚好对应Java里的higher(k)：

// 实现类似higher(k)的功能
    auto it_greater = myset.upper_bound(k);
    if (it_greater != myset.end()) {
        std::cout << "恰好大于" << k << "的元素是：" << *it_greater << std::endl; // 输出60
    } else {
        std::cout << "集合中没有大于" << k << "的元素" << std::endl;
    }

    return 0;
}

同样要判断迭代器是否为end()，如果是的话说明集合里没有比k大的元素。

最后给你梳理下对应关系：

• Java TreeSet的lower(i) → C++ std::set：调用lower_bound(i)后，若迭代器不是开头则前移一位
• Java TreeSet的higher(i) → C++ std::set：直接调用upper_bound(i)

内容的提问来源于stack exchange，提问作者Batwoman05