Classificando um vetor em ordem decrescente dentro de dois intervalos

14

Digamos que eu tenha um vetor de números inteiros:

std::vector<int> indices;
for (int i=0; i<15; i++) indices.push_back(i);

Então eu classifico em ordem decrescente:

sort(indices.begin(), indices.end(), [](int first, int second) -> bool{return indices[first] > indices[second];})
for (int i=0; i<15; i++) printf("%i\n", indices[i]);

Isso produz o seguinte:

14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Agora, quero que os números 3, 4, 5 e 6 sejam movidos para o final e mantenha a ordem decrescente para eles (de preferência sem precisar usar sortpela segunda vez). Ou seja, aqui está o que eu quero:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3

Como devo modificar a função de comparação do std::sortpara conseguir isso?

Yury
fonte
4
return indices[first] > indices[second]Você não quer dizer return first < second;?
acraig5075 28/02
2
Para uma classificação descendente simples, std::greaterfrom <functional>pode ser usado no lugar de sua lambda. Quanto à sua pergunta, escrever um comparador mais detalhado que garanta que seus valores sejam comparados da maneira que você deseja pode ser a maneira mais fácil de fazê-lo.
sweenish 28/02
4
@ acraig5075, em ordem decrescente deve ser return first > second.
ks1322 28/02
11
@ acraig5075 Sinto que estou perdendo alguma coisa, ou as pessoas não sabem a diferença entre ascendente e descendente ?
sweenish 28/02
3
Talvez você esteja procurando por std :: rotate ?
super

Respostas:

8

Sua função de comparação está incorreta, pois os valores que você obtém como firste secondsão os elementos do std::vector. Portanto, não há necessidade de usá-los como índices. Então, você precisa mudar

return indices[first] > indices[second];

para

return first > second;

Agora, com relação ao problema que você tenta resolver ...

Você pode deixar 3, 4, 5 e 6 fora de comparação com outros elementos e ainda compará-los entre si:

std::sort(
    indices.begin(), indices.end(),
    [](int first, int second) -> bool {
        bool first_special = first >= 3 && first <= 6;
        bool second_special = second >= 3 && second <= 6;
        if (first_special != second_special)
            return second_special;
        else
            return first > second;
    }
);

Demo

NutCracker
fonte
@NutCracker Sim, eu concordo que é melhor ter o critério principal primeiro.
Heap Overflow
5

Funções da biblioteca de algoritmos padrão como iota, sort, find, rotatee copyiria tornar sua vida mais fácil. Seu exemplo se resume a:

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


int main()
{
  std::vector<int> indices(15);
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), std::greater<>());

  auto a = std::find(indices.begin(), indices.end(), 6);
  auto b = std::find(indices.begin(), indices.end(), 3);
  std::rotate(a, b + 1, indices.end());

  std::copy(indices.begin(), indices.end(), std::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}

Resultado:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3


O @TedLyngmo nos comentários enfatiza que poderia / deveria ser aprimorado com:

auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;
acraig5075
fonte
auto b = a + 4;está errado (se você deseja manter a consistência com o snippet anterior). Deve ser auto b = a + 3;porque no que std::rotatevocê usab + 1
Biagio Festa
3

Solução 1

Abordagem direta com um comparador não linear .

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol1(std::vector<int>* v) {
  std::sort(v->begin(), v->end(), [](const int a, const int b) noexcept {
    const bool aSpecial = SpecialNumber(a);
    const bool bSpecial = SpecialNumber(b);

    if (aSpecial && bSpecial) return b < a;
    if (aSpecial) return false;
    if (bSpecial) return true;
    return b < a;
  });
}

Solução 2

Usando std::algorithms (partição)!

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol2(std::vector<int>* v) {
  auto pivot = std::partition(v->begin(), v->end(), std::not_fn(SpecialNumber));
  std::sort(v->begin(), pivot, std::greater{});
  std::sort(pivot, v->end(), std::greater{});
}

Considerações de desempenho

Pode parecer que a segunda solução é mais lenta devido à sobrecarga da partição. Provavelmente não, devido à previsão de cache e falta de ramificação nos processadores modernos.

Referência

Biagio Festa
fonte
Qualquer bom compilador deve se transformar n <= 6 && 3 <= n no que funciona melhor para a CPU de destino, para que você não ganhe nada introduzindo os números 2 e 7, exceto uma confusão potencial - e por que usar um ponteiro para o vetor em vez de uma referência?
Ted Lyngmo
Não use `const int number` como função de argumento
Antoine Morrier
11
@AntoineMorrier Por que?
Heap Overflow
@HeapOverflow Porque é o mesmo sem usar const :).
Antoine Morrier
@AntoineMorrier Eu não acho que é o mesmo. Não constdiz ao leitor que a função não altera o valor? Nesse caso específico de uma linha, pode ficar claro, mas em geral não é.
Heap Overflow