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

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

treeset set data-structures c++ java

Batwoman05 · 技术社区 · 6 年前

我需要在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 回复 | 直到 6 年前

gsamaras 6 年前

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

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

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

Daniel 6 年前

您可以使用 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

推荐文章

patrick · 从boost::绑定1和2占位符运行make失败。。。?

1 年前

rookie · 检查函数模板的所有参数包参数是否属于int

1 年前

ivaigult · -W转换和隐式字符串到布尔类型转换

1 年前

David Bien · declval<_Xp(&)()>()()-这在下面的上下文中意味着什么?

1 年前

khallad sayed · 在%上,C++表达式必须具有整型或无范围枚举类型

1 年前

rainer · 后台插入程序的初始化

1 年前

Community wiki · 以理智、安全和高效的方式复制文件

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Prakritish Ghosh · 现在显示正确输出的函数中的Infix到Postfix错误[重复]

1 年前

Ma Joonyoung · 粗粒度和细粒度链表的时间比较

1 年前