Nat*_*iel 5 c++ iterator set data-structures
std::set如果它指向的项被删除,则迭代器变为无效.(如果以任何其他方式修改集合,它不会失效,这很好.)但是,无法检测迭代器是否已失效.
我正在实现一种算法,要求我能够以std::set这样的方式跟踪a的成员,以便我可以在恒定的时间内擦除它们,但如果我尝试删除相同的两次,则不会冒未定义的行为的风险.如果我有两个指向同一个成员的迭代器set,那么如果我试图擦除它们,就会发生坏事.
我的问题是,我该如何避免这种情况？有没有办法实现像迭代器一样的东西set,但是它知道什么时候它已经失效？
顺便说一句,我正在使用,std::set因为这是一个性能危急的情况,我需要set提供的复杂性保证.我很乐意接受建议不同数据结构的答案,但前提是它允许我(a)在恒定时间内访问和删除最小元素,(b)在恒定时间内删除指向元素,并且(c) )在O(log(N))时间或更好的时间插入元素.C++ 11没问题.