Сравнение двух std :: vectors / arrays или вообще двух stl contianers

Question

У меня есть два массива / вектора строк, например,

str1_arr = ["hello","my","dear","world"]
str2_arr = ["dear","my","world","hello"]

позиция / последовательность слов не совпадают. Я хотел бы знать, присутствует ли каждый элемент в str1_arr в str2_arr, не заботясь о своей позиции внутри контейнера.

Несколько раз обсуждали здесь и здесь но ответы вернулись в 2011 году. Учитывая, что c ++ продвинулся немного вперед, задаваясь вопросом, есть ли лучший способделает это с использованием std :: алгоритмов

Спасибо

Answer 1

Обновление

Ну, вот немодифицирующая и модифицирующая версия. Вся сложная сортировка и копирование кажутся большой работой, самая высокая сложность сортировки - log (n) * n и включает в себя всего 4 * n, плюс несколько линейных n, что намного меньше, чем n ^ 2,(Аппроксимируя размер / расстояние обоих диапазонов с помощью n, который просто равен размеру большего)

Так что для обозначения больших O это решение находится в O (n * log (n)) вместоO (n ^ 2) из ​​наивного for для решения или std::is_permutation (что также неверно в результатах).

Но мне было интересно, это все еще довольно высокий постоянный коэффициент сложности, поэтому я рассчитал:

Даже наихудший случай, при котором 2 n от копирования, 2 (log (n) * n) от сортировки и 2 (2n) от включений, меньше, чем n ^ 2наивное решение, для контейнера только размером 14 элементов .

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


template<typename Iterator1, typename Iterator2>
bool is_included_general_modifying(Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2) {
    std::sort(begin1, end1);
    std::sort(begin2, end2);
    return std::includes(begin2, end2, begin1, end1);
}

template<typename Iterator1, typename Iterator2>
bool is_included_general(Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2) {
    const auto first_range_is_sorted = std::is_sorted(begin1, end1);
    const auto second_range_is_sorted = std::is_sorted(begin2, end2);
    if (first_range_is_sorted && second_range_is_sorted) {
        return std::includes(begin2, end2, begin1, end1);
    } else if (first_range_is_sorted) {
        auto second_range_copy = std::vector<typename std::iterator_traits<Iterator2>::value_type>(begin2, end2);
        auto new_begin2 = second_range_copy.begin(), new_end2 = second_range_copy.end();
        std::sort(new_begin2, new_end2);
        return std::includes(new_begin2, new_end2, begin1, end1);
    } else if (second_range_is_sorted) {
        auto first_range_copy = std::vector<typename std::iterator_traits<Iterator1>::value_type>(begin1, end1);
        auto new_begin1 = first_range_copy.begin(), new_end1 = first_range_copy.end();
        std::sort(new_begin1, new_end1);
        return std::includes(begin2, end2, new_begin1, new_end1);
    }
    auto first_range_copy = std::vector<typename std::iterator_traits<Iterator1>::value_type>(begin1, end1);
    auto new_begin1 = first_range_copy.begin(), new_end1 = first_range_copy.end();
    std::sort(new_begin1, new_end1);
    auto second_range_copy = std::vector<typename std::iterator_traits<Iterator2>::value_type>(begin2, end2);
    auto new_begin2 = second_range_copy.begin(), new_end2 = second_range_copy.end();
    std::sort(new_begin2, new_end2);

    return std::includes(new_begin2, new_end2, new_begin1, new_end1);
}

int main() {
    std::array<std::string, 4> str1_arr = {"hello", "my", "dear", "world"};
    std::vector<std::string> str2_arr = {"additional element", "dear", "my", "world", "hello"};
    std::cout << is_included_general(str1_arr.begin(), str1_arr.end(), str2_arr.begin(), str2_arr.end()) << "\n";
}

Answer 2

std::vector<std::string> str1_arr{"hello", "my", "dear", "world"};
std::vector<std::string> str2_arr{"dear", "my", "world", "hello"};

assert(std::is_permutation(str1_arr.begin(), str1_arr.end(), 
                           str2_arr.begin(), str2_arr.end()));

Согласно C ++ ссылка , std::is_permutation(first1, last1, first2, last2) возвращает true, если существует перестановка элементов в диапазоне [first1, last1), которая делает этот диапазон равным диапазону [first2, last2).