如何排序 std::vector 忽略某些数字？

Question

我正在尝试对数字向量进行排序并忽略某个数字，即将其保留在原位。实际上并没有将元素留在找到它的位置。

例如，如果我有以下

std::vector<int> test{5, 3, 8, 4, -1, 1, 11, 9, 6};
std::sort(test.begin(), 
         std::partition(test.begin(), test.end(), [](int n)
                                                  {return n != -1;}));

将 test 排序为 1 3 4 5 6 8 9 11 -1。我搜索了几个小时，修改了两个自定义比较器并使用 std::partition，但我无法想出将 test 向量排序为 1 3 4 5 -1 6 8 9 11 的解决方案。这真的很难吗？

Answer 1

是的，使用 std::sort 执行此操作很棘手：您必须以某种方式欺骗您的比较器将不变数字插入正确的位置，如果不事先检查其他元素，这将很困难。

一个简单的补救方法是使用插入排序；当你到达它时省略不合适的数字（但记录位置），并在最后记录的位置手动插入它。

Answer 2

根据@Bathsheba 在他的回答中提到的 remedy 和欺骗 std::sort() 的谓词，可以实现如下解决方案：

DEMO

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> test{5, 3, 8, 4, -1, 1, 11, 9, 6};
    // get the position of -1
    auto itr = std::find(test.begin(), test.end(), -1);
    // sort all elements so that -1 will be moved to end of vector
    std::sort(test.begin(), test.end(), [](const int& lhs, const int& rhs )
        {
            if( lhs == -1 ) return false;
            if( rhs == -1 ) return true;
            return lhs < rhs;
        });

    test.erase(test.end()-1);   //  now erase it from end
    test.insert(itr, -1);       //  insert to the earlier position

    for(const auto& it: test)   std::cout << it << " ";

    return 0;
}

Answer 3

给定一个向量。

找到您要离开的元素的位置。
换到最后。
Partial sort 向量（没有最后一个元素）- 所选位置之前的所有元素将被排序，之后将是随机顺序。
将元素交换回找到的位置
对向量的其余部分进行排序

代码：

std::vector< int > data{ 5, 3, 8, 4, -1, 1, 11, 9, 6 };

auto chosen_iter = std::find( data.begin(), data.end(), -1 );

std::swap( *chosen_iter, *( data.end() - 1 ) );

std::partial_sort( data.begin(), chosen_iter, data.end() - 1 );

std::swap( *chosen_iter, *( data.end() - 1 ) );

std::sort( chosen_iter + 1, data.end() );

Answer 4

不将元素交换到末尾:

找到元素的位置。
使用使该元素大于向量其他元素的比较器，对向量进行部分排序直至并排除此位置，以便该元素不会出现在部分排序部分。
从该位置到末尾对向量的其余部分进行排序，使用使此元素小于向量其余元素的其他元素的比较器，将此元素放在此位置。

代码：

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

constexpr int ignored_number = 100;

int main()
{
    vector<int> test{5, 3, 8, 4, ignored_number, 1, 11, 9, 6};

    auto it = find(test.begin(), test.end(), ignored_number);
    partial_sort(test.begin(), it, test.end(), [](int lhs, int rhs) {
        return lhs == ignored_number ? false :
            (rhs == ignored_number ? true : lhs < rhs);
    });
    sort(it, test.end(), [](int lhs, int rhs) {
        return rhs == ignored_number ? false :
            (lhs == ignored_number ? true : lhs < rhs);
    });

    for (const auto& x: test) {
      cout << x << ' ';
    }
    cout << endl;
}

如何排序 std::vector 忽略某些数字？

How to sort std::vector ignoring certain numbers?

c++

sorting

algorithm

stdvector

c++11