Given 2 lists generate 2 new lists with the elements that are in both and with those that are only in one

Question

Given 2 lists generate 2 new lists with the elements that are in both and with those that are only in one

Navigation

#1 by (1 votes)

1

Given two ordered lists L1 and L2 , write a function:

void bool_opers(list<int> &Lxor, list<int> &Land, list<int> &L1, list<int> &L2);

The algorithm must generate in Lxor a new sorted list with all the elements that are in only one of the two original lists, and in Land a new list ordered with all the elements that are in both.

For example, if L1 = (1,3,5,7,9) and L2 = (3,4,5,6,7) , then the algorithm must generate the lists

Lxor = (1,4,6,9) and Land = (3,5,7) .

The code you reach is the following:

auto it=L1.begin();
  while(it != L1.end()) {
    auto it2=L2.begin();
    bool flag = false;
    while(it2 != L2.end()){
      if(*it == *it2) {
        Land.push_back(*it);
        it = L1.erase(it);
        it2 = L2.erase(it2);
        --it; --it2;
      }
      ++it2;

    }
    ++it;
  }
  Lxor.insert(Lxor.begin(), L1.begin(), L1.end());
  Lxor.insert(Lxor.end(), L2.begin(), L2.end());
  Lxor.sort();

It seems to work in most cases. The problem is that I try this code in an evaluator function that teachers in my algorithm class and data structure use and it goes into an infinite loop. This function is to test the code with many cases and say if it is correct or not. I can not see the cases that are tested so I do not know where I'm failing.

c++ c++11

asked by facundo rotger 05.09.2018 в 16:31

source

1 answer

Problem in MySQL Select query How do I put a text on a responsive image, that when the image adapts to a smaller size the text also m

score 1 · Accepted Answer

The erase function (available in many data containers, I do not know which one you are using) returns the iterator after deletion (or end if you deleted the last one). In your algorithm after deleting a data, you move back one position and in that case if you have deleted the last data: you will no longer go out of loop.

Starting from a state in which both lists have only one element, this element being repeated in both:

When you delete, you make both iterators point to end .

Next, you rewind both iterators, making them point to an unknown place; depending on the iterator type this will have bad, very bad or worse consequences; possibly the new iterators (pointing to an unknown place) will no longer be able to track their position and moving them will cause more problems.

The next thing you do is to advance it2 , which (when lost) does not advance correctly and never reaches end , entering an infinite loop since no matter how much you keep moving forward, it may not reach the end again.

Proposal.

You are complicating the code a lot, I advise you to use an approach that is not aggressive with the lists (do not modify the lists) and focus the decisions on whether a value is present or not, I would do so:

using enteros = std::list<int>;

std::pair<enteros, enteros> bool_opers(const enteros &L1, const enteros &L2)
{
    enteros repetidos, unicos;

    // Una sencilla lambda que devuelve 'true' si el valor está en la lista
    auto esta = [](int valor, const enteros &lista)
    {
        return std::find(lista.begin(), lista.end(), valor) != lista.end();
    };

    // Si un valor de L1 está en L2: es repetido. En caso contrario es único.
    for (const auto &valor : L1)
        if (esta(valor, L2))
            repetidos.push_back(valor);
        else
            unicos.push_back(valor);
    // Ya sabemos los repetidos entre L1 y L2, sólo buscamos los L2 que no están en L1
    for (const auto &valor : L2)
        if (!esta(valor, L1))
            unicos.push_back(valor);

    return {repetidos, unicos};
}