es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • C++ asignar dinámicamente una estructura que contiene un sindicato [vector o mapa] dos veces lleva a un error de bad_alloc.

C++ asignar dinámicamente una estructura que contiene un sindicato [vector o mapa] dos veces lleva a un error de bad_alloc.

15 Jun, 2023 Programación

Tengo una gran cantidad de tuplas (arreglo de enteros[N], mensaje de cadena) para almacenar. Quiero poder agregar / eliminar muchos elementos de esta matriz muy rápido, pero lo más importante, dados otro arreglo array2, Quiero encontrar todas las cadenas de modo que para todos i: array[i] <= array2[i] (aún no implementado).

Por lo tanto, pensé en usar un árbol de altura N donde una hoja es un mensaje. Si es una hoja, debe contener un vector si es un nodo, debe contener un mapa.

Estoy usando una unión para administrar si un árbol es una hoja o un nodo.

Mi función de eliminación debería eliminar la hoja y todos los nodos que llevan solo a esta hoja.

Puedo insertar un mensaje (o varios mensajes diferentes). Sin embargo, no puedo volver a insertar un mensaje que eliminé previamente. Genera un error bad_alloc.

```cpp
#include
#include

#include

using namespace std;

struct Nodo{
enum{HOJA, NODO} tag;
union {
std::map<int, struct Nodo> mapa;
std::vector msg;
};
Nodo(std::string m){
tag = HOJA;
cout << "Bandera 1: se bloquea aquí, por alguna razón se asigna un mapa" << "\n";
msg.push_back(m);
cout << "Bandera 2: ¿lo lograste arreglar?" << "\n";
}
Nodo(){
tag = NODO;
mapa = std::map<int, struct Nodo>();
}
~Nodo(){
if (tag==NODO){
mapa.~map();
} else {
msg.~vector();
}
}
};

void insertar(int* array, int size, Nodo* nodo, std::string msg){
cout << "Insertar\n";
if (size > 1){
if (!nodo -> mapa.count(array[0])){
nodo->mapa[array[0]] = new Nodo();
}
insertar(array+1, size-1, nodo->mapa[array[0]], msg);
} else {
if (!nodo->mapa.count(array[0])){
cout << "Caso 1\n";
nodo -> mapa[array[0]] = new Nodo(msg);
}
else{
cout << "Caso 2\n";
nodo -> mapa[array[0]]->msg.push_back(msg);
}
}
}

bool encontrar(int * array, int size, Nodo * nodo){
if (!nodo -> mapa.count(array[0])){
return false;
}
if (size==1){
return true;
}
return encontrar(array+1, size-1, nodo->mapa[array[0]]);

}

std::vector encontrar_vec(int * array, int size, Nodo * nodo){
if (!nodo -> mapa.count(array[0])){
return std::vector();
}
if (size==1){
if (!nodo -> mapa.count(array[0])){
return std::vector();
}
return nodo -> mapa[array[0]]->msg;
}
return encontrar_vec(array+1, size-1, nodo->mapa[array[0]]);
}

void imprimir_array(std::vector v){
for (auto & elem : v){
cout << elem << " ";
}
cout << "\n";
}

void borrar(int * array, int size, Nodo * nodo){
std::vector<Nodo*> vec;
int i = 0;
Nodo *t = nodo;
while (i < size){
if (t -> mapa.count(array[i])){
vec.push_back(t);
t = t-> mapa[array[i]];
} else
break;
i++;
}

if (i == size){

    // Borrar la hoja
    cout << "Borrando hoja\n";
    delete t; 

    cout << "Borrando vec [" << size-1 << "] elem " << array[size-1] << "\n";
    cout << "¿Borrado? " << vec[size-1]->mapa.erase(array[size-1]) << "\n";

    // Borrar el camino si no tiene otra hoja
    cout << "Borrar camino\n";
    for (i = size-1; i > 0; i--){
        //cout << "debut loop " << i << "\n";
        //vec[i-1]->mapa.erase(array[i-1]);
        if (!vec[i] -> mapa.size()){
            delete vec[i];
            cout << "Borrando vec [" << i-1 << "] elem " << array[i-1] << "\n";
            cout << "¿Borrado? " << vec[i-1]->mapa.erase(array[i-1]) << "\n";
        }
        else 
            break;
        //cout << "fin loop\n";
    }
}

}

int main()
{
Nodo * Arbol = new Nodo;
for (int k = 0; k < 2; k++){
cout << "k = " << k << "\n-----------------------------------------------------------\n";

    int size = 4;
    int array[4] = {0,1,2,3};


    std::string m1 = "Mensaje aleatorio que quiero almacenar tantas veces como quiera";

    insertar(array, size, Arbol, m1);


    cout << "encontrar: " << encontrar(array, size, Arbol) << "\n";


    std::vector<std::string> vec1 = encontrar_vec(array, size, Arbol);


    cout << "vec "; 
    imprimir_array(vec1);



    cout << "-------------------\n";
    borrar(array, size, Arbol);
    cout << "Deberíamos encontrar el mensaje \n";
    imprimir_array(vec1);

    cout << "-------------------\n";
    cout << "No deberíamos encontrar el mensaje \n";
    vec1 = encontrar_vec(array, size, Arbol);
    imprimir_array(vec1);
    cout << "-------------------\n";

}
return 0;

}
```

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Solución

    La implementación proporcionada utiliza una estructura de árbol para almacenar tuplas de (int array [N], string mensaje) y permite una rápida inserción, eliminación y búsqueda. El árbol tiene una altura N, y cada nodo hoja contiene una cadena de mensaje, mientras que cada nodo no hoja contiene un mapa que asocia índices de matriz con sus nodos secundarios correspondientes.

    La función erase elimina un nodo hoja y todos los nodos no hoja que lo preceden, siempre y cuando la ruta no tenga otro nodo hoja. Para ello, primero encuentra el nodo hoja usando la entrada array de índices, y luego encuentra todos los nodos no hoja que lo preceden mientras los almacena en un vector. Luego elimina el nodo hoja y verifica cada nodo no hoja para ver si tiene otros nodos secundarios. Si no lo tiene, elimina el nodo y continúa subiendo por el vector hasta llegar a la raíz del árbol.

    El programa se bloquea debido al uso de map.~map () y msg.~vector () en el constructor de Node. Estas líneas deben eliminarse ya que están invocando el destructor de los objetos map y vector, respectivamente, lo cual no es necesario y puede causar un comportamiento indefinido. El constructor simplemente puede inicializar el vector msg y el mapa se puede inicializar más adelante en el constructor por defecto.

Comments are closed.