代码之家 › 专栏 › 技术社区 › Batwoman05

C++中是否有具有类似函数的树集数据结构

treeset set data-structures c++ java

Batwoman05 · 技术社区 · 7 年前

我需要在C++中使用树集数据结构(java中可用),并使用TreeSet之类的函数。下(i)和树集。更高(i)->它返回的元素比给定树集中的i低,也比i高。是否有STL?

编辑: 以下是我需要的功能,我想知道如何使用上限和下限函数来实现它:

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
}

3 回复 | 直到 7 年前

gsamaras a Data Head 7 年前

使用 std::set ,它通常实现为二进制搜索树。

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

我想你应该对 std::lower_bound ,它将迭代器返回到下限,并在 std::upper_bound ,它将迭代器返回到上限。

Daniel 7 年前

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

chirag garg 4 年前

您可以在此处使用std::set。对于您的功能,您可以使用函数上限(i)和下限(i),但这里需要注意的是,它们的工作方式与TreeSet不同。下(i)和树集。更高(i)。

下限(常数i) –将迭代器返回到容器中第一个元素,该元素被认为不在i之前(即,它是等价的或在i之后),或者如果所有元素都被认为在i之前,则返回set::end。

上限(常数i) –将迭代器返回到容器中被视为在i之后的第一个元素,如果没有元素被视为在i之后,则返回set::end。

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

推荐文章

Codeforces Fan · 如何在c中的STL集合中添加lambda函数或执行自定义操作++

2 年前

tryingmybest09 · 设置出生日期排序不正确

2 年前

David · 在c++中,将集合的向量创建为类成员会产生错误[重复]

7 年前