std::vector разлики

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> &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 от предходното решение):

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

За да се поддържа първоначалният ред, Стъпка 4 стана по-скъпа, отколкото в предишното решение, особено ако броят на премахнатите елементи е голям. Това е така, защото:

1. Всички елементи ще бъдат тествани втори път за допустимост да се появят в контейнера за разлики чрез тест за присъствие в съответните им хеш-таблици.
2. Хеш-таблиците ще премахнат остатъка от своите елементи един по един, когато се формира контейнерът за разлики, като част от присъстващо в разликите тестване на Елемент 1.