2

次のように std::map を変換する必要があります。

std::map<int, std::set<int> > t_contents;

このようなマップで：

std::map<int, std::vector<int> > seq;

私はこの方法で変換を行っています：

std::map<int, std::set<int> >::const_iterator it;
for(it = t_contents.begin(); it != t_contents.end(); ++it)
{    
    std::move((*it).second.begin(), (*it).second.end(), 
        std::back_inserter(seq[(*it).first])
    );   
}

マップには最大 100 万の要素が含まれ、各セットには最大 1 万の要素も含まれることを考慮してください。これは、スペースの浪費と時間の点で私が見つけた最良の解決策です。この作業を行うためのより良い方法はありますか?

4

2 に答える 2

3

ヒント付き挿入を使用すると、パフォーマンスが向上します (挿入ごとの償却定数)。

std::map<int, std::set<int> >::const_iterator it;
for (it = t_contents.begin(); it != t_contents.end(); ++it) {
    std::vector<int> &vec = seq.insert(seq.end(),
        std::make_pair(it->first, std::vector<int>()))->second;
    vec.reserve(it->second.size());
    vec.assign(it->second.begin(), it->second.end());
}

reserve再割り当てを防ぐために使用しvector::assign、イテレータ引数とともに使用します。よりも読みやすい（効率的ではないにしても）back_inserter。

別の方法として、ベクトルをマップに直接配置することもできますが、ヒントは引き続き使用します。

std::map<int, std::set<int> >::const_iterator it;
for (it = t_contents.begin(); it != t_contents.end(); ++it) {
    seq.emplace_hint(seq.end(), it->first,
        std::vector<int>(it->second.begin(), it->second.end());
}

moveset 要素は必要ないことに注意してください。それらはプリミティブであるため、移動はコピーと同じです。

これは、たとえば、イテレータ引数間の距離をチェックするかどうかに応じて、速くなったり遅くなったりする可能性がありinsertます (いずれにせよ、設定されたサイズでは O(n) です)。

于 2013-02-08T10:41:09.400 に答える
3

別のオプションは次のとおりです。

std::transform(t_contents.begin(), t_contents.end(), std::inserter(seq.begin()),
  [](const std::pair<const int, std::set<int>>& s) {
    std::vector<int> v;
    v.reserve(s.second.size());
    v.assign(s.second.begin(), s.second.end());
    return std::make_pair(s.first, std::move(v));
  }
);

s の移動intは無意味であり、std::setとにかくイテレータは const であるため、セットから移動することはできません。

ecatmur's answer のように、これはヒントを挿入することでメリットがあります。これinsert_iteratorは、への各割り当てinsertが前の挿入ポイントをヒントとして行うためです。これは、入力範囲が既に同じ順序でソートされているため、パフォーマンスが大幅に向上するため、連続する挿入はそれぞれラストに隣接。

于 2013-02-08T11:07:21.057 に答える