эффективный способ получить уникальные элементы из вектора пар

Question

у меня есть вектор пар целых чисел, который выглядит как-то так:

(0, 1) 
(1, 9) 
(2, 3) 
(6, 1) 
(4, 0) 

Я хочу, чтобы извлечь уникальные элементы там, так что результат выглядит следующим образом:
‍‍0‍, 1, 9, 2, 3, 6, 4 (в основном только все числа без дубликатов)

на данный момент я делаю это так:

std::vector<int> getElements(std::vector<std::pair<int, int>> S) { 
    std::vector<int> V; 
    for (std::vector<std::pair<int, int>>::iterator i = S.begin(); i != S.end(); i++) { 
     if (std::find(V.begin(), V.end(), i->first) == V.end()) { 
      V.push_back(i->first); 
     } 
     if (std::find(V.begin(), V.end(), i->second) == V.end()) { 
      V.push_back(i->second); 
     } 
    } 
    return V; 
} 

Есть ли более эффективный способ сделать это?

Answer 1

Ваше текущее решение: O(n^2). Вы можете уменьшить линейное сканирование для уже увиденных элементов до амортизированного O(1) с помощью std::unordered_set для хранения уже увиденных номеров; Это улучшит ваше время выполнения до O(n).

Вот улучшенный алгоритм:

std::vector<int> getElements(std::vector<std::pair<int, int>> S) { 
    std::unordered_set<int> ss; 
    std::for_each(S.begin(), S.end(), [&ss](const auto& p) { 
     ss.insert(p.first); 
     ss.insert(p.second); 
    }); 
    return std::vector<int>(ss.begin(), ss.end()); 
} 

Смотрите пример Live On Coliru

Answer 2

Есть ли более эффективный способ сделать это?

Да, есть. std::find имеет сложность O (n) для вектора, поэтому повторение ее для каждого элемента дает вам сложность O (n * n).

Простой вариант состоит в том, чтобы добавить каждый элемент в std::set. Сложность построения набора - O (n log n).

Answer 3

не измерял, но я думаю, что это быстрее ...

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

std::vector<int> getElements(std::vector<std::pair<int, int>>& S) { 
    std::vector<int> V; 
    V.reserve(2*S.size()); 
    for (const auto& i : S) { 
     V.push_back(i.first); 
     V.push_back(i.second); 
    } 
    std::sort(V.begin(), V.end()); 
    V.erase(std::unique(V.begin(), V.end()), V.end()); 
    return V; 
} 

int main() 
{ 
    std::vector<std::pair<int, int>> v{{0, 1},{1, 9},{2, 3},{6, 1},{4, 0}}; 

    for(const auto& i : getElements(v)) 
     std::cout << i << ' '; 
    std::cout << '\n'; 
}