为什么insert invalidate std :: set reverse iterator [英] Why does insert invalidate the std::set reverse iterator

问题描述

我的理解是关联容器的迭代器不会在插入或擦除期间无效（除非迭代器指向的节点被擦除）。但在下面的程序
插入看起来无效的迭代器。我的理解是否错误？

===

  typedef std： ：set< unsigned int> myset_t; 
 
 int main（int argc，char ** argv）
 {
 myset_t rs; 
 myset_t :: reverse_iterator rit; 
 myset_t :: reverse_iterator srit; 
 int ii = 500; 
 
 rs.insert（10）; 
 rs.insert（11）; 
 rs.insert（12）; 
 rs.insert（13） 
 rs.insert（14）; 
 rs.insert（100000）; 
 rs.insert（102000）; 
 rs.insert（103000）; 
 
 rit = rs.rbegin（）; 
 
 while（rit！= rs.rend（））{
 srit = rit; 
 if（* rit< 100000）{
 cout<< bailing here< * rit<< endl; 
 return 0; 
} 
 rit ++; 
 cout<< 擦除前<< * rit<< endl; 
 rs.erase（* srit）; 
 cout<< Before insert<< * rit<< endl; 
 rs.insert（ii）; 
 cout<< 插入后<< * rit<< endl; 
 ii ++; 
} 
 cout<< 环路外<< endl; 
} 
 === 
 
输出为
删除前102000 
插入前102000 
插入后14 
 14 
 
 ===== 
  

解决方案

标准容器的迭代器的承诺行为对该容器的反向迭代器不适用。

反向迭代器实际上存储了正常向前移动）迭代器，它在反向迭代器引用的元素之后 之后。然后，当你解引用反向迭代器，本质上它减少这个存储的正常迭代器的副本，并解除引用。所以这是一个问题：

  rit = rs.rbegin（）; // rit stores rs.end（）
 srit = rit; // srit也存储rs.end（）
 rit ++; // rit存储指向最后一个元素的正常迭代器
 
 rs.erase（* srit）; //这将删除最后一个元素，使存储在rit中的正则
 //迭代器无效。有趣的是，存储在srit中的
 //仍然有效，但现在* srit是一个
 //不同的值
  

反向迭代器的行为是这样的，因为没有before begin迭代器。如果他们将迭代器存储到他们实际引用的元素， rs.rend（）存储？我肯定有这方面的方法，但我想他们需要妥协，标准委员会不愿意。或者他们从来没有考虑过这个问题，或者没有考虑这个问题。

My understanding is the iterators of associative containers are not invalidated during insert or erase (unless the node pointed by iterator is erased). But in the below program the insert seems to invalidate the iterator. Is my understanding wrong?

===

typedef std::set<unsigned int> myset_t;

int main(int argc, char **argv)
{
    myset_t rs;
    myset_t::reverse_iterator rit;
    myset_t::reverse_iterator srit;
    int ii = 500;

    rs.insert(10);
    rs.insert(11);
    rs.insert(12);
    rs.insert(13);
    rs.insert(14);
    rs.insert(100000);
    rs.insert(102000);
    rs.insert(103000);

    rit = rs.rbegin();

    while(rit != rs.rend()) {
        srit = rit;
        if (*rit < 100000) {
            cout << "bailing here " << *rit << endl;
            return 0;
        } 
        rit++;
        cout << "Before erase " << *rit << endl;
        rs.erase(*srit);
        cout << "Before insert " << *rit << endl;
        rs.insert(ii);
        cout << "After insert " << *rit << endl;
        ii++;
    }
    cout << "Out of loop" << endl;
}
===

The output is 
Before erase 102000
Before insert 102000
After insert 14
bailing here 14

=====

解决方案

The promised behavior for iterators of a standard container does not hold for reverse iterators of that container.

A reverse iterator actually stores, as a member, the normal (forward moving) iterator which comes after the element to which the reverse iterator refers when dereferenced. Then when you dereference the reverse iterator, essentially it decrements a copy of this stored normal iterator and dereferences that. So this is a problem:

rit = rs.rbegin();     // rit stores rs.end()
srit = rit;            // srit also stores rs.end()
rit++;                 // rit stores a normal iterator pointing to the last element

rs.erase(*srit);       // this deletes the last element, invalidating the normal
                       // iterator which is stored in rit. Funnily enough, the
                       // one stored in srit remains valid, but now *srit is a
                       // different value

Reverse iterators behave this way because there is no "before begin" iterator. If they stored the iterator to the element to which they actually refer, what would rs.rend() store? I'm sure there are ways around this, but I guess they required compromises which the standards committee was not willing to make. Or perhaps they never considered this problem, or didn't consider it significant enough.

这篇关于为什么insert invalidate std :: set reverse iterator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！