如何在没有C ++ STL sort（）的情况下对结构的矢量进行排序

Question

我正在尝试对包含结构的向量进行排序。在这个程序中，我不想使用任何C ++标准模板库（STL），如sort（）。

我试过这段代码

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (auto l = GTSlist.begin()+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = k->owner;
            k->owner = l->owner;
            l->owner = tmp;
        }
    }
}

打印矢量值

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) 
{
    cout << "\n print sorted vector k->owner =" << k->owner << "k->length =" << k->length ;
}

结构宣言

Struct Basic802154GTSspec
{
    int owner;
    int start;
    int length;
}

结构宣言

vector <Basic802154GTSspec> GTSlist;

在向量中插入值

// GTSlist.end()=5,length = 1,2,3,4,5 , owner= 5,1,4,2,3 
for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) {
    Basic802154GTSspec newGTSspec;
    newGTSspec.length = value shown above;
    newGTSspec.owner = value shown above;
    GTSlist.push_back(newGTSspec); 
}

预期结果

print sorted vector k->owner  k->length= 1,2; 2,4; 3,5; 4,3; 5,1

实际结果

print sorted vector k->owner  k->length= 1,1; 5,2; 2,3; 4,4; 3,5

Answer 1

这段代码错了：

if(k->owner > l->owner)
{
     auto tmp = k->owner;
     k->owner = l->owner;
     l->owner = tmp;
}

改为：

if (k->owner > l->owner)
{
    auto tmp = *k;
    *k = *l;
    *l = tmp;
}

而且，因为我认为auto在这里隐藏了一个重要的细节：

if (k->owner > l->owner)
{
    Basic802154GTSspec tmp = *k;
    *k = *l;
    *l = tmp;
}

最后，你应该调查使用::std::iter_swap作为建议的另一个答案。这是一个STL便利功能和::std::swap的伴侣（你也可以在这里使用）。你可以得到的主要优点是你可以略微简化你的代码，从而消除错误的可能性，并且它会尽可能地使用移动语义，这在许多情况下会更有效（尽管可能不是你的具体情况） ）。

如果您不知道什么是移动语义，请不要担心它。这是一个中级到高级的C ++理念，你可以跳过作为初学者的担忧。

总而言之，不使用STL算法是愚蠢的。排序实现是我知道的第二种更糟糕的排序算法（冒泡排序）。我所知道的唯一一个更糟糕的是一个反复洗牌的阵列，直到它偶然以排序的顺序结束。

Answer 2

您可能不想使用iter_swap，而且您的功能变得非常简单：

template <typename ForwardIterator>
void bubble_sort( ForwardIterator first, ForwardIterator last )
{
    for ( ForwardIterator sorted = first; first != last; last = sorted )
    {
        sorted = first;
        for ( ForwardIterator current = first, prev = first; ++current != last; ++prev )
        {
            if ( *current < *prev )
            {
                std::iter_swap( current, prev );
                sorted = current;
            }
        }
    }
}

Answer 3

在

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (auto l = GTSlist.begin()+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = k->owner;
            k->owner = l->owner;
            l->owner = tmp;
        }
    }
}

你只需要交换'所有者'而你需要交换所有的结构内容，而且我不依赖于k，做（我想你也不想使用std :: swap）

for (vector <Basic802154GTSspec>::iterator k = GTSlist.begin(); k != GTSlist.end(); k++)
{ 
    for (vector <Basic802154GTSspec>::iterator l = k+1; l != GTSlist.end(); l++)    
    {
        if(k->owner > l->owner)
        {
            auto tmp = *k;
            *k = *l
            *l = tmp;
        }
    }
}

你也有一个灾难性的问题

for (auto k = GTSlist.begin(); k != GTSlist.end(); k++) {
    Basic802154GTSspec newGTSspec;
    newGTSspec.length = value shown above;
    newGTSspec.owner = value shown above;
    GTSlist.push_back(newGTSspec); 
}

如果GTSlist在达到该值时不为空，那么您将永远不会停止并在GTSlist中不断添加新元素