¿Cómo elimino el elemento más pequeño y más grande de una matriz de una manera adecuada para C++?

Question

Digamos que tengo una matriz de entradas y quiero llamar a una función para eliminar los valores más pequeños y más grandes. Por eliminación quiero decir que si mi matriz inicial tenía 7 elementos de longitud, la nueva matriz tiene 5 elementos. El orden de los elementos restantes no importa. He encontrado algunas formas de hacerlo, pero no estoy seguro de cuál es la "forma" C++ de hacerlo, si tiene sentido.

Lo que tengo ahora es que uso std :: sort para ordenar mi matriz y luego utilizo un bucle for para copiar los resultados comenzando desde el segundo elemento y deteniéndome en el penúltimo elemento en una nueva matriz con el tamaño apropiado ¿Cómo debería devolver la matriz?

No puedo devolver la matriz recién creada porque es una variable local para la función. Podría pasar la nueva matriz como argumento para la función, pero ¿no es una forma más antigua de estilo C de hacer esto? También podría usar std :: vector, pero luego tendría que envolver la matriz en un vector y luego desenvolverla (los números deben permanecer en una serie de entradas). Parece exagerado, ¿no?

Vengo de un fondo de Python y solo quiero saber cuál es la forma más adecuada de hacerlo en C++.

Answer 1

Olvídese de las matrices y use std::vector<int> en su lugar.

using std::vector; 

vector<int> WithoutHiLo(vector<int> orig) 
{ 
    std::sort(orig.begin(), orig.end()); 
    vector<int> newVec = vector(orig.size()); 
    std:copy(&orig[1], &orig[orig.size()-1], &newVec[0]); 
    return newVec; 
} 

ACTUALIZACIÓN (por comentario):

vector<int> WithoutHiLo(vector<int> orig) 
{ 
    std::sort(orig.begin(), orig.end()); 
    return vector(&orig[1], &orig[orig.size()-1]); 
} 

Si realmente necesita una matriz de entrada:

vector<int> WithoutHiLo(int orig[], int size) 
{ 
    std::sort(&orig[0], &orig[size]); 
    vector<int> newVec = vector(size); 
    std:copy(&orig[1], &orig[size-1], &newVec[0]); 
    return newVec; 
} 

Answer 2

Utilizando el vector de STL para envolver la matriz de enteros en realidad no lo hace tiene sentido, como dijiste, y debido a que necesitas retener la estructura de datos del arreglo, también podrías no aventurarte fuera de esa estructura de datos.

Editar: Eliminé mi respuesta anterior y agregué el código de muestra.

He añadido algunos códigos a continuación para demostrar que no se trata del vector STL, pero es más que bienvenido.

//Other stuff here... 
int test[] = {5, 4, 3, 2, 1}; 
JunkFunc(test); 
//whatever else your program needs to do afterward... 

void CFlirPumpDlg::JunkFunc(int *arr) 
{ 
int junkArr[] = {1, 2, 3, 4, 5}; 
    //The above array is just dummy data; removing the high/low would go here 
memcpy(arr, &junkArr, sizeof(junkArr)); 
} 

Answer 3

Esto es más de STL tipo de camino.

std::vector<int> vec; 
//populate your vector 
vec.erase (max_element(vec.begin(), vec.end())); 
vec.erase (min_element(vec.begin(), vec.end())); 

Pero la complejidad es lineal, por lo que tal vez no sea la mejor si se requiere una eliminación más rápida.

Answer 4

La clasificación no es necesaria. ¿Y qué pasa si la matriz int tiene un duplicado mínimo o máximo? Cortar el primer y último valor después de una clasificación no resolverá el problema.

#include <vector> 
#include <stdio.h> 

void 
rm_minmax(int* x, int sz, std::vector<int>& v) { 
    int min = x[0]; 
    int max = x[0]; 
    int Sz = sz; 

    while (sz) { 
     int dv = x[sz-1]; 
     if (dv < min) min = dv; 
     if (dv > max) max = dv; 
     sz--; 
    } 

    for (int i=0; i < Sz; i++) { 
     if (x[i] != min && x[i] != max) v.push_back(x[i]); 
    } 
} 

int 
main(int argc, char** argv) { 
    int foo[] = { 5, 1, 33, 22, 54, 1, 44, 54 }; 
    int sz = sizeof(foo)/sizeof(int); 
    std::vector<int> x; 
    rm_minmax(foo, sz, x); 
    sz = x.size(); 
    for (int i=0; i < sz; i++) printf("%d\n", x[i]); 

}

Answer 5

Si los números tenían que permanecer en una matriz de enteros y el orden no importa, me gustaría hacerlo de esta manera:

void MoveHiLoToEnd(int orig[], int size) 
{ 
    int* last = orig + size - 1; 
    int* maxp = std::max_element(orig, orig + size); 
    std::iter_swap(maxp, last); 
    int* minp = std::min_element(orig, orig + size - 1); 
    std::iter_swap(minp, last - 1); 

    //now the original array contains max and min elements moved. 
    //to the end. You can ignore them or copy elements except 
    //those last two to a new array, if really necessary. 
} 

La firma

int* MoveHiLoToEnd(int* begin, int* end); 

es más en el estilo de biblioteca C++ y podría cambiarse a una plantilla

template<typename ForwardIter> 
ForwardIter RemoveHiLo(ForwardIter begin, ForwardIter end); 

devolver el iterador al elemento vieja min (más allá de la nueva colección truncada) , pero no creo que vale la pena. Eso requeriría diferentes parámetros (menos convenientes, creo) en la llamada.

EDITAR

idea sentimos plantilla es malo. Las cosas se complican. Usted tendría que requerir iterador bidireccional (lo que hace que la plantilla menos universal que podría ser con los delanteros. Por min y hacia adelante max_element es suficiente)

template<typename BidirectionalIterator> 
BidirectionalIterator RemoveHiLo(BidirectionalIterator begin, BidirectionalIterator end); 

o de entrada no estándar parámetros, ya que es necesario iterador hasta el último elemento .

Answer 6

Parte de su pregunta denota una falta de comprensión de la semántica de matriz de C++: no puede "eliminar" elementos de las matrices de C++ (dado que son memoria bruta). Puede reasignar la memoria a un área más pequeña; puedes usar un vector; puedes copiar a una matriz más pequeña.

Pero no puede hacer foo.delete_first() donde foo es una matriz.

Aquí está mi solución. Le da una nueva matriz (asignada en el montón) con las características que desea. Controlará maxes/mins duplicados. Mi solución tiene más líneas de código que una solución STL y recomendaría usar el STL si es posible.

//Returns a new'd array of type T. 
//Delete when done. 
// Big-O = O(std::sort(len)) + len + O(cost-of-new) 
template<typename T> 
T* filter(T* t, int len) 
{ 
    T* trimmed; 
    std::sort(t[0], t[len-1]); //consider that this will not compile if T is not comparable 

    //Here you could use a predicate approach, but let's write it out... 
    int num_mins = 1; //t[0] is always min 
    int num_maxes = 1; //t[len-1] is always max 
    for(int i = 0; i < len; i++) 
    { 
    if(t[i] == t[0]) 
     num_mins++; 
    if(t[i] == t[len-1]) 
     num_maxes++; 
    } 

    trimmed = new T[len - (num_mins + num_maxes)]; 
    return trimmed 
} 

Answer 7

Hay dos operaciones que debe realizar: busque el mínimo y el máximo, y luego elimine el mínimo y máximo. Al reconocer estos pasos y recordar el principio de responsabilidad única, usted mantiene el código limpio.

La primera operación es falta en C++ 03. Tal como están las cosas, sin hacer su propia función, la única forma es pasar por el rango dos veces, una con min_element y . Esto es algorítmicamente innecesario.

C++ 0x reconoce este defecto y agrega minmax_element (y minmax). Si tiene un compilador que admita C++ 0x, solo use std::minmax_element definido en <algorithm>. Si no, use Boost's o robar Boost's/escribe el tuyo.

Ahora podemos completar la primera operación:

int array[] = {4, 7, 6, 5, 9, 4, 3, 1, 11}; 

// see footnote for begin and end 
std::pair<int*, int*> mm = minmax_element(begin(array), end(array)); 

con punteros (o iteradores) a los elementos, que ahora retiramos.Con una matriz estática de tamaño, normalmente la solución es moverlos hasta el final, Ala:

// and take care your array has enough elements! 
std::swap(*mm.first, end(array) - 2); 
std::swap(*mm.second, end(array) - 1); 

A continuación, sólo tratan a la matriz de dos elementos más corto; esto es O (1). Otra solución, que mantiene el orden, es copiar/desplazar todos los elementos en uno; esto es O (N).

Y eso es todo. Puede ajustar lo anterior en alguna forma de la función erase_minmax.

_{* begin y end acaba de hacer las cosas un poco más fácil, son:}

template <typename T, size_t N> 
T* begin(T (&pArray)[N]) 
{ 
    return pArray; 
} 

template <typename T, size_t N> 
T* end(T (&pArray)[N]) 
{ 
    return pArray + N; 
} 

Answer 8

entré en la solución de este y la discusión con Morón en los comentarios pregunta anterior dio lugar a la siguiente . El código está muy modificado pero es based on this answer by Rayhan.

Compilarlo y llamarlo con un archivo de entrada de números como ./a.out < /tmp/numbers o tubería que algunos números como echo 1 5 2 10 -2 0 | ./a.out

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

template<class T, class U> 
U copy_without_min_max(T in_begin, T in_end, U out) 
{ 
    typedef typename std::iterator_traits<T>::value_type value_type; 
    // min and max hold the min and max values found so far in the loop. 
    value_type min, max; 
    // small and big hold the values from the current pair being evaluated. 
    value_type small, big; 

    typename std::iterator_traits<T>::difference_type len = std::distance(in_begin, in_end); 
    // in_stop is either the end of input or one less if length is odd. 
    // This is needed so that in_begin will equal in_stop while advancing 2 at a time. 
    T in_stop(in_end); 
    T in_next(in_begin); 
    ++in_next; 
    // evaluate the first pair to find initial min,max values. 
    if (*in_begin < *in_next){ 
     min = *in_begin; 
     max = *in_next; 
    } else { 
     min = *in_next; 
     max = *in_begin; 
    } 
    if (len % 2 != 0) { // if len is odd 
     --in_stop; 
    } 
    std::advance(in_begin, 2); 

    // Advance two elements at a time tracking min and max as we go. 
    // Whenever a previous min or max is evicted, output it to the destination. 
    // Whenever a min or max is confirmed, output the element to the destination. 
    while(in_begin != in_stop) { 
     in_next = in_begin; 
     ++in_next; 
     if (*in_begin < *in_next) { // one comparison 
      small = *in_begin; 
      big = *in_next; 
     } else { 
      small = *in_next; 
      big = *in_begin; 
     } 
     if (min > small) { // one comparison 
      *out++ = min; 
      min = small; 
     } else { 
      *out++ = small; 
     } 
     if (max < big) { // one comparison 
      *out++ = max; 
      max = big; 
     } else { 
      *out++ = big; 
     } 
     std::advance(in_begin, 2); 
    } 
    // Special case for odd number of elements. 
    // Output either the last element or min or max, depending. 
    if (in_begin != in_end) { 
     if (*in_begin > min && *in_begin < max) { 
      *out++ = *in_begin++; 
     } else if (*in_begin < min) { 
      *out++ = min; 
     } else if(*in_begin > max) { 
      *out++ = max; 
     } 
    } 
    return out; 
} 

int main() 
{ 
    std::vector<int> in; 
    std::copy(
     std::istream_iterator<int>(std::cin), 
     std::istream_iterator<int>(), 
     std::back_inserter(in) 
    ); 
    copy_without_min_max(
     in.begin(), 
     in.end(), 
     std::ostream_iterator<int>(std::cout, " ") 
    ); 
    std::cout << std::endl; 

    return 0; 
}