0

Qual a estrutura mais eficiente em c/c++ que eu posso utilizar para criar e armazenar ciclos, de forma que eu garanta que ciclos repetidos não sejam armazenados?

Eu tenho um struct CICLO, tal que:

struct CICLO {
    vector<Arco> rota;
    float COST;
}

struct Arco {

    int i, j;
    Arco () {};
    Arco (const Arco& obj): i(obj.i), j(obj.j) {};
    Arco(int _i, int _j) : i(_i), j(_j) {}    

};

Pensei em ter um vector de ciclos para armazenar todos os ciclos já craidos.

vector<CICLO> ConjCiclos;

Para cada novo ciclo criado, eu preciso verificar se ele já não está armazenado em ConjCiclos.
O ciclo 1-2-2-1 é o mesmo que o ciclo 2-2-1-2. Como eu consigo detectar isso de maneira eficiente? Pensei que utilizar map seria uma boa opção. Porém, qual a lófica de chave que eu posso criar, tal que os ciclos acima tenham a mesma chave?

1 Resposta 1

-1

Sugiro usar unordered_map, que tem um custo de pesquisa constante O(1), desde que você possa compor uma chave de buscas unica para cada pesquisa.
Por exemplo, se sua chave for uma string:

typedef std::unordered_map<std::string, CICLO> map_ciclos_type;

[EDIT]
Segue um exemplo de uso:

map_ciclos_type map_ciclos;
map_ciclos_type::iterator iter_map_ciclos;

std::string chave("1-2-2-1-1");
CICLO ciclo;
map_ciclos[chave] = ciclo;

iter_map_ciclos = map_ciclos.find(chave);

if (iter_map_ciclos == map_ciclos.end())
{
    //não encontrou
}
else
{
    //ciclo existe
}
4
  • Mas como eu poderia compor um chave, nesse caso? Vc tem alguma sugestão?
    – rbl
    Commented 27/03/2018 às 15:58
  • Quais os parâmetros que você define como chave para pesquisar?
    – lsalamon
    Commented 27/03/2018 às 17:23
  • Eu estou precisando de ajuda justamente para definir essa chave. Dados dois ciclos iguais, mais criados de maneira diferentes, por exemplo 1-2-3-4-1 e 2-3-4-1-2. Como posso definir a chave para os ciclos, de forma que esses ciclos tenham a mesma chave e eu possa detectar redundância?
    – rbl
    Commented 27/03/2018 às 17:47
  • Você pode usar esta sequencia de números para montar um único número, concatenando-os, assim eles serão únicos para cada Ciclo. Caso estas sequencias sejam maiores, não cabendo em um LONG, por exemplo, passe eles para uma buffer std:string, colocando cada um em um posição. Como std:string é uma classe você pode ajustar cada um para ter o tamanho necessário e não se preocupa com liberação de memória.
    – lsalamon
    Commented 27/03/2018 às 19:16

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .