c++ - 侵入式 rbtree 中第一个元素的恒定时间测试

Question

如何有效判断元素是否位于侵入集或 rbtree 的开头？我想定义一个简单的函数 prev 返回指向树中前一项的指针，如果没有前一项则返回 nullptr 。类似的 next 函数很容易编写，使用 iterator_to 并与 end() 进行比较。但是，没有等效的 reverse_iterator_to 函数可以让我与 rend() 进行比较。此外，我特别不想与 begin() 进行比较，因为这在红黑树中不是常数时间。

似乎确实可行的一件事是递减迭代器并将其与 end() 进行比较。这在实现中效果很好，但我在文档中找不到对此的支持。在以下最小工作示例中实现 prev 的最佳方法是什么？

#include <iostream>
#include <string>
#include <boost/intrusive/set.hpp>

using namespace std;
using namespace boost::intrusive;

struct foo : set_base_hook<> {
  string name;
  foo(const char *n) : name(n) {}
  friend bool operator<(const foo &a, const foo &b) { return a.name < b.name; }
};

rbtree<foo> tree;

foo *
prev(foo *fp)
{
  auto fi = tree.iterator_to(*fp);
  return --fi == tree.end() ? nullptr : &*fi;
}

int
main()
{
  tree.insert_equal(*new foo{"a"});
  tree.insert_equal(*new foo{"b"});
  tree.insert_equal(*new foo{"c"});
  for (foo *fp = &*tree.find("c"); fp; fp = prev(fp))
    cout << fp->name << endl;
}

更新: 好的，所以我遗漏的是，在 STL 中，begin() 实际上保证是恒定时间的，这可能是 sehe 间接得到的。因此，即使通用红黑树需要 log(n) 时间来找到最小元素，STL 映射却不需要——需要 STL std::map 实现来缓存第一个元素。我认为 sehe 的意思是，即使没有记录 boost，也可以公平地假设 boost::intrusive 容器的行为有点像 STL 容器。鉴于该假设，完全可以说:

foo *
prev(foo *fp)
{
  auto fi = tree.iterator_to(*fp);
  return fi == tree.begin() ? nullptr : &*--fi;
}

因为与 tree.begin() 的比较应该不会太昂贵。

Answer 1

你可以从 iterator_to 得到反向迭代器.

Also, note that there is rbtree<>::container_from_iterator(iterator it) so you don't have to have a "global" state for your prev function.

---

您只需创建相应的 reverse_iterator 即可。您必须 +1 迭代器才能获得预期的地址:

所以我对此的看法是(好处:没有内存泄漏):

Live On Coliru

#include <boost/intrusive/set.hpp>
#include <iostream>
#include <string>
#include <vector>

using namespace boost::intrusive;

struct foo : set_base_hook<> {
    std::string name;
    foo(char const* n) : name(n) {}

    bool operator<(const foo &b) const { return name < b.name; }
};

int main()
{
    std::vector<foo> v;
    v.emplace_back("a");
    v.emplace_back("b");
    v.emplace_back("c");

    using Tree = rbtree<foo>;

    Tree tree;
    tree.insert_unique(v.begin(), v.end());

    for (auto key : { "a", "b", "c", "missing" })
    {
        std::cout << "\nusing key '" << key << "': ";
        auto start = tree.iterator_to(*tree.find(key));

        if (start != tree.end()) {
            for (auto it = Tree::reverse_iterator(++start); it != tree.rend(); ++it)
                std::cout << it->name << " ";
        }
    }
}

哪个打印

using key 'a': a 
using key 'b': b a 
using key 'c': c b a 
using key 'missing':