5

Tenho dois vectors, cada um com coordenadas (x,y). Eu preciso inverter o segundo vector, ficando com (y, x) e mesclar com o primeiro, mas não posso ter repetição no primeiro campo, por isso pensei em usar um set.

Entretanto, preciso que o segundo valor da estrutura seja sempre o maior possível. Por exemplo, se eu tiver os seguintes valores: {(3, 2); (3, 10)}, preciso que fique no set o par (3,10).

É possível fazer isso com set?

Exemplo em pseudo-código:

vector<pair<int, int> > vector1 = {(10, 2); (10, 1); (3, 7)};
vector<pair<int, int> > vector2 = {(1, 3); (9, 10)};

Invertendo as coordenadas do segundo vetor, ficaria com:

vector2 = {(3, 1); (10, 9)};

Ao mesclar com o primeiro vetor, quero que os valores do primeiro campo sejam únicos, enquanto que o do segundo sejam sempre os, maiores. No caso eu queria um set com os seguintes valores:

set1<pair<int, int> > set1 = {(10, 9); (3, 7)};
2
  • Sua dúvida não está clara. Por vector e set você se refere ao std::vector e std::set? Pode mostrar um exemplo de código? Commented 15/03/2014 às 15:33
  • 1
    Sim, Guilherme. Editei o post para tentar explicar melhor a dúvida.
    – user6635
    Commented 15/03/2014 às 16:33

2 Respostas 2

5

Considerando C++11, o seguinte é válido:

vector<pair<int, int>> vec1 = {{10, 2}, {10, 1}, {3, 7}};
vector<pair<int, int>> vec2 = {{1, 3}, {9, 10}};

Para inverter as coordenadas de cada elemento do segundo vetor, você pode fazer o seguinte:

for (auto& coord : vec2)
    swap(coord.first, coord.second);

Agora quanto a inserir eles em um std::set mantendo apenas o valor mais alto, você provavelmente está fazendo algo muito errado aqui. Verificar se o valor da coordenada já está no set vai lhe custar um loop passando por todos os elementos do set. Isso para cada inserção. Então para inserir n itens, você precisa de operações. É muita coisa.

Do que entendo você tem uma coordenada que identifica o par e outra que é apenas um valor. Claramente você tem um par de chave e valor e quer ter uma lista deles, sem repetir chaves. O que você precisa é de um std::map.

map<int, int> m;

void insertPair(const pair<int, int>& p) {
    if (m.find(p.first)) // Se já tem a key
        m[p.first] = max(m[p.first], p.second);
    else
        m[p.first] = p.second;
}

for (const auto& coord : vec1)
    insertPair(coord);

for (const auto& coord : vec2)
    insertPair(coord);

Essa função tem complexidade de n log(n) agora que não precisa procurar em todos os elementos pela chave.

Se ainda assim pretende usar um std::set, tem que ir pelo caminho longo:

set<pair<int, int>> s;

void insertPair(const pair<int, int>& p) {
    for (const pair<int, int>& p2 : s) { // percorra todo o set em busca do elemento
        if (p2.first == p.first) { // ao encontrar
            p2.second = max(p2.second, p.second); // troque o valor pelo maior
            return; // e retorne
        }
    }
    s.insert(p); // se não encontrou, basta inserir
}

for (const auto& coord : vec1)
    insertPair(coord);

for (const auto& coord : vec2)
    insertPair(coord);
1
  • Obrigado, Guilherme. Era exatamente esta a dúvida. Vou utilizar um std::map então.
    – user6635
    Commented 15/03/2014 às 17:21
3

Solução alternativa só com vetores (usando generic lambdas do c++14):

#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    vector<pair<int, int>> v1 = { {10, 2}, {10, 1}, {3, 7} };
    vector<pair<int, int>> v2 = { {1, 3}, {9, 10} };

    for(auto &p : v2)
        swap(p.first, p.second);
    v1.insert(end(v1), begin(v2), end(v2));
    sort(rbegin(v1), rend(v1));
    v1.erase(
        unique(begin(v1), end(v1),
            [](auto lhs, auto rhs) { return lhs.first == rhs.first; }),
        end(v1));

    for (auto &p : v1)
        cout << '(' << p.first << ", " << p.second << ')' << endl;
}

ou:

#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    vector<pair<int, int>> v1 = { {10, 2}, {10, 1}, {3, 7} };
    vector<pair<int, int>> v2 = { {1, 3}, {9, 10} };

    for(auto &p : v2)
        swap(p.first, p.second);
    v1.insert(end(v1), begin(v2), end(v2));
    sort(rbegin(v1), rend(v1));
    vector<pair<int, int>> v3;
    unique_copy(begin(v1), end(v1), back_inserter(v3),
        [](auto lhs, auto rhs) { return lhs.first == rhs.first; });

    for (auto &p : v3)
        cout << '(' << p.first << ", " << p.second << ')' << endl;
}
6
  • pepper_chico, essa solução não garante que terei sempre o maior valor no campo second do pair para chaves repetidas, não?
    – user6635
    Commented 16/03/2014 às 1:57
  • @lfelix sim ela garante, dê uma olhada sobre o que ocorre quando se compara grandeza entre dois pairs. (2, 1) > (2, 0) > (1, 2) > (1, 1), etc. Eles fazem uma comparação lexicográfica.
    – oblitum
    Commented 16/03/2014 às 2:00
  • @lfelix A sacada é, fazer uso disto e, tacar tudo no vetor, ordenar, e então, correr o vetor pescando pairs somente quando o first muda. Por exemplo, fazendo essa "pesca" na lista que dei anteriormente, pega-se o primeiro (2,1), o próximo é igual, o próximo não, então pesca esse, (1, 2), e o outro é igual. No final só (2, 1) e (1, 2) foram pescados.
    – oblitum
    Commented 16/03/2014 às 2:07
  • 1
    Creio que fosse melhor você usar std::unique ou std::unique_copy nesse seu exemplo pois deixa mais claro o que esta acontecendo e simplifica seu código. Bastaria definir uma função ou um lambda que compare apenas o primeiro elemento dos pairs passados para ele. Veja um exemplo: ideone.com/7Bvi3k Commented 16/03/2014 às 16:12
  • 1
    @TiagoGomes muito melhor Tiago, std::unique me escapou, e o uso de std::transform pra swap está legal também, integrarei estas dicas, obrigado.
    – oblitum
    Commented 16/03/2014 às 16:46

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