sorting vector> based on the content of vector

Question

I have 2000 vector<vector<bool>> and each vector<bool> contains 200 elements , I am going to sort this vector of vectors. Supposing that the elements in vector<bool> are a one binary number.

original data:

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

After sorting:

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

It is possible to use sort with a special predicate but surprisingly when I call sort without a predicate it seems to work anyway.

    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());

and the order is as "after sorting" above.

Why does it work without a special predicate?

Would 0,1,0,0 compare before or after 0,0,1,0? What is your bit endianess? — eerorika, Aug 29 '14 at 12:09
This is not a duplicate, it is just a badly worded question. — CashCow, Aug 29 '14 at 12:46
I have rephrased the question as to what I think the user is asking — CashCow, Aug 29 '14 at 12:49
@juanchopanza "how to sort a vector of user defined type" is certainly a part of his question and the duplicate answers that. But "how to write a predicate to sort vectors of bool as if they were interpreted as a binary number" is also part of the original question (not with those exact words, but because the answer to the first part is "use std::sort and a predicate") and that is not answered in the duplicate. — eerorika, Aug 29 '14 at 13:14
The duplicate shows that you can use std::sort and a predicate. It would be a simple step to figure out why and when the predicate is needed, and what the default behaviour does. I must have forgotten for a moment that we're in the business of spoon-feeding answers to people. — juanchopanza, Aug 29 '14 at 13:18

Vlad from Moscow · Accepted Answer · 2014-08-29T12:18:11.083

5

It is enough simply to apply standard algorithm std::sort declared in header <algorithm> because there is defined operator < for vectors provided that all boolean vectors have the same size.

Here is an example

#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;
}

The output is

Otherwise you could use algorithm std::accumulate in a predicate of std::sort

edited Aug 29 '14 at 12:18

answered Aug 29 '14 at 12:03

Vlad from Moscow

301,070
26
186
335

@Quentin It depends on whether all boolean vectors have the same size. As in the original post all vectors have the same size then they will be sorted accordingly. – Vlad from Moscow Aug 29 '14 at 12:10
After a quick peek at the C++ reference, I take back that comment :) – Quentin Aug 29 '14 at 12:12
1

Even if they don't have the same size, `<` works just fine because it's the same as `lexicographical_compare`. – Anton Savin Aug 29 '14 at 12:14
@Anton Savin No, it will not work if to consider boolean vectors as binary representations of unsigned integral numbers. – Vlad from Moscow Aug 29 '14 at 12:23
@VladfromMoscow this will not sort the vectors according to the bit-endiannes that OP wants (according to the comments on question). – eerorika Aug 29 '14 at 12:24
@user2079303 in this case it is enough to sort vectors in the descending order. – Vlad from Moscow Aug 29 '14 at 12:28
@VladfromMoscow, no, wouldn't (1 1 1) then be before (0 0 0) which is also wong? – eerorika Aug 29 '14 at 12:32
@user2079303 In this case you will need to use a predicate. – Vlad from Moscow Aug 29 '14 at 12:41

score 3 · Answer 2 · answered Aug 29 '14 at 12:07

std::sort can take a Compare function. So just define a compare function on std::vector<bool> doing what you expect.

Hence you need to define a convention about how to compare two std::vector<bool> of different lengths.

BTW, it looks like you are re-inventing bignums, why don't you use some existing library like gmplib?

notadam · Answer 3 · 2014-08-29T12:21:01.793

Use a simple bubble sorting algorithm on the elements of the outer vector (which are vectors as well), and the condition of swapping would be this:

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 */

Because if you take two binary numbers, iterate through them, and compare each corresponding digit, then the greater of the two numbers is the one that has the highest digit that's a one and the corresponding digit in the other number is a 0. Like this:

0011010110101010000111011011

0010101011101000011101101010

Without converting them to decimal, it's easy to tell that the top one is larger. The first three digits are the same, but the fourth one is greater in the top number. The rest don't matter, this makes the top number bigger. Therefore, it's simple to use this as a swapping condition in bubble sorting.

sorting vector> based on the content of vector

3 Answers3