子集std：：映射到预定义长度的std::vector<std::map>中

Question

我正在尝试将一个std::map<string,string>子集为一个映射向量，每个映射都具有预先定义的长度+ rest。我试图遵循在这个link上找到的解决方案。这里的问题是，我不想将映射分割成两个部分，而是将其分成n部分，每个部分都大小相同+ rest。我就是这样做的(不是因为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;
}

我认为我被困在移动迭代器的下界。

Answer 1

IMHO的“其余部分”定义不清，因为(例如)将20个元素分成11个部分将产生10个部分，每个元素1个元素，而一个“rest”元素包含10个元素，如果分裂应该是一致的，这是(某种程度上)丑陋的。相反，我将使用9个部分，每个部分有2个元素，然后每个元素使用2个“rests”元素。但这只是一个(早期)的副词，你可以随意调整。

重要的部分可能是迭代器。因为您要从同一类型的map中删除元素并将元素插入其中，所以最好的选择是extract()及其对应的insert()重载，它接受节点。这样做的好处是，您在map do 而不是中使用的类型需要支持移动语义；整个节点仍然存在，因此不需要移动。这里也不涉及move_iterator --如果我们取消迭代器的引用，那么只会影响到，而我们没有这样做。

首先，让我们为任何map-like类型和任何vector-like类型定义map拆分(节点传输)，因为我们可以：

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] )
   }

当涉及到一种不同的分裂为均匀的部分和“其余的”，该算法可以很容易地调整。

Answer 2

如果要将映射子集为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;
    }
}