Удаление дубликатов в двух векторах - PullRequest
Новая
       27

Удаление дубликатов в двух векторах

0 голосов
/ 15 мая 2018

Я попытаюсь объяснить мою проблему на следующем примере: 

vector<pair<string, string>> a = { { "A","1" }, {"B","2" },{ "C","3" },{ "D","3" },{ "E","5" } };

vector<pair<string, string>> b = { { "A","1" },{ "B","3" },{ "D","3" },{ "E","4" },{ "Z","5" } };

Какой будет наиболее эффективный способ удаления дубликатов и получения выходных данных в тех же векторах?Количество пар довольно большое, скажем, около 100 000.

Оба вектора отсортированы по первому элементу. 

vector<pair<string, string>> a = { { "B","2" },{ "C","3" },{ "E","5" } };

vector<pair<string, string>> b = { { "B","3" },{ "E","4" },{ "Z","5" } };

Дело в том, что мне нужносравнить эти векторы после удаления дубликатов.Первый элемент в паре - это путь к файлу, а второй - контрольная сумма для него.Так, например, если у меня есть "B","2" в первом контейнере, а "B","3" - во втором, я могу перечислить этот файл как «измененный».Я открыт для использования std::set, если это облегчит эту проблему.

Ответы [ 3 ]

0 голосов
/ 15 мая 2018

Использование бегущих индексов даст вам O (len (a) + len (b)) временную сложность и O (1) дополнительное пространство (учитывая, что a и b уже отсортированы) 

void removeDuplicate(vector<pair<string, string>>& a, vector<pair<string, string>>& b) {

    //Add these two lines if there can be duplicates in a or b themselves.
    //a.erase(std::unique(a.begin(), a.end()), a.end());
    //b.erase(std::unique(b.begin(), b.end()), b.end());

    size_t i = 0;
    size_t j = 0;

    size_t p1 = 0;
    size_t p2 = 0;

    while(i < a.size() && j < b.size()) {
        if(a[i] == b[j]) {
            i++;
            j++;
        } else if (a[i] > b[j]) {
            b[p2++] = b[j++]; 
        } else if (b[j] > a[i]) {
            a[p1++] = a[i++];
        }
    }

    while(i < a.size()) {
        a[p1++] = a[i++]; 
    }

    while(j < b.size()) {
        b[p2++] = b[j++];
    }

    a.erase(a.begin()+p1, a.end());
    b.erase(b.begin()+p2, b.end());
}
0 голосов
/ 15 мая 2018

Я не думаю, что какой-либо из стандартных библиотечных алгоритмов будет здесь прямо полезен.

Сначала мы проверяем, следует ли удалить (из обоих), в противном случае мы передвигаем итератор, указывая на меньшее значение, и продолжаем. 

for (auto ait = a.begin(), bit = b.begin(); ait != a.end() && bit != b.end();)
{
    if (*ait == *bit)
    {
        // Potenitally multiple duplicate values
        ait = a.erase(std::remove(ait, a.end(), *ait), a.end());
        bit = b.erase(std::remove(bit, b.end(), *bit), b.end());
    }
    else if (*ait < *bit) ++ait;
    else ++bit;
}
0 голосов
/ 15 мая 2018

Вы можете использовать некоторые алгоритмы из библиотеки STL, чтобы помочь решить эту задачу. Сначала найдите те же элементы и поместите их во временный вектор, затем удалите эти элементы из каждого вектора, см. Пример кода: 

vector<pair<string, string>> a = { { "A","1" }, {"B","2" },{ "C","3" },{ "D","3" },{ "E","5" } };
vector<pair<string, string>> b = { { "A","1" },{ "B","3" },{ "D","3" },{ "E","4" },{ "Z","5" } };

//Vector to hold same elements
vector<pair<string, string>> same_elements {};

//Fill same_elements vector
std::for_each(a.begin(), a.end(), [&same_elements, b]( pair<string, string>& el )
              {
                  if( find(b.begin(), b.end(), el) != b.end() )
                  {
                      same_elements.push_back(el);
                  }
              });

//Remove same elements from a and b
std::for_each(same_elements.begin(), same_elements.end(), [&a, &b]( pair<string, string>& el_to_delete )
              {
                  auto It_a = find(a.begin(), a.end(), el_to_delete);
                  if( It_a != a.end() )
                  {
                      a.erase(It_a);
                  }

                  auto It_b = find(b.begin(), b.end(), el_to_delete);
                  if( It_b != b.end() )
                  {
                      b.erase(It_b);
                  }
              });

Я использовал std::for_each для перебора всех элементов вектора, std::find для поиска необходимых элементов в векторах и erase векторный метод для удаления того же элемента из вектора с помощью итератора.

...