stl实现插入排序的有关问题

stl实现插入排序的问题

C/C++ code


template <class T> void InsertSort(vector<T>& v) //插入排序
{
    vector<T> temp;
    typedef vector<T>::iterator VI;
    temp.push_back(v[0]);
    
    for (VI i = v.begin()+1;i<v.end();++i)
    {        
        for (VI j = temp.end()-1;j>=temp.begin();--j)
        {        
            if ((*i)>=(*j))
            {
                temp.insert(j+1,(*i));
                break;
            }
            if (j==temp.begin()&&(*i)<(*j))
            {
                temp.insert(temp.begin(),(*i));//[color=#800000]问题应该在这里 但是不知道啥问题[/color]
            }
        }
    }
    v=temp;
}

很简单的插入排序但是找了好久都没找到请各位看看

------解决方案--------------------
for (VI j = temp.end()-1;j>=temp.begin();--j)
//这一句，迭代器失效在插入之后
------解决方案--------------------

temp.insert(temp.begin(),(*i));//问题应该在这里但是不知道啥问题

一句后面break好像可以。。。
------解决方案--------------------
for (VI j = temp.end()-1;j>=temp.begin();--j)
跳出这个循环的条件是 j<temp.begin()而不是j等于temp.begin(),也就是说j指向了temp.begin()的前一个位置才跳出循环

if (j==temp.begin()&&(*i)<(*j))
这一句有问题，j有可能不等于temp.begin()而是指向了temp.begin()的前一个位置
将这一句更改为：if (j==temp.begin()-1&&(*i)<(*（j-1))）

------解决方案--------------------
不要在stl不熟练的情况下，复用vector。加一个vector的临时变量来存储中间过程。
------解决方案--------------------

探讨

引用:

是啊加个break就行了这个break有啥意义呢？

------解决方案--------------------
j指向begin的前一个位置的时候不就退出循环了吗？所以我觉得这里指不到啊！而且在if (j==temp.begin()&&(*i)<(*j)) 这句话后面加一个break就可以了，我觉得是不是如果不加break 就会使j=begin()-1 从而产生非法指针？

j =begin() - 1;不会产生非法指针的，况且j根本就不是指针是一个迭代器，迭代器和指针是不一样的，唉，楼主你要多看看书啊，因为vector容器允许它的迭代器进行算术运算，也允许迭代器指向第一个元素的前一个位置
------解决方案--------------------

C/C++ code


if (j==temp.begin()&&(*i)<(*j))
            {
                temp.insert(temp.begin(),(*i));//[color=#800000]问题应该在这里 但是不知道啥问题[/color]
break;//在这里加个break就可以了
            }

------解决方案--------------------
如果你不在temp.insert(temp.begin(),(*i));这条语句后加break的话，执行完插入语句后，迭代器j就失效了，不再执向temp.begin()了，而程序会继续执行下一句，也就是下面这一句：
for (VI j = temp.end()-1;j>=temp.begin();--j)；会继续对j进行--j;操作，然而当前迭代器j已经失效了，再对j进行前自减操作是非法的，会发生运行时错误，程序崩溃

stl实现插入排序的有关问题

相关推荐