Как отсортировать все элементы со значением false до конца вектора?

#c #vector #boolean #stdvector

#c #вектор #логическое #stdvector

Вопрос:

Я хочу отсортировать вектор bools по их значению. Это список:

 std::vector<bool> bolis {true true false true false false true true};

Есть ли какая-то функция, которая сделала бы этот список равным этому:

 {true,true,true,true,true,false,false,false}

Я видел std::sort функцию, но, похоже, единственное ее реальное применение — сортировать список целых чисел или чисел с плавающей запятой, а не список bools.

1. Взгляните на std::partition .

2. std::sort конечно, можно было бы использовать. Однако, поскольку существует только два значения, безусловно, существуют более простые решения

Ответ №1:

Первый метод:

Этого можно достичь, определив пользовательскую функцию сравнения и передав ее sort функции.

Посмотрите на реализацию следующим образом:

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



//define the function:
bool comparator(bool lhs, bool rhs) { return rhs < lhs; }

int main()
{
    std::vector<bool> bolis {true, true, false, true, false, false, true, true};
    
    // pass it to sort:
    sort(bolis.begin(), bolis.end(), amp;comparator);
    
    for(int i=0;i<bolis.size();i  ){
        std::cout<<(bolis[i] ? "true " : "false ");
    }
    std::cout<<std::endl;
}

Вывод:

 true true true true true false false false

Второй метод за O (N) временной сложности:

Подсчитайте количество истинных и ложных значений в векторе и выведите их соответствующим образом.

Например, если имеется 5 истинных значений и 2 ложных значения, затем выведите true для 5 количество раз и false для 2 количество раз.

Или вы также можете поместить значения в другой вектор или отредактировать исходный вектор.

Спасибо @john за все предложения по улучшению ответа!

1. Спасибо @John. Изменил его.

2. Нет проблем. Мне нравится упоминание O (N) в вашем ответе. Очевидно, что вектор bools может быть отсортирован в O (N) просто путем подсчета, а затем присвоения false или true в соответствующих местах.

3. Спасибо @John! Также добавлено ваше предложение о редактировании исходного вектора.

4. comparator не требуется (значение по умолчанию правильное).

Ответ №2:

Сортировка a std::vector<bool> — это очень специфический случай, и его можно выполнить с помощью очень специфического решения:

подсчет количества true элементов, а затем перезапись вектора на основе этого количества.

Пример кода:

 #include <vector>
#include <iostream>

int main()
{
  std::vector<bool> bolis {true, true, false, true, false, false, true, true};
  // count number of true
  size_t nT = 0;
  for (bool value : bolis) nT  = value == true;
  // write sorted vector
  for (size_t i = 0, n = bolis.size(); i < n;   i) bolis[i] = i < nT;
  // show result
  const char *sep = "";
  for (bool value : bolis) {
    std::cout << sep << std::boolalpha << value;
    sep = ", ";
  }
}

Вывод:

 true, true, true, true, true, false, false, false

Живая демонстрация на coliru

Ответ №3:

std::partition Функция из стандартной библиотеки предназначена для выполнения именно того, что вы хотите сделать. Он принимает диапазон и предикат и переупорядочивает элементы диапазона так, чтобы они были разделены в соответствии с этим предикатом:

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


int main()
{
    std::vector<bool> bolis {true, true, false, true, false, false, true, true};

    //reorder so that true comes first    
    std::partition(bolis.begin(), bolis.end(), [](bool b){return b;});

    std::cout << std::boolalpha;
    std::copy(bolis.begin(), bolis.end(), std::ostream_iterator<bool>(std::cout, " " ));
    
    return 0;    
}

Вывод:

 true true true true true false false false

Вот демонстрация.