之前有一些关于这个问题的问题; 我的理解是,调用std::vector::erase只会使处于擦除元素之后的位置的迭代器无效.但是,在擦除元素之后,该位置的迭代器是否仍然有效(当然,前提是它end()在擦除后没有指向)？
我对如何实现向量的理解似乎表明迭代器肯定是可用的,但我不完全确定它是否会导致未定义的行为.
作为我正在谈论的一个例子,下面的代码从向量中删除所有奇数整数.此代码是否会导致未定义的行为？
typedef std::vector<int> vectype;
vectype vec;
for (int i = 0; i < 100; ++i) vec.push_back(i);
vectype::iterator it = vec.begin();
while (it != vec.end()) {
if (*it % 2 == 1) vec.erase(it);
else ++it;
}
代码在我的机器上正常运行,但这并不能说服它是有效的.
最近我一直在研究Patricia尝试,并使用一个非常好的C++实现,可以用作STL Sorted Associative Container.Patricia尝试与普通二叉树不同,因为叶节点具有指向内部节点的后向指针.尽管如此,如果您只通过叶节点后向指针访问内部节点,则可以通过执行有序遍历来按字母顺序遍历Patricia trie.
这让我想到了一个问题:是否可以用Patricia trie 实现STL lower_bound和upper_bound功能？我使用的实施确实事实上,实现这些功能,但预计他们不工作.
例如:
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
这会输出BLQ,当我希望它输出HCDA时.(std::set例如,肯定会在这里输出HCDA.)
我通过电子邮件发送了制作此库的开发人员,但从未收到回复.无论如何,我觉得我非常了解Patricia如何尝试工作,我无法弄清楚low_bound之类的东西是如何可行的.问题是lower_bound似乎依赖于按字母顺序比较两个字符串的能力.由于树中不存在"GG",我们需要找出哪个元素> =到GG.但Radix/Patricia尝试不使用词典比较从一个节点移动到另一个节点; 而是每个节点存储一个比特索引,用于对搜索关键字进行比特比较.位比较的结果告诉您是向左还是向右移动.这样可以很容易地在树中找到特定的前缀.但是如果树中不存在前缀,
我正在使用的C++实现似乎没有正确实现lower_bound的事实证实了我怀疑它可能是不可能的.尽管如此,你可以按字母顺序迭代树,这让我觉得可能有办法做到这一点.
有没有人有这方面的经验,或者知道是否可以用Patricia Trie实现lower_bound功能？