c++ - std::map から項目をフィルタリングする方法は?

Question

おおよそ次のコードがあります。これをより良く、またはより効率的にすることはできますか? おそらく使用していstd::remove_ifますか？移動中にマップからアイテムを削除できますか? 一時的な地図の使用を避けることはできますか?

typedef std::map<Action, What> Actions;
static Actions _actions;

bool expired(const Actions::value_type &action)
{
  return <something>;
}

void bar(const Actions::value_type &action)
{
  // do some stuff
}

void foo()
{
  // loop the actions finding expired items
  Actions actions;
  BOOST_FOREACH(Actions::value_type &action, _actions)
  {
    if (expired(action))
      bar(action);
    else
      actions[action.first]=action.second;
    }
  }
  actions.swap(_actions);
}

score 53 · Accepted Answer

Mark Ransom アルゴリズムのバリエーションですが、一時的なものは必要ありません。

for(Actions::iterator it = _actions.begin();it != _actions.end();)
{
    if (expired(*it))
    {
        bar(*it);
        _actions.erase(it++);  // Note the post increment here.
                               // This increments 'it' and returns a copy of
                               // the original 'it' to be used by erase()
    }
    else
    {
        ++it;  // Use Pre-Increment here as it is more effecient
               // Because no copy of it is required.
    }
}

score 30 · Accepted Answer

erase() を使用できますが、BOOST_FOREACH が無効化されたイテレータをどのように処理するかはわかりません。map::eraseのドキュメントには、消去されたイテレータのみが無効化され、他のイテレータは問題ないと記載されています。内側のループを再構築する方法は次のとおりです。

Actions::iterator it = _actions.begin();
while (it != _actions.end())
{
  if (expired(*it))
  {
    bar(*it);
    Actions::iterator toerase = it;
    ++it;
    _actions.erase(toerase);
  }
  else
    ++it;
}

score 4 · Accepted Answer

誰も知らないようですが、任意のコンテナーで使用すると、erase が有効であることが保証された新しいイテレーターを返すということです。

Actions::iterator it = _actions.begin();
while (it != _actions.end())
{
  if (expired(*it))
  {
    bar(*it);
    it = _actions::erase(it);
  }
  else
    ++it;
}

この場合、イテレータの安定性が保証されていないため、actions.end() を格納することはおそらく適切な計画ではありません。

score 1 · Accepted Answer

期限切れのアイテムを削除することが目的の場合は、map::eraseを使用してみませんか? この方法では、保持したいすべての要素を含むコピー全体を再構築する必要はなく、不要になった要素を削除するだけで済みます。

これを行う方法は、消去したい要素を指す反復子を保存し、反復が終了した後にそれらをすべて消去することです。

または、アクセスした要素を保存し、次の要素に移動してから、一時要素を消去できます。ただし、ループの境界が台無しになるため、反復を自分で微調整する必要があります。

expired() の実装方法によっては、他にもっと良い方法があるかもしれません。たとえば、マップのキーとしてタイムスタンプを追跡している場合 (expired() が意味するように?)、現在のタイムスタンプで upper_bound を実行でき、範囲 [ begin(), upper_bound() ) 内のすべての要素が必要です。処理して消去します。

c++ - std::map から項目をフィルタリングする方法は?

4 に答える 4

Related

Reference