时间戳

首页 > 解决方案 > 如何在 C++ 列表中使用 while 循环？

c++ - 如何在 C++ 列表中使用 while 循环？

问题描述

我在 C++ 列表上使用合并排序。到目前为止，我可以使用 assign 函数将列表分成两半。

由于列表不使用数组或向量之类的索引，因此我在为我的列表翻译这个 while 循环时遇到了麻烦。

i = 0; j = 0; k = l;

//marge temp arrays to real array
while (i < nl && j < nr) {
    if (larr[i] <= rarr[j]) {
        array[k] = larr[i];
        i++;
    } 
    else {
        array[k] = rarr[j];
        j++;
    }

    k++;
}

while (i < nl) {       //extra element in left array
    array[k] = larr[i];
    i++; 
    k++;
}

while (j < nr) {     //extra element in right array
    array[k] = rarr[j];
    j++; 
    k++;
}

我该怎么做呢？

标签： c++algorithmwhile-loopmergemergesort

解决方案

如果你想为列表编写一个while循环，那么你应该使用迭代器而不是索引来访问列表的元素。

尽管如此，在 C++ 标准库std::merge的头文件中已经声明了标准算法。<algorithm>

给你。

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

int main()
{
    std::list<int> list1 = { 1, 3, 5 };
    std::list<int> list2 = { 0, 2, 4 };
    
    std::list<int> list3;
    
    std::merge( std::begin( list1 ), std::end( list1 ),
                std::begin( list2 ), std::end( list2 ),
                std::back_inserter( list3 ) );
                
    for ( const auto &item : list3 )
    {
        std::cout << item << ' ';
    }
    
    std::cout << '\n';
}

程序输出为

0 1 2 3 4 5

标准算法不会更改合并列表。它根据合并列表的元素创建一个新列表。

或者您可以自己编写这样的函数，例如

#include <iostream>
#include <list>
#include <iterator>

template <typename T>
std::list<T> merge_lists( std::list<T> &list1, std::list<T> &list2 )
{
    std::list<T> list3;
    
    typename std::list<T>::iterator first1 = std::begin( list1 ),
                                    first2 = std::begin( list2 );
    typename std::list<T>::iterator last1  = std::end( list1 ),
                                    last2  = std::end( list2 );

    while ( first1 != last1 && first2 != last2 )                                    
    {
        if ( *first2 < *first1 )
        {
            list3.push_back( *first2 );
            first2 = list2.erase( first2 );
        }
        else
        {
            list3.push_back( *first1 );
            first1 = list1.erase( first1 );
        }
    }
    
    list3.insert( std::end( list3 ), first1, last1 );
    list1.erase( first1, last1 );
    
    list3.insert( std::end( list3 ), first2, last2 );
    list2.erase( first2, last2 );
    
    return list3;
}

int main()
{
    std::list<int> list1 = { 1, 3, 5 };
    std::list<int> list2 = { 0, 2, 4 };
    
    std::list<int> list3 = merge_lists( list1, list2 );
    

    for ( const auto &item : list3 )
    {
        std::cout << item << ' ';
    }
    
    std::cout << '\n';
}

程序输出再次是

0 1 2 3 4 5

这个函数的实现实际上将元素从合并列表移动到结果列表。即调用函数后合并的列表为空。似乎这样的功能更适合您对列表进行排序的任务。

推荐阅读