Найти слова, которые являются уникальными для 1 набора из 3 C ++

Question

У меня есть 3 набора, содержащие слова.

a: car, boat, table, ball

b: car, goat, helicopter

c: square, car, goat, boat

Мне нужно создать вектор или набор со словами, содержащимися ТОЛЬКО в наборе a.

Таким образом, ответ будет таким:

result: table, ball

Я пытался сделать это, используя set_difference и set_intersection, но пока не повезло. Можете ли вы предложить мне что-то?

Я пытался

set_difference(a.begin(), a.end(), b.begin(), b.end(), res.begin()); 
set_difference(res.begin(), res.end(), c.begin(), c.end(), res.begin());

Но результат пуст

Answer 1

Ваша ошибка здесь:

set_difference(res.begin(), res.end(), c.begin(), c.end(), res.begin());
//             ^            ^                              ^

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

Решение будет следующим:

std::set<std::string> a {"car", "boat", "table", "ball"};
std::set<std::string> b {"car", "goat", "helicopter"};
std::set<std::string> c {"square", "car", "goat", "boat"};

std::set<std::string> tmp;
std::set<std::string> res;

// Difference between a and b --> stored in tmp
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(tmp, tmp.begin()));

// Difference between tmp and c --> stored in res
std::set_difference(tmp.begin(), tmp.end(), c.begin(), c.end(), std::inserter(res, res.begin()));

for(const std::string & s : res)
    std::cout << s << '\n';

Вывод:

ball таблица

Живой пример

---

Примечание: Если мы посмотрим на документацию std::set_difference, мы можем видеть:

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

Полученный диапазон также сортируется. Эквивалентные элементы обрабатываются индивидуально, то есть, если какой-то элемент найден m раз в [first1, last1) и n раз в [first2, last2), он будет скопирован в d_first точно в std :: max (mn, 0 ) раз. Полученный диапазон не может перекрываться ни с одним из входных диапазонов.

^{выделение шахты}

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

---

Примечание 2: Если вы не хотите беспокоиться о наборе tmp (который бесполезен после получения набора res), вы можете поместить его в блок c, чтобы впоследствии он был уничтожен:

std::set<std::string> res;

{
    std::set<std::string> tmp;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(tmp, tmp.begin()));
    std::set_difference(tmp.begin(), tmp.end(), c.begin(), c.end(), std::inserter(res, res.begin()));
} // tmp destroyed here

Живой пример

Answer 2

Не передавая ваш код, мы можем только догадываться, что ваш код делает неправильно.

Вот что я сделал. Я обернул разницу логики c в помощник operator-. Я использовал std::unordered_set намеренно, потому что они не могут быть использованы непосредственно в std::set_difference.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>
#include <vector>

using std::cout;
using std::inserter;
using std::ostream;
using std::set_difference;
using std::sort;
using std::string;
using std::unordered_set;
using std::vector;

namespace {

unordered_set<string> operator-(unordered_set<string> const& minuend, unordered_set<string> const& subtrahend) {
    vector<string> m(minuend.begin(), minuend.end());
    vector<string> s(subtrahend.begin(), subtrahend.end());
    sort(m.begin(), m.end());
    sort(s.begin(), s.end());
    unordered_set<string> diff;
    set_difference(m.begin(), m.end(), s.begin(), s.end(), inserter(diff, diff.begin()));
    return diff;
}

ostream& operator<<(ostream& out, unordered_set<string> const& container) {
    char const* sep = " ";
    out << "{";

    for (auto const& s : container) {
        out << sep << "\"" << s << "\"";
        sep = ", ";
    }
    out << " }";
    return out;
}

}

int main() {
    auto a = unordered_set<string>{ "car", "boat", "table", "ball" };
    auto b = unordered_set<string>{ "car", "goat", "helicopter" };
    auto c = unordered_set<string>{ "square", "car", "goat", "boat" };
    auto d = a - b - c;
    cout << d << "\n";
}

ОБНОВЛЕНИЕ , отвечая на вопросы Фаэнора

Почему вы используете std :: unordered_set (вместо std :: set)?

Я выбрал unordered_set, чтобы продемонстрировать, что для set_difference требуется отсортированный контейнер. В unordered_set отсутствует эта функция.

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

Почему вы конвертируете это в std :: vector, который нужно будет отсортировать (вместо преобразования в std :: set)?

Вектор - очень эффективный контейнер, так как элементы в нем имеют локальность, и поэтому хороший кеш. Это мой go -контейнер.

Набор имеет гораздо больше выделений памяти, потому что это я sh узлов, и ему не хватает локальности.

Строковый объект в любом случае в содержимом может отсутствовать локальность, поскольку это в основном умный указатель на массив символов. Но из-за небольшой оптимизации строк (SSO), и это небольшие строки, он также не будет выделяться из кучи.

В сценарии исходного плаката в каждом контейнере есть только несколько элементов, таким образом, проблемы эффективности незначительны. Но стоит подумать, если проблемный домен был увеличен.

Я думаю, что вы должны были использовать std :: set (без каких-либо разъяснений со стороны OP) и если пользователь получил std: Вместо этого: unordered_set, он сам должен преобразовать его в правильный std :: set и затем вызвать ваш operator-().

Это жизнеспособный вариант. Из-за отсутствия контекста я считал, что это «худший сценарий», поскольку контейнер unordered_set не удовлетворяет требованию алгоритма set_difference.