Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cassert>
- // Функция, принимающая вектор векторов строк и объединяющая их в один отсортированный вектор строк
- std::vector < std::string > merge(std::vector < std::vector < std::string» input_vecs) {
- // Проверяем, что каждый вектор строк во входном векторе отсортирован
- assert(std::all_of(input_vecs.begin(), input_vecs.end(),
- [](const std::vector < std::string > & v) {
- return std::is_sorted(v.begin(), v.end());
- }));
- std::vector < std::string > result;
- // Сначала считаем суммарный размер всех векторов, чтобы зарезервировать нужный объем памяти
- size_t total_size = 0;
- for (const auto & vec: input_vecs)
- total_size += vec.size();
- result.reserve(total_size);
- // Используем merge для каждой пары соседних векторов
- for (auto it = input_vecs.begin(); it != input_vecs.end(); ++it) {
- if (it + 1 == input_vecs.end()) // Только один вектор остался
- {
- result.insert(result.end(), it -> begin(), it -> end()); // Добавляем оставшийся вектор в результат
- break;
- }
- std::vector < std::string > merged_vectors;
- // Сливаем два текущих вектора с помощью merge и добавляем результат в merged_vectors
- std::merge(it -> begin(), it -> end(), (it + 1) -> begin(), (it + 1) -> end(), std::back_inserter(merged_vectors));
- // Добавляем merged_vectors в результат
- result.insert(result.end(), merged_vectors.begin(), merged_vectors.end());
- }
- return result; // Возвращаем объединенный отсортированный вектор строк
- }
- // Пример использования функции
- int main() {
- std::vector < std::vector < std::string» input = {
- {
- "a",
- "c",
- "e"
- },
- {
- "b",
- "d"
- },
- {
- "f",
- "g",
- "h"
- }
- };
- std::vector < std::string > output = merge(input);
- for (const auto & str: output)
- std::cout« str« " ";
- std::cout« std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement