Removal of repeated values

Question

I have two Vectors, each with coordinates (x,y). I need to reverse the second vector, getting with (y, x) and merging with the first, but I can’t get repeat in the first field, so I thought I’d use a set.

However, I need the second value of the structure to be as large as possible. For example, if I have the following values: {(3, 2); (3, 10)}, I need the pair to stay on the set (3,10).

It is possible to do this with set?

Example in pseudo-code:

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

Reversing the coordinates of the second vector would be with:

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

When mixing with the first vector, I want the values of the first field to be unique, while the values of the second are always the greatest. In case I wanted a set with the following values:

set1<pair<int, int> > set1 = {(10, 9); (3, 7)};

Answer 1

Recital C++11, the following is valid:

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

To invert the coordinates of each element of the second vector, you can do the following:

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

Now as to insert them into one std::set keeping only the highest value, you are probably doing something much wrong here. Checking if the value of the coordinate is already in the set will cost you a loop passing through all the elements of the set. This for each insert. So to insert n items, you need to n² operations. It’s a lot.

From what I understand you have a coordinate that identifies the pair and another that is only a value. Clearly you have a key pair and value and want to have a list of them without repeating keys. What you need is a 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);

This function has complexity of n log(n) now that you don’t need to search all the elements for the key.

If you still want to use one std::set, has to go the long way:

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);

Answer 2

Vector-only alternative solution (using Generic Both of 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;
}

or:

#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;
}