Блог

Как определить, каковы различия в 2 векторах?

У меня есть vector<int> v1 и vector<int> v2 ;

То, что я ищу, — это a vector<int> vDifferences , который содержит только элементы, которые находятся только в v1 or v2 .

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

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

   using namespace std; // For brevity, don't do this in your own code...

  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // For the set_symmetric_difference algorithm to work, 
  // the source ranges must be ordered!    
  vector<int> sortedV1(v1);
  vector<int> sortedV2(v2);

  sort(sortedV1.begin(),sortedV1.end());
  sort(sortedV2.begin(),sortedV2.end());

  // Now that we have sorted ranges (i.e., containers), find the differences    
  vector<int> vDifferences;

  set_symmetric_difference(
    sortedV1.begin(),
    sortedV1.end(),
    sortedV2.begin(),
    sortedV2.end(),
    back_inserter(vDifferences));

  // ... do something with the differences
  

Следует отметить, что сортировка является дорогостоящей операцией (т.Е. O (n log n) для обычных реализаций STL). Особенно для случая, когда один или оба контейнера очень большие (т. Е. Миллионы целых чисел или более), Другой алгоритм с использованием хэш-таблиц может быть предпочтительным на основе алгоритмической сложности. Вот высокоуровневое описание этого алгоритма:

1. Загрузите каждый контейнер в хеш-таблицу.
2. Если два контейнера отличаются по размеру, для обхода на шаге 3 будет использоваться хэш-таблица, соответствующая меньшей. В противном случае будет использоваться первая из двух хэш-таблиц.
3. Пройдите по хэш-таблице, выбранной на шаге 2, проверяя, присутствует ли каждый элемент в обеих хэш-таблицах. Если это так, удалите его из них обоих. Причина, по которой меньшая хеш-таблица предпочтительнее для обхода, заключается в том, что поиск в хеш-таблице составляет в среднем O (1) независимо от размера контейнера. Следовательно, время прохождения является линейной функцией n (т. Е. O (n)), где n — размер проходимой хэш-таблицы.
4. Возьмите объединение оставшихся элементов в хеш-таблицах и сохраните результат в контейнере различий.

C 11 предлагает нам некоторые возможности для такого решения путем стандартизации unordered_multiset контейнера. Я также использовал новое использование auto ключевого слова для явных инициализаций, чтобы сделать следующее решение на основе хэш-таблицы более кратким:

 using namespace std; // For brevity, don't do this in your own code...

// The remove_common_items function template removes some and / or all of the
// items that appear in both of the multisets that are passed to it. It uses the
// items in the first multiset as the criteria for the multi-presence test.
template <typename tVal>
void remove_common_items(unordered_multiset<tVal> amp;ms1, 
                         unordered_multiset<tVal> amp;ms2)
{
  // Go through the first hash table
  for (auto cims1=ms1.cbegin();cims1!=ms1.cend();)
  {
    // Find the current item in the second hash table
    auto cims2=ms2.find(*cims1);

    // Is it present?
    if (cims2!=ms2.end())
    {
      // If so, remove it from both hash tables
      cims1=ms1.erase(cims1);
      ms2.erase(cims2);
    }
    else // If not
        cims1; // Move on to the next item
  }
}

int main()
{
  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // Create two hash tables that contain the values
  // from their respective initial containers    
  unordered_multiset<int> ms1(v1.begin(),v1.end());
  unordered_multiset<int> ms2(v2.begin(),v2.end());

  // Remove common items from both containers based on the smallest
  if (v1.size()<=v2.size)
    remove_common_items(ms1,ms2);
  else
    remove_common_items(ms2,ms1);

  // Create a vector of the union of the remaining items
  vector<int> vDifferences(ms1.begin(),ms1.end());

  vDifferences.insert(vDifferences.end(),ms2.begin(),ms2.end());

  // ... do something with the differences
}
  

Чтобы определить, какое решение лучше для конкретной ситуации, профилирование обоих алгоритмов было бы разумным решением. Хотя решение на основе хеш-таблицы находится в O (n), оно требует больше кода и выполняет больше работы на каждый найденный дубликат (т. Е. Удаление хеш-таблицы). Он также (к сожалению) использует пользовательскую функцию дифференцирования, а не стандартный алгоритм STL.

Следует отметить, что оба решения представляют различия в порядке, который, скорее всего, сильно отличается от порядка появления элементов в исходных контейнерах. Существует способ обойти это, используя вариант решения для хеш-таблицы. Далее следует описание высокого уровня (которое отличается только на шаге 4 от предыдущего решения):

1. Загрузите каждый контейнер в хеш-таблицу.
2. Если два контейнера отличаются по размеру, для обхода на шаге 3 будет использоваться меньшая хеш-таблица. В противном случае будет использоваться первая из двух.
3. Пройдите по хэш-таблице, выбранной на шаге 2, проверяя, присутствует ли каждый элемент в обеих хэш-таблицах. Если это так, удалите его из них обоих.
4. Чтобы сформировать контейнер различий, пройдите исходные контейнеры по порядку (т. Е. Первый контейнер перед вторым). Найдите каждый элемент из каждого контейнера в соответствующей хэш-таблице. Если он найден, элемент должен быть добавлен в контейнер различий и удален из его хэш-таблицы. Элементы, отсутствующие в соответствующих хэш-таблицах, будут пропущены. Таким образом, только элементы, которые присутствуют в хеш-таблицах, будут помещены в контейнер различий, и порядок их появления останется таким же, как и в исходных контейнерах, потому что эти контейнеры определяют порядок окончательного обхода.

Чтобы сохранить первоначальный порядок, шаг 4 стал дороже, чем в предыдущем решении, особенно если количество удаленных элементов велико. Это потому, что:

1. Все элементы будут проверены во второй раз на соответствие требованиям для отображения в контейнере различий с помощью теста присутствия в их соответствующих хэш-таблицах.
2. Оставшиеся элементы хэш-таблиц будут удаляться по одному при формировании контейнера различий, как часть настоящего в тестировании различий элемента 1.

Вам нужны элементы из обоих v1 и v2 которые являются уникальными, а не в другой последовательности? Для меня это звучит как std::set_symmetric_difference .

Копирует элементы диапазона [first1,last1), которых нет в диапазоне [first2, last2), и элементы диапазона [first2,last2), которых нет в диапазоне [first1, last1), в диапазон, начинающийся с result . Элементы в построенном диапазоне сортируются.