Как отсортировать std :: vector, игнорируя определенные числа? - PullRequest
Новая
       13

Как отсортировать std :: vector, игнорируя определенные числа?

0 голосов
/ 21 мая 2018

Я пытаюсь отсортировать вектор чисел и игнорировать определенное число, т.е. оставить его на месте. Этот ответ фактически не оставляет элемент, в котором он был найден.

Например, если у меня есть следующие 

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.Это просто очень сложно?

Ответы [ 4 ]

0 голосов
/ 21 мая 2018

Без замены элемента до конца:

  • Найти местоположение элемента.
  • Частичная сортировка вектора до и без этого местоположения, используя компаратор, который делает этоэлемент больше, чем другие элементы вектора, поэтому элемент не отображается в частично отсортированной части.
  • Отсортируйте оставшуюся часть вектора из этого местоположения до конца, используя компаратор, который делает этот элемент меньшимчем другие элементы остального вектора, этот элемент повторяется в этом месте.

Код: 

#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;
}
0 голосов
/ 21 мая 2018

В соответствии с лекарством @Bathsheba's , упомянутым в его ответе, и обманом предиката 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;
}
0 голосов
/ 21 мая 2018

Учитывая вектор.

  • Найдите расположение элемента, который вы хотите оставить.
  • Поменяйте его до конца.
  • Частичноsort vector (без последнего элемента) - все элементы до выбранного местоположения будут отсортированы, после чего будет случайный порядок.
  • Поменять элемент обратно в найденное место
  • отсортировать остаток вектора

Код: 

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() );
0 голосов
/ 21 мая 2018

Да, это сложно сделать с помощью std::sort: вам нужно каким-то образом обмануть компаратор, вставив инвариантное число в правильное место, и это сложно без предварительного изучения других элементов.

Простое решение - использовать сортировку вставок ;пропуская неуместный номер (но записывая позицию), когда вы доберетесь до него, и вставьте его вручную в конце в этой записанной позиции.

...