Различия std::vector

Ответ 1

Вот полный и правильный ответ. Прежде чем использовать алгоритм 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). Специально для случая, когда один или оба контейнера являются очень большими (то есть миллионы целых чисел или более), другой алгоритм, использующий хеш-таблицы, может быть предпочтительным на основе алгоритмической сложности. Вот описание этого алгоритма на высоком уровне:

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

С++ 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> &ms1, 
                         unordered_multiset<tVal> &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 от предыдущего решения):

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

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

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

Ответ 2

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

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