1

En un ejercicio de Programming Principles and Practice Using C++ piden ordenar dos vectores; uno de nombres y otro de edades, y al final deben coincidir. Por ejemplo:

Tengo 2 vectores:

vector<string> nombres;
vector<double> edades;

Y al llenar los vectores con push_back() obtengo la siguiente salida:

(María, 19)
(Arturo, 12)
(José, 20)
(Chabelo, 1000)

Al utilizar la función sort(nombres) obtengo:

(Arturo, 19)
(Chabelo, 12)
(José, 20)
(María, 1000)

Y si también utilizo sort(edades) obtengo:

(Arturo, 12)
(Chabelo, 19)
(José, 20)
(María, 1000)

Mi pregunta es ¿Cómo puedo utilizar la función sort() con el vector nombres para generar lo siguiente:

(Arturo, 12)
(Chabelo, 1000)
(José, 20)
(María, 19)
4
  • ¿ Te pide explicitamente que uses la función sort( ) ?
    – Trauma
    el 29 dic. 2016 a las 8:45
  • Define "al final deben coincidir" por favor
    – David Isla
    el 29 dic. 2016 a las 9:10
  • 1
    Interpreté mal esa parte del ejercicio; lo que tenía que hacer era crear una función sort propia. Ya lo he hecho funcionar, muchas gracias.
    – akko
    el 29 dic. 2016 a las 10:08
  • ¿Cómo es que obtienes esa salida? ¿Puedes mostrar cómo es que "llenas" esos vectores? Explícate. Pon una muestra mínima de código compilable. -1
    – user4717
    el 30 dic. 2016 a las 21:27

4 respuestas 4

1

Hay una forma de ordenar los dos de forma simultanea sin tener que mover los datos a un contenedor nuevo. La idea pasa por crear un nuevo vector que contenga los índices ordenados del vector de referencia. Este nuevo vector se puede utilizar para reordenar los dos vectores.

Lo primero, por comodidad, es proporcionar una forma genérica para comparar los elementos del vector principal. En este caso el método genérico intentará ordenar los elementos usando el operador "menor que":

template<class T>
struct DefaultFuncComparar
{
  bool operator()(T const& a, T const& b)
  {
    return a < b;
  }
};

Y ahora la función de ordenación:

template<class T, class U, class FuncComparar = std::function<bool(T const&, T const&)>>
void OrdenarVectores(
  std::vector<T>& a,
  std::vector<U>& b,
  FuncComparar comparar = DefaultFuncComparar<T>())
{
  std::vector<T> copiaA{a};
  std::vector<U> copiaB{b};

  // Creamos el vector de índices
  std::vector<std::size_t> vector_indices(a.size());
  std::iota(vector_indices.begin(), vector_indices.end(), 0);

  // Ordenamos los índices en base al vector "a"
  std::sort(vector_indices.begin(), vector_indices.end(),
      [&](std::size_t i, std::size_t j){ return comparar(a[i], a[j]); });

  // Ordenamos los vectores "a" y "b" en base al vector de índices
  std::transform(vector_indices.begin(), vector_indices.end(), a.begin(),
      [&](std::size_t i){ return copiaA[i]; });

  std::transform(vector_indices.begin(), vector_indices.end(), b.begin(),
      [&](std::size_t i){ return copiaB[i]; });
}

Si ahora lo probamos con el siguiente código:

int main(){
  std::vector<std::string> nombres = { "Maria", "Arturo", "Jose", "Chabelo" };
  std::vector<int> edades = { 19, 12, 20, 1000 };

  OrdenarVectores(nombres,edades);

  std::cout << "Ordenados por nombre\n";
  for( unsigned i=0u; i<nombres.size(); i++)
  {
    std::cout << edades[i] << ' ' << nombres[i] << '\n';
  }
  std::cout << '\n';

  OrdenarVectores(edades,nombres);

  std::cout << "Ordenados por edad\n";
  for( unsigned i=0u; i<nombres.size(); i++)
  {
    std::cout << edades[i] << ' ' << nombres[i] << '\n';
  }
}

El resultado es el siguiente:

Ordenados por nombre
12 Arturo
1000 Chabelo
20 Jose
19 Maria

Ordenados por edad
12 Arturo
19 Maria
20 Jose
1000 Chabelo

En cualquier caso, si resulta que los dos vectores están relacionados hasta el punto de que han de mantener los mismos índices entonces el diseño que planteas no es el más adecuado. Mantener sincronizados dos o más vectores puede complicar en exceso el diseño del programa.

1

Quisiera añadir a las soluciones ya existentes una versión con plantillas variádicas

Propuesta.

template <std::size_t INDEX, typename TUPLE>
void push(const TUPLE &) {}

template <std::size_t INDEX, typename TUPLE, typename T, typename ... TYPES>
void push(const TUPLE &tupla, std::vector<T> &t, std::vector<TYPES> &...args)
{
    t.push_back(std::get<INDEX>(tupla));
    push<INDEX + 1>(tupla, args ...);
}

template <typename T>
T pop(std::vector<T> &v)
{
    auto t = v.back();
    v.pop_back();
    return t;
}

template <typename T, typename ... TYPES>
void ordena(std::vector<T> &t, std::vector<TYPES> &...args)
{
    using tupla = std::tuple<T, TYPES ...>;
    std::vector<tupla> valores(t.size());

    std::generate(valores.begin(), valores.end(), [&]() -> tupla
    {
        return { pop(t), pop(args)... };
    });

    std::sort(valores.begin(), valores.end(), [](auto i, auto d)
    {
        return std::get<0>(i) < std::get<0>(d);
    });

    for (const auto &valor : valores)
    {
        push<0>(valor, t, args...);
    }
}

Esta aproximación no confía en la obtención de índices para posteriormente ordenar mediante dichos índices (como hace eferion) si no que mueve1 los datos de cada uno de los vectores a un vector con una tupla y ordena dicho vector, posteriormente vuelve a mover1 los datos del vector de tupla a los vectores originales.

Explicación.

La función ordena recibe entre 1 e infinitos2 vectores de cualquier tipo ordenable y ordena todos ellos con el orden del primer vector recibido:

template <typename T, typename ... TYPES>
void ordena(std::vector<T> &t, std::vector<TYPES> &...args)

El parámetro t es el primer vector, que se usará de referencia de ordenación, el parámetro args es el paquete de parámetros con el resto de vectores. La función sólo acepta vectores no otro tipo de contenedores (aunque se podría adaptar para permitirlo).

Lo primero que se hace es crear una tupla de todos los tipos de los vectores para crear un vector con esa tupla y ordenar todos los valores a la vez:

using tupla = std::tuple<T, TYPES ...>;
std::vector<tupla> valores(t.size());

Al expandir la plantilla con los vectores nombres y edades la función ordena quedaría así:

void ordena(std::vector<std::string> &t, std::vector<double> &p0)
{
    using tupla = std::tuple<std::string, double>;
    std::vector<tupla> valores(t.size());
    ...

De haber usado más parámetros, la expansión de la plantilla se adaptaría:

std::vector<std::string> s;
std::vector<double> d;
std::vector<int> i;
std::vector<char> c;

ordena(s, d, i, c);

Se expandiría a:

void ordena(std::vector<std::string> &t, std::vector<double> &p0, std::vector<int> &p1, std::vector<char> &p2)
{
    using tupla = std::tuple<std::string, double, int, char>;
    std::vector<tupla> valores(t.size());
    ...

Seguidamente se guarda en el vector de tuplas cada uno de los valores de los vectores originales, a la vez que se vacían los vectores originales, esto se consigue con std::generate usando una lambda:

std::generate(valores.begin(), valores.end(), [&]() -> tupla
{
    return { pop(t), pop(args)... };
});

Esta instrucción, usando el último ejemplo expandería de la siguiente manera:

std::generate(valores.begin(), valores.end(), [&]() -> tupla
{
    return { pop(t), pop(p0), pop(p1), pop(p2) };
});

Llamamos a generate con una lambda cuyo tipo de retorno es la tupla de la plantilla instanciada, así que iremos añadiendo los elementos emparejados con todos los elementos en la misma posición en todos los vectores pasados como parámetro, en nuestro caso le vector valores tras la llamada a generate quedaría:

valores 0: <María,   19>
valores 1: <Arturo,  12>
valores 2: <José,    20>
valores 3: <Chabelo, 1000>

Para hacerlo nos valemos de la función plantilla auxiliar pop, que recibe un vector cualquiera y devuelve el último elemento del mismo a la vez que lo elimina.

A continuación se ordena la tupla de valores usando el primer elemento de la tupla (mediante la función std::get<0>):

std::sort(valores.begin(), valores.end(), [](auto i, auto d)
{
    return std::get<0>(i) < std::get<0>(d);
});

Y para acabar usamos la función plantilla recursiva auxiliar push:

for (const auto &valor : valores)
{
    push<0>(valor, t, args...);
}

Que en el ejemplo de nombres y edades se expandiría así:

push<0>(const std::tuple<std::string, double> &tupla, std::vector<std::string> &t, std::vector<double> &p0)
{
    t.push_back(std::get<0>(tupla));
    push<1>(tupla, p0);
}

push<1>(const std::tuple<std::string, double> &tupla, std::vector<double> &t)
{
    t.push_back(std::get<1>(tupla));
    push<2>(tupla);
}

push<2>(const std::tuple<std::string, double> &tupla) {}

Así que la función ordena puede ser usada así:

int main()
{
    std::vector<std::string> nombres = {"María", "Arturo", "José", "Chabelo"};
    std::vector<double> edades = {19, 12, 20, 1000};

    ordena(nombres, edades);

    return 0;
}

Ordenando nombres y edades así:

| nombres | edades |
+---------+--------+
| Arturo  | 12     |
| Chabelo | 1000   |
| José    | 20     |
| María   | 19     |

Y permite ordenar con cualquier2 cantidad de vectores:

std::vector<std::string> nombres = {"María", "Arturo", "José", "Chabelo"};
std::vector<double> edades = {19, 12, 20, 1000};
std::vector<double> numeros { 3.1415, 1.11, 2.22, 1e6 };

ordena(numeros, edades, nombres);

Muestra:

| numeros | edades | nombres |
+---------+--------+---------+
| 1.11    | 19     | María   |
| 2.22    | 20     | José    |
| 3.1415  | 12     | Arturo  |
| 1e+06   | 1000   | Chabelo |

[Aquí] puedes ver el código funcionando. Ten en cuenta que el código asume que todos los vectores son del mismo tamaño y que es costoso a nivel de realojamiento de memoria.


1Borra del origen y copia en el destino, no usa semánticas de movimiento.

2Infinitos no: tantos como permita el compilador.

5
  • Buena solución. Lo único que ya puestos con la abstracción sabe a poco ver que la función de comparación es fija e inamovible.
    – eferion
    el 2 ene. 2017 a las 14:38
  • En el ejemplo online, la función ordenar solo acepta 2 parámetros.
    – user13558
    el 2 ene. 2017 a las 15:51
  • @ArtEze en la línea 67 del ejemplo online veo que está recibiendo tres parámetros: ordena(numeros, edades, nombres); el 3 ene. 2017 a las 7:13
  • No está recibiendo, está enviando en una llamada a la función... Pero al declarar la función, recibe solo 2.
    – user13558
    el 3 ene. 2017 a las 7:21
  • 1
    @ArtEze te equivocas. Está recibiéndolo. En el caso de que los parámetros sean 2 o más, los parámetros adicionales se reciben como paquete de parámetros variádicos. el 3 ene. 2017 a las 7:43
0

Pon ambos datos dentro de una pareja y construye un solo vector de pares (nombre, edad). Luego utiliza un comparador a medida para ordenar el vector de pares.

Construir el vector de pares :

std::vector< std::pair< string, int> > nombreEdad;
for (size_t n=0; n<nombres.size(); ++n)
    nombreEdad.push_back( std::pair<string,int>(nombres[n], edades[n]));

Comparador a medida :

struct nombreMenor
{
    inline bool operator() (std::pair<string,int>& p1, 
                            const std::pair<string,int>& p2)
    {
        return p1.first.compare( p2.first) < 0;
    }
};

Llamara a sort con el comparador a medida.

std::sort(nombreEdad.begin(), nombreEdad.end(), nombreMenor());    

Imprimir resultado.

for( auto par : nombreEdad )
    std::cout << par.first << "," << par.second << std::endl;
0

El ejercicio requería crear una función que ordenara ambos vectores -lo confundí con la función sort() - La solución que implementé fue la siguiente (donde edad y nombre son vectores que ya han sido llenados en otra función del programa):

void Ordenar(){
    vector<string> cp_nom = nombre;     
    sort(nombre);
    vector<double> cp_edad;     
    for(int i = 0; i < nombre.size(); ++i){
        for(int j = 0; j < cp_nom.size(); ++j){
            if(cp_nom[j] == nombre[i]){
                cp_edad.push_back(edad[j]);
            }
        }
    }           
    edad.clear();
    edad = cp_edad;
}

Donde creo una copia del vector nombre vector< string > cp_nom la cual utilizo para comprobar las posiciones del vector original vector< string > nombre ya ordenado con la función sort() y así comienzo a llenar el vector< double > cp_edad al terminar reemplazo el contenido del vector< double > edad con el contenido de vector< double > cp_edad

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.