Advertisement
Fen1848

Untitled

Jun 9th, 2023
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. // Функция, принимающая вектор векторов строк и объединяющая их в один отсортированный вектор строк
  7. std::vector < std::string > merge(std::vector < std::vector < std::string» input_vecs) {
  8.   // Проверяем, что каждый вектор строк во входном векторе отсортирован
  9.   assert(std::all_of(input_vecs.begin(), input_vecs.end(),
  10.     [](const std::vector < std::string > & v) {
  11.       return std::is_sorted(v.begin(), v.end());
  12.     }));
  13.  
  14.   std::vector < std::string > result;
  15.  
  16.   // Сначала считаем суммарный размер всех векторов, чтобы зарезервировать нужный объем памяти
  17.   size_t total_size = 0;
  18.   for (const auto & vec: input_vecs)
  19.     total_size += vec.size();
  20.  
  21.   result.reserve(total_size);
  22.  
  23.   // Используем merge для каждой пары соседних векторов
  24.   for (auto it = input_vecs.begin(); it != input_vecs.end(); ++it) {
  25.     if (it + 1 == input_vecs.end()) // Только один вектор остался
  26.     {
  27.       result.insert(result.end(), it -> begin(), it -> end()); // Добавляем оставшийся вектор в результат
  28.       break;
  29.     }
  30.  
  31.     std::vector < std::string > merged_vectors;
  32.     // Сливаем два текущих вектора с помощью merge и добавляем результат в merged_vectors
  33.     std::merge(it -> begin(), it -> end(), (it + 1) -> begin(), (it + 1) -> end(), std::back_inserter(merged_vectors));
  34.     // Добавляем merged_vectors в результат
  35.     result.insert(result.end(), merged_vectors.begin(), merged_vectors.end());
  36.   }
  37.  
  38.   return result; // Возвращаем объединенный отсортированный вектор строк
  39. }
  40.  
  41. // Пример использования функции
  42. int main() {
  43.   std::vector < std::vector < std::string» input = {
  44.     {
  45.       "a",
  46.       "c",
  47.       "e"
  48.     },
  49.     {
  50.       "b",
  51.       "d"
  52.     },
  53.     {
  54.       "f",
  55.       "g",
  56.       "h"
  57.     }
  58.   };
  59.   std::vector < std::string > output = merge(input);
  60.   for (const auto & str: output)
  61.     std::cout« str« " ";
  62.   std::cout« std::endl;
  63.   return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement