在 C++ 中是否有一个具有类似功能的 TreeSet 数据结构？

Question

我需要在 C++ 中使用树集数据结构（在 java 中可用），并使用像 TreeSet.lower(i) 和 TreeSet.higher(i) 这样的函数 - > which returns 该元素在给定的树集中比 i 低，且比 i 高。有STL吗？

编辑：以下是我需要的功能，我想知道如何使用 upper_bound 和 lower_bound 函数来实现：

for (int i = 1; i<10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
int k = 50;  // I need 40 and 60
set<int>::iterator itr = myset.find(k);

if (itr != myset.end()) {
    // Found the element
    itr--; // Previous element;
    cout << *(itr); //prints 40
    itr++; // the element found
    itr++; // The next element
    cout << *(itr);  // prints 60
}

Answer 1

您可以使用std::set
查看 std::set::lower_bound 和 std::set::upper_bound

Answer 2

使用 std::set，它通常作为二叉搜索树实现。

它的insert()、erase()和find()方法的大小是对数的，但如果给出提示可以做得更好。对数复杂度参考 Java TreeSet.

我想你应该对 std::lower_bound, which returns an iterator to the lower bound, and in std::upper_bound 感兴趣，它 returns 一个迭代器到上界。

Answer 3

你可以在这里使用std::set。对于您的功能，您可以使用函数 upper_bound(i) 和 lower_bound(i) 但要注意的是它们的工作方式与 TreeSet.lower(i) 和 TreeSet.higher 不同(i).

lower_bound(const i) – Returns 容器中第一个元素的迭代器，该元素不被认为在 i 之前（即, 要么等价要么在之后), 或者 set::end 如果所有元素都被认为在 i.

之前

upper_bound(const i) – Returns 容器中第一个被认为在 i 之后的元素的迭代器，或者 set::end 如果没有元素被认为在 i 之后。

for (int i = 1; i<10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
int k = 50; 
set<int>::iterator itlow,itup;

itlow=myset.lower_bound (k);  
itup=myset.upper_bound (k);

if(itlow!=myset.begin()){
   itlow--;
   cout << *itlow;  // 40 will print
}
cout << *itup;  // 60 will print

在 C++ 中是否有一个具有类似功能的 TreeSet 数据结构？

Is there a TreeSet data structure equivalent in C++ with similar functions

c++

java

set

treeset

data-structures