partición_punto en C++ – Part 1

partición_punto() Obtiene el punto de partición: Devuelve un iterador al primer elemento en el rango particionado [primero, último] para el cual pred(predicado) no es verdadero, indicando su punto de partición.

Los elementos del rango ya estarán particionados, como si se hubiera llamado a la partición con los mismos argumentos.

La función optimiza el número de comparaciones realizadas al comparar elementos no consecutivos del rango ordenado, lo cual es especialmente eficiente para iteradores de acceso aleatorio.

Sintaxis:

  ForwardIterator partition_point(ForwardIterator first, 
                                  ForwardIterator last,
                                  UnaryPredicate pred); 

Parámetros:
primero, último:
reenvía iteradores a las posiciones inicial y final de la secuencia particionada. El rango marcado es [primero, último], que contiene todos los elementos entre primero y último, incluido el elemento señalado por primero pero no el elemento señalado por último.

pred
Función unaria que acepta un elemento en el rango como argumento y devuelve un valor convertible a bool. El valor devuelto indica si el elemento va antes del punto de partición (si es verdadero, va antes; si es falso, va después o después). La función no modificará su argumento. Puede ser un puntero de función o un objeto de función.

Valor devuelto:
un iterador al primer elemento en el rango particionado [primero, último] para el cual pred no es verdadero, o último si no es verdadero para ningún elemento.

La definición de esta plantilla de función es equivalente a:

template 
  ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                                   UnaryPredicate pred)
{
  auto n = distance(first, last);
  while (n>0)
  {
    ForwardIterator it = first;
    auto step = n/2;
    std::advance (it, step);
    if (pred(*it)) { first=++it; n-=step+1; }
    else n=step;
  }
  return first;
}

Ejemplo 1:

// C++ program to get odd elements
// and even elements
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
  
bool IsOdd(int i) { return (i % 2) == 1; }
  
int main()
{
    std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    std::vector<int> odd, even;
  
    // partition data on the basis of odd elements 
    // using pred IsOdd()
    std::stable_partition(data.begin(), data.end(), IsOdd);
  
    // gets the partition point based on odd elements
    auto it = std::partition_point(data.begin(), data.end(), 
                                                     IsOdd);
  
    // assign elements to odd from beginning till partition 
    // point.
    odd.assign(data.begin(), it);
    even.assign(it, data.end());
  
    // print contents of odd:
    std::cout << "odd:";
    for (int& x : odd)
        std::cout << ' ' << x;
    std::cout << '\n';
  
    // print contents of even:
    std::cout << "even:";
    for (int& x : even)
        std::cout << ' ' << x;
    std::cout << '\n';
  
    return 0;
}

Producción:

odd:  1 3 5 7 9
even: 2 4 6 8 10

Ejemplo 2:

// C++ program to get negative elements
// and positive elements using partition_point
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
  
bool IsNegative(int i) { return (i < 0); }
  
int main()
{
    std::vector<int> data{ 1, -1, 3, -4, 5, 2, -2, 4, 
                                             -5, -3 };
    std::vector<int> negative, positive;
  
    // partition data on the basis of odd elements using 
    // pred IsNegative()
    std::stable_partition(data.begin(), data.end(), 
                                       IsNegative);
  
    // gets the partition point based on odd elements
    auto it = std::partition_point(data.begin(), data.end(), 
                                                 IsNegative);
  
    // assign elements to odd from beginning till
    // partition point.
    negative.assign(data.begin(), it);
    positive.assign(it, data.end());
  
    // print contents of odd:
    std::cout << "Negative: ";
    for (int& x : negative)
        std::cout << ' ' << x;
    std::cout << '\n';
  
    // print contents of even:
    std::cout << "Positive: ";
    for (int& x : positive)
        std::cout << ' ' << x;
    std::cout << '\n';
  
    return 0;
}

Producción:

Negative:  -1 -4 -2 -5 -3
Positive:  1 3 5 2 4

Complejidad :
Realiza comparaciones de aproximadamente log2(N)+2 elementos (donde N es esta distancia). En los iteradores de acceso no aleatorio, los avances del iterador producen una complejidad lineal adicional en N en promedio.

Este artículo es una contribución de Shubham Rana . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.