Repaso de C++: Ordenamiento y Plantillas

Repaso de algoritmos de ordenamiento en C++

Índice

  1. Algoritmos de ordenamiento: Burbuja y Selección

1.1 Ordenamiento burbuja

1.2 Ordenamiento por selección

  1. Palabra clave auto en C++
  2. Plantillas

3.1 Concepto y características de las plantillas

3.2 Funciones plantilla

3.2.1 Sintaxis:

3.2.2 Dos formas de invocar funciones plantilla:

3.2.3 Consideraciones importantes

3.2.4 Ejemplo práctico

3.2.5 Conversión implícita entre funciones normales y plantillas

3.2.6 Sobrecarga y reglas de invocación de funciones plantilla

Ejemplo 3: Lista vacía de parámetros de plantilla

Sobrecarga de funciones plantilla:

Mejor coincidencia prioriza el uso de plantillas:

3.3 Limitaciones de las plantillas

3.4 Clases plantilla

3.4.1 Diferencias entre clases y funciones plantilla:

3.4.2 Momento de creación de funciones miembro en clases plantilla

3.4.3 Clases plantilla como parámetros de función

3.4.4 Herencia con clases plantilla

3.4.5 Implementación de funciones miembro fuera de la clase

3.4.6 Escritura dividida de clases plantilla

3.4.7 Amistad entre clases plantilla

1. Algoritmos de ordenamiento: Burbuja y Selección

1.1 Ordenamiento burbuja

Comienza desde el primer elemento comparando elementos adyacentes, colocando los mayores hacia la derecha.

Por lo tanto, cada iteración puede encontrar un valor máximo relativo (el más a la derecha), lo que requiere len-1 iteraciones.

En cada subiteración se comparan elementos dos a dos, necesitando len-1-i comparaciones.

Código:

int main(int argc, char const *argv[])
{
    int arr[4] = {3,5,1,2};
    int length = sizeof(arr)/sizeof(int);
    for(int i = 0; i<length-1; i++)
    {
        for(int j = 0; j<length-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for(int i = 0; i<length; i++)
    {
        cout<<arr[i]<<endl;
    }
    return 0;
}

1.2 Ordenamiento por selección

Referencia: Algoritmo de ordenamiento: Selección [Ilustración + Código] - Bilibili

Cada vez (de los elementos restantes del arreglo) se escanea para encontrar el mínimo (o máximo) y se registra su índice, intercambiándose con el primer elemento del arreglo (colocándolo al inicio).

La elección entre máximo o mínimo depende del orden deseado (ascendente o descendente).

Dado que cada elemento debe ser examinado, se requieren len escaneos. En cada subescaneo se comienza desde el elemento i+1 hasta el final.

#include <iostream>
using namespace std;

void swap(int& a, int& b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void print_arr(int* arr, int n)
{
    for(int i = 0; i<n; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}

int main(int argc, char const *argv[])
{
    int arr[4] = {3,5,1,2};
    int length = sizeof(arr)/sizeof(int);
    print_arr(arr,length);

    for(int i = 0; i<length; i++)
    {
        cout<<"i: "<<i<<endl;
        int min = i;
        cout<<"min: "<<min<<endl;
        for(int j = i+1; j<length; j++)
        {
            if(arr[j]<arr[min])
            {
                min = j;  
            }
        }
        cout<<"min: "<<min<<endl;

        swap(arr[min],arr[i]);
        print_arr(arr,length);
    }

    return 0;
}

2. Palabra clave auto en C++

Resumen sobre el uso de auto en C++

3. Plantillas

Programación genérica y tecnologías STL en C++.

3.1 Concepto y características de las plantillas

Un molde genérico que mejora la reutilización.

No puede usarse directamente, solo es un marco. La generalidad no significa universalidad.

La técnica utilizada en programación genérica es la plantilla.

Dos mecanismos de plantilla: plantillas de funciones y plantillas de clases.

3.2 Funciones plantilla

Crea una función genérica donde el tipo de retorno y los parámetros pueden no especificarse, usando tipos virtuales.

3.2.1 Sintaxis:
template <typename T>
declaración o definición de función

Explicación:

template: declara la creación de una plantilla

typename: puede reemplazarse con class

T: tipo de datos genérico, nombre puede cambiarse, usualmente en mayúsculas

Ejemplo:

// Intercambio de dos enteros
void swapInt(int& a, int& b)
{
    int c = a;
    a = b;
    b = c;
}
// Intercambio de dos flotantes
void swapFloat(double& a, double& b)
{
    double c = a;
    a = b;
    b = c;
}

// Declarar una plantilla, indicando a compilador que T representa un tipo de dato genérico
template<typename T>
void Swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}
3.2.2 Dos formas de invocar funciones plantilla:

Inferencia automática de tipos por parte del compilador

int main()
{
    int a = 10;
    int b = 20;
    Swap(a, b);
}

Especificación explícita de tipo

int main()
{
    int a = 10;
    int b = 20;
    Swap<int>(a,b);
}
3.2.3 Consideraciones importantes
  • Cuando se usa inferencia automática, todos los parámetros deben derivar al mismo tipo T para poder usarlo.
template<typename T>
void Swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    char c = 'a';

    //Swap(a,b);   //Correcto
    //Swap(a,c);   //Incorrecto
    cout<<"a = "<<a<<endl;
    cout<<"b = "<<b<<endl;
    return 0;
}
  • La plantilla debe determinar el tipo T para poder ser utilizada.
template<typename T>
void Swap()
{
    cout<<"haha"<<endl;
}
int main()
{
    Swap();         //Error
    Swap<int>();    //Sin error
}
3.2.4 Ejemplo práctico
  • Crear una función plantilla para ordenar arreglos de diferentes tipos de datos, implementando selección.
  • Regla de ordenamiento: de mayor a menor.
  • Probar con arreglos de tipo int y char.
/*Una plantilla de función para ordenar arreglos de int o char*/

#include <iostream>
using namespace std;

template<typename T>
void my_Swap(T&a, T&b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

template<typename T>
void my_Sort(T* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        int min_index = i;
        for (int j = i+1; j < len; j++)
        {
            if(arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }

        //swap
        my_Swap(arr[min_index],arr[i]);
    }
}

int main(int argc, char const *argv[])
{
    int arr[4] = {3,5,1,2};
    my_Sort(arr,4);

    char arr1[4] = {'b','a','f','e'};
    my_Sort(arr1,4);

    for(int i = 0; i<4; i++)
    {
        cout<<arr1[i]<<endl;
    }
    return 0;
}

Error extraño: Si se escribe accidentalmente arr[min_index] como arr[min], el error es "error: overloaded function with no contextual type information if(arr[j] < arr[min])"

3.2.5 Conversión implícita entre funciones normales y plantilla

Las funciones normales realizan conversiones implícitas automáticamente

int my_add(int a, int b)
{
    return a+b;
}
int main()
{
    int a = 10;
    int c = 'c';
    cout<<my_add(a,c)<<endl;    //No hay error
}

Las funciones plantilla con inferencia automática no permiten conversiones implícitas

Las funciones plantilla con especificación explícita sí permiten conversiones implícitas

(Pero mi compilador permite conversión implícita)

template<typename T>
T my_add(T a, T b)
{
    return a+b;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    int c = 'c';
    cout<<my_add(a,c)<<endl;       //109 
    cout<<my_add<int>(a,c)<<endl;  //109
    return 0;
}
3.2.6 Sobrecarga y reglas de invocación de funciones normales y plantilla
  • Si ambas son invocables, se prefiere la función normal
  • Se puede usar lista vacía de parámetros de plantilla para forzar invocar una función plantilla
  • Las funciones plantilla pueden sobrecargarse
  • Si una función plantilla ofrece mejor coincidencia, se invoca preferentemente

Ejemplo 1:

#include <iostream>
using namespace std;

void my_print(int a, int b)
{
    cout<<"normal"<<endl;
    cout<<a+b<<endl;
    return;
}

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    my_print(a,b);
    return 0;
}

Salida:

normal
30

Ejemplo 2:

#include <iostream>
using namespace std;

void my_print(int a, int b);

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    my_print(a,b);
    return 0;
}

Salida: Error de enlazado: undefined reference to `my_print(int, int)'

Ejemplo 3: Lista vacía de parámetros de plantilla

#include <iostream>
using namespace std;

void my_print(int a, int b);

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    //Lista vacía de parámetros de plantilla
    my_print<>(a,b);
    return 0;
}

Salida:

template
30

Sobrecarga de funcoines plantilla:

#include <iostream>
using namespace std;

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

template<typename T>
void my_print(T a, T b, T c)
{
    cout<<"template"<<endl;
    cout<<a+b+c<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    int c = 30;
    
    my_print<>(a,b,c);
    return 0;
}

Salida:

template
60

Pero tenga cuidado, si se usan parámetros por defecto podría haber errores

#include <iostream>
using namespace std;

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

template<typename T>
void my_print(T a, T b, T c = 100)
{
    cout<<"template"<<endl;
    cout<<a+b+c<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    int c = 30;
    
    my_print<>(a,b,c);
    return 0;
}

No hay error.

#include <iostream>
using namespace std;

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

template<typename T>
void my_print(T a, T b, T c = 100)
{
    cout<<"template"<<endl;
    cout<<a+b+c<<endl;
}

int main(int argc, char const *argv[])
{
    int a = 10;
    int b = 20;
    int c = 30;
    
    my_print<>(a,b);
    return 0;
}

Error: error: call of overloaded 'my_print(int&, int&)' is ambiguous my_print<>(a,b);

Mejor coincidencia prioriza el uso de plantillas:
void my_print(int a, int b)
{
    cout<<"normal"<<endl;
    cout<<a+b<<endl;
    return;
}

template<typename T>
void my_print(T a, T b)
{
    cout<<"template"<<endl;
    cout<<a+b<<endl;
}

int main(int argc, char const *argv[])
{
    char a = 'a';
    char b = 'b';
    my_print(a,b);
    return 0;
}

Salida:

template
195

3.3 Limitaciones de las plantillas

No son completamente universales

template<typename T>
void f(T a, T b)
{
    cout<<a+b<<endl;
}

Si se pasan dos arreglos, no funcionará

Para ciertos tipos específicos, proporcionar especializaciones de plantillas:

/*Limitaciones de plantillas*/

#include <iostream>
using namespace std;

class Person
{
public:
    Person(int age)
    {
        m_age = age;
    }
    int m_age;
};

template<typename T>
bool my_cmp(T &a, T &b)
{
    cout<<"func1"<<endl;
    if(a == b)
    {
        return true;
    }
    return false;
}

// bool my_cmp(Person &a, Person &b)
// {
//     cout<<"func2"<<endl;
//     if(a.m_age == b.m_age)
//     {
//         return true;
//     }
//     return false;
// }

template<>bool my_cmp(Person &a, Person &b)
{
    cout<<"func3"<<endl;
    if(a.m_age == b.m_age)
    {
        return true;
    }
    return false;
}

int main(int argc, char const *argv[])
{
    Person p1(10);
    Person p2(20);
    cout<<my_cmp(p1,p2)<<endl;
    return 0;
}

3.4 Clases plantilla

Propósito: crear una clase genérica donde los tipos de datos de los miembros pueden no especificarse, usando un tipo virtual.

Sintaxis:

template<typename T>
clase

Igualmente, typename puede sustituirse por class

/*Clases plantilla*/
#include <iostream>
#include <string>
using namespace std;

template<typename NameType, typename AgeType>
class Person
{
public:
    Person(NameType name, AgeType age)
    {
        this->m_name = name;
        this->m_age = age;
    }

    void show()
    {
        cout<<"nombre: "<<this->m_name<<" edad: "<<this->m_age<<endl;
    }

    NameType m_name;
    AgeType m_age;
};

int main(int argc, char const *argv[])
{
    Person<string, int> p1("henry",12);
    p1.show();

    Person<string, double> p2("henry",12.5);
    p2.show();
    return 0;
}

Salida:

nombre: henry edad: 12
nombre: henry edad: 12.5
3.4.1 Diferencias entre clases y funciones plantilla:
  1. Inferencia automática de tipos no aplica a clases plantilla (ni sobrecarga)

Continuando con el ejemplo anterior:

Person p3("henry",12.5);
p3.show();

Error: error: missing template arguments before 'p'

  1. Las clases plantilla pueden tener parámetros por defecto en la lista de parámetros
template<typename NameType, typename AgeType = int>
class Person
{
public:
    Person(NameType name, AgeType age)
    {
        this->m_name = name;
        this->m_age = age;
    }

    void show()
    {
        cout<<"nombre: "<<this->m_name<<" edad: "<<this->m_age<<endl;
    }

    NameType m_name;
    AgeType m_age;
};

int main(int argc, char const *argv[])
{
    Person<string, int> p1("henry",12);
    p1.show();

    Person<string, double> p2("henry",12.5);
    p2.show();

    // La lista de parámetros puede tener valores por defecto
    Person<string> p6("henry",100.5);
    p6.show();

    return 0;
}

Salida:

nombre: henry edad: 12
nombre: henry edad: 12.5
nombre: henry edad: 100
3.4.2 Momento de creación de funciones miembro en clases plantilla

El momento de creación de funciones miembro en clases plantilla difiere del de clases normales

  • Clase normal: se crean desde el inicio
  • Clase plantilla: se crean cuando se invocan
class Person1
{
public:
    void showPerson1()
    {
        cout<<"Person1"<<endl;
    }
};

class Person2
{
public:
    void showPerson2()
    {
        cout<<"Person2"<<endl;
    }
};

template<typename T>
class MyClass
{
public:
    T obj;
    void func1()
    {
        obj.showPerson1();
    }
    void func2()
    {
        obj.showPerson2();
    }
};

int main()
{
    MyClass<Person1> m;
    m.func1();
    
    //m.func2();    //Error
}
3.4.3 Clases plantilla como parámetros de función

Cómo pasar objetos instanciados de clases plantilla a funciones

Tres formas de pasar:

  • Especificar tipo de datos: mostrar explícitamente el tipo de datos del objeto
  • Parametrizar argumentos: convertir parámetros del objeto en plantillas para pasar
  • Parametrziar toda la clase: pasar la plantilla de la clase completa
#include <iostream>
using namespace std;

template<typename C1, typename C2>
class Person
{
public:
    Person(C1 name, C2 age)
    {
        this->name = name;
        this->age = age;
    }
    void showPerson()
    {
        cout<<"nombre: "<<this->name<<" edad: "<<this->age<<endl;
    }
    C1 name;
    C2 age;
};

//1. Especificar tipo de datos
void print_person(Person<string, int>&p)
{
    p.showPerson();
}

//2. Parametrizar argumentos
template<typename T1, typename T2>
void print_person2(Person<T1, T2>&p)
{
    p.showPerson();

    cout<<"Tipo de T1: "<<typeid(T1).name()<<endl;
    cout<<"Tipo de T2: "<<typeid(T2).name()<<endl;
}

//3. Parametrizar toda la clase
template<typename T1>
void print_person3(T1 &p)
{
    p.showPerson();

    cout<<"Tipo de T1: "<<typeid(T1).name()<<endl;
}

int main(int argc, char const *argv[])
{
    Person<string,int> p1("henry",24);
    print_person(p1);
    cout<<"-----"<<endl;
    print_person2(p1);
    cout<<"-----"<<endl;
    print_person3(p1);
    return 0;
}
3.4.4 Herencia con clases plantilla
  • Cuando una clase hija hereda de una clase base plantilla, se debe especificar el tipo T en la declaración de la clase hija.
  • Si no se especifica, no se puede determinar el tipo T y no se asigna memoria.
  • Para permitir especificar T de manera flexible, la clase hija también debe ser una plantilla.
#include <iostream>
using namespace std;

template<typename T>
class Base
{
public:
    T name;
};

//class Child : public Base //Error
//class Child : public Base<int>  //Funciona pero limita a int

template<typename T1, typename T2>
class Child : public Base<T1>
{
public:
    Child()
    {
        cout<<"Tipo T1: "<<typeid(T1).name()<<endl;
        cout<<"Tipo T2: "<<typeid(T2).name()<<endl;
    }
    T2 age;
};

int main(int argc, char const *argv[])
{
    Child<string,int> c;
    return 0;
}
3.4.5 Implementación de funciones miembro fuera de la clase

Sintaxis:

template<typename T1, typename T2>
void Person<T1, T2>::printPerson(){}


#include <iostream>

using namespace std;

template<typename T1, typename T2>
class Person
{
public:
    Person(T1 name, T2 age);
    void printPerson();

    T1 name;
    T2 age;
};

// Constructor implementado fuera de la clase
template<typename T1, typename T2>
Person<T1, T2>::Person(T1 name, T2 age)
{
    this->name = name;
    this->age = age;
}

// Función miembro implementada fuera de la clase
template<typename T1, typename T2>
void Person<T1, T2>::printPerson()
{
    cout<<"nombre: "<<this->name<<" edad: "<<this->age<<endl;
}

int main(int argc, char const *argv[])
{
    Person<string,int> p("Tom",20);
    p.printPerson();
    return 0;
}
3.4.6 Escritura dividida de clases plantilla

Debido a que las funciones miembro de clases plantilla se crean en tiempo de llamada, al dividir en archivos separados ocurren problemas de enlazado.

Solución:

  • Incluir directamente el archivo .cpp
  • O declarar e implementar (en archivos .h y .cpp) en el mismo archivo con extensión .hpp
3.4.7 Amistad entre clases plantilla
  • Función global implementada dentro de la clase: declarar directamente como amiga
  • Función global implementada fuera de la clase (complejo): se debe notificar previamente al compilador sobre la existencia de la función global

Recordatorio: La amistad permite a funciones u otras clases acceder a miembros privados o funciones miembro de la clase actual

Función global implementada dentro de la clase:

class Person
{
private:
    friend void printPerson(Person p)
    {
        cout<< p.name <<" "<<p.age <<endl;
    }
    
    string name;
    int age;

public:
    Person(string name, int age)
    {
        this->name = name;
        this->age = age;
    }
};

int main(int argc, char const *argv[])
{
    Person p("henry",24);
    printPerson(p);
    return 0;
}

También se puede aplicar a plantillas:

#include <iostream>
using namespace std;

template<typename T1, typename T2>
class Person
{
private:
    friend void printPerson(Person<T1,T2> p)
    {
        cout<< p.name <<" "<<p.age <<endl;
    }
    
    T1 name;
    T2 age;

public:
    Person(T1 name, T2 age)
    {
        this->name = name;
        this->age = age;
    }
    
};

int main(int argc, char const *argv[])
{
    Person<string, int> p("henry",24);
    printPerson(p);
    return 0;
}

Etiquetas: C++ plantillas ordenamiento burbuja selección

Publicado el 8-29 13:18

Etiquetas populares

©2026 Friki Work