子集 std::map 到预定义长度的 std::vector<std::map>

subset std::map into std::vector<std::map> of predefined length

我正在尝试将 std::map<string,string> 子集化为映射矢量，每个映射都具有预定义的长度 + 剩余部分。我正在尝试遵循在此 中找到的解决方案。这里的问题是我不想将地图分成两部分，而是分成 n 个大小相等的部分 + 其余部分。这就是我试图实现这一目标的方式（由于 nullptr 而未编译）：

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <map>

int main(){
using namespace std::string_literals;

    auto code = std::map<std::string, std::string>{
        {"Red"s, "Red"s},
        {"Blue"s, "Blue"s},
        {"Green"s, "Green"s},
        {"Fuchsia"s, "Fuchsia"s},
        {"Mauve"s, "Mauve"s},
        { "Gamboge"s, "Gamboge"s },
        {"Vermillion"s, "Vermillion"s}
    };
    
    std::vector<std::map<std::string,std::string>> subsetCode;
    auto it = code.begin();
    auto bt = code.begin();
    for (size_t i = 0; i < code.size(); i += 2)
        {
            auto last = std::min(code.size(), i + 2);
            
            std::advance(it, last);
            std::advance(bt, last-2);
            subsetCode.push_back(std::map{
                std::make_move_iterator(bt),
                std::make_move_iterator(it)});
        }
    
    for (int i = 0; i < subsetCode.size(); i++) {
        for (auto [key, value]: subsetCode[i]){
            std::cout << key << ":" << value << " ";
        }
        std::cout << " " << std::endl;
    }

    return 1;
}

我想我无法移动下界的迭代器。

如果你想将地图子集化为 n 个部分，子地图的大小等于 map.size()/n，听说是一个 o(n) 的解决方案：

#include <iostream>
#include <string>
#include <vector>
#include <map>

int main() {
    auto code = std::map<std::string, std::string>{
        {"Red", "Red"},
        {"Blue", "Blue"},
        {"Green", "Green"},
        {"Fuchsia", "Fuchsia"},
        {"Mauve", "Mauve"},
        { "Gamboge", "Gamboge" },
        {"Vermillion", "Vermillion"}
    };
    
    // assume you want each part size is 2.
    constexpr int subSize = 2; 

    std::vector<std::map<std::string, std::string>> subsetCodes;    
    std::map<std::string, std::string> subset;
    for (auto& item : code) {
        subset.insert({item.first, std::move(item.second)});
        while (subset.size() == subSize) {
            subsetCodes.push_back(std::move(subset));
            subset = std::map<std::string, std::string>();
        }
    }
    if (!subset.empty())
      subsetCodes.push_back(std::move(subset));
    code.clear();
    
    for (int i = 0; i < subsetCodes.size(); i++) {
        for (auto [key, value]: subsetCodes[i]){
            std::cout << key << ":" << value << " ";
        }
        std::cout << " " << std::endl;
    }
}

恕我直言，“其余”定义不明确，因为（例如）将 20 个元素分成 11 个部分会产生 10 个部分，每个部分有 1 个元素，而“其余部分”有 10 个元素，如果分裂应该是均匀的。我会改为使用 9 个部分，每个部分包含 2 个元素，然后使用 2 个“休止符”，每个部分包含 1 个元素。但这只是一个（早期的）旁注；你可以随心所欲地调整它。

重要的部分可能是迭代器。好吧，因为您要从相同类型的 map 中删除元素并将元素插入到相同类型的 map 中，所以最好的选择是 extract() 及其对应物，即采用节点的 insert() 的重载。这样做的美妙之处在于，在这种情况下，您在 map 中使用的类型 而不是 需要完全支持移动语义；整个节点仍然存在，因此不需要移动任何东西。这里也不涉及 move_iterator — 如果我们取消引用迭代器，那么 仅 很重要，而我们没有这样做。

首先让我们为 any map-like 类型和 any[=39 定义 map 分裂（节点转移） =] vector-like 类型，只是因为我们可以：

template<template<typename ... S> class R,
         template<typename ... A> class C,
         typename I,
         typename ... S, typename ... A>
void
transfer_segments(C<A...> &source, I &it,
                  size_t n_segs, const size_t seg_size,
                  R<C<A...>, S...> &sink) {
  for (; n_segs; --n_segs) {
    auto &seg{sink.emplace_back()};
    for (size_t i{0}; i < seg_size; ++i)
      seg.insert(source.extract(it++));
  }
}

template<template<typename ... S> class R,
         template<typename ... A> class C,
         typename ... S, typename ... A>
void
split_container(C<A...> &&source, const size_t n_segs,
                R<C<A...>, S...> &sink) {
  const size_t seg_leftover{source.size() % n_segs};
  const size_t seg_size{source.size() / n_segs};
  auto it{source.begin()};
  transfer_segments(source, it, seg_leftover, seg_size + 1, sink);
  transfer_segments(source, it, n_segs - seg_leftover, seg_size, sink);
}

这些模板可以使用 C++20 概念获得（非常需要）额外的类型安全性，但为了简洁起见省略了这一点。接下来我们可以根据您的数据和类型测试解决方案：

#include <iostream>
#include <map>
#include <string>
#include <vector>

namespace { /* ... magic templates from above go here ... */ }

int main() {
  static const auto get_map{
    []() -> std::map<std::string, std::string> {
      using namespace std::string_literals;
      return {{"Red"s, "Red"s},
              {"Blue"s, "Blue"s},
              {"Green"s, "Green"s},
              {"Fuchsia"s, "Fuchsia"s},
              {"Mauve"s, "Mauve"s},
              {"Gamboge"s, "Gamboge"s},
              {"Vermillion"s, "Vermillion"s}};
    }};

  for (size_t n_segs{1}; n_segs <= 7; ++n_segs) {
    std::cout << n_segs << ": {\n";
    std::vector<std::map<std::string, std::string>> segs;
    split_container(get_map(), n_segs, segs);
    for (const auto &seg : segs) {
      std::cout << "     (";
      for (const auto &[k, v] : seg)
        std::cout << " [" << k << ':' << v << ']';
      std::cout << " )\n";
    }
    std::cout << "   }\n";
  }
}

输出为：

1: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] [Gamboge:Gamboge] [Green:Green] [Mauve:Mauve] [Red:Red] [Vermillion:Vermillion] )
   }
2: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] [Gamboge:Gamboge] [Green:Green] )
     ( [Mauve:Mauve] [Red:Red] [Vermillion:Vermillion] )
   }
3: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] [Gamboge:Gamboge] )
     ( [Green:Green] [Mauve:Mauve] )
     ( [Red:Red] [Vermillion:Vermillion] )
   }
4: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] )
     ( [Gamboge:Gamboge] [Green:Green] )
     ( [Mauve:Mauve] [Red:Red] )
     ( [Vermillion:Vermillion] )
   }
5: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] )
     ( [Gamboge:Gamboge] [Green:Green] )
     ( [Mauve:Mauve] )
     ( [Red:Red] )
     ( [Vermillion:Vermillion] )
   }
6: {
     ( [Blue:Blue] [Fuchsia:Fuchsia] )
     ( [Gamboge:Gamboge] )
     ( [Green:Green] )
     ( [Mauve:Mauve] )
     ( [Red:Red] )
     ( [Vermillion:Vermillion] )
   }
7: {
     ( [Blue:Blue] )
     ( [Fuchsia:Fuchsia] )
     ( [Gamboge:Gamboge] )
     ( [Green:Green] )
     ( [Mauve:Mauve] )
     ( [Red:Red] )
     ( [Vermillion:Vermillion] )
   }

当涉及到不同类型的拆分成统一部分和“其余部分”时，可以轻松调整算法。