基于vector<vector<bool>>内容的vector<bool>排序

Question

我有2000 vector<vector<bool>>，每个vector<bool>包含200个元素，我要对这个向量进行排序。假设vector<bool>中的元素是一个二进制数。

原始数据：

vector 1: 1,1,1
vector 2: 1,0,1
vector 3: 0,0,0
vector 4: 1,0,0

分类后：

vector 3: 0,0,0
vector 4: 1,0,0
vector 2: 1,0,1
vector 1: 1,1,1

可以将sort与一个特殊的谓词一起使用，但令人惊讶的是，当我调用没有谓词的sort时，它似乎仍然有效。

    vector<bool> A = {1, 1, 1};
    vector<bool> B = {1, 0, 1};
    vector<bool> C = {0, 0, 0};
    vector<bool> D = {1, 0, 0};

    vector < vector<bool> > v = {A,B,C,D};

    sort(v.begin(),v.end());

上面的顺序是“排序后”。

为什么它在没有特殊谓词的情况下工作？

Answer 1

只需应用标头<algorithm>中声明的标准算法<algorithm>就足够了，因为只要所有布尔向量都具有相同大小的，就可以为向量定义operator <。

下面是一个例子

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

int main() 
{
    std::vector<std::vector<bool>> v =
    {
        { 1, 1, 1 }, { 1, 0, 1 }, {0, 0, 0 }, { 1, 0, 0 }
    };

    std::sort( v.begin(), v.end() );

    for ( const std::vector<bool> &v1 : v )
    {
        for ( bool b : v1 ) std::cout << b << ' ';
        std::cout << std::endl;
    }

    return 0;
}

输出是

0 0 0 
1 0 0 
1 0 1 
1 1 1 

否则，可以在std::accumulate的谓词中使用算法std::sort。

Answer 2

std:分类可以接受一个比较函数。因此，只需在std::vector<bool>上定义一个比较函数，以满足您的期望。

因此，您需要定义一个关于如何比较两个不同长度的std::vector<bool>的约定。

顺便说一句，看起来您正在重新发明大群，为什么不使用一些现有的库，比如格林普利布？

Answer 3

对外部向量(也是向量)的元素使用一个简单的气泡排序算法，交换的条件如下：

for (int i=0; i<200; i++)
    if (vec1[i] > vec2[i]) vec1.swap(vec2);
    /* vec1 and vec2 are the two vectors you
    compare when bubble sorting the outer vector */

因为如果你取两个二进制数，遍历它们，比较每一个对应的数字，那么这两个数字中较大的一个是一个最高的数字，一个是1，另一个数字中的对应数字是0。如下所示：

0011010110101010000111011011

001010101010000111011010

如果不将它们转换为十进制，很容易看出顶部的小数点更大。前三个数字是相同的，但是第四个数字在最上面的数字更大。其余的都不重要，这使得最高的数字更大。因此，在气泡排序中使用这一交换条件是简单的。