6

次のように、API から Foo のベクトルを受け取ります。

std::vector<Foo> foos;

次に、という関数を作成しました

std::vector<std::string> getKeys(const std::vector<Foo>&)

コンテナーを反復処理し、各 Foo オブジェクトの std::string 型のキーを取り出します。

foos の Foo オブジェクトをソートされた順序でどのように反復処理しますか。ソートはキーで大文字と小文字を区別しない方法で行われます。さらに、サイズが大きいため、foos のソートされたコピーを作成したくありません。

これが私の試みです。これは機能しますが、もっとうまくできるかどうか疑問に思っています。

struct CaseInsensitiveComparitor {
    bool operator ()(const std::pair<std::string, Foo&> lhs, const std::pair<std::string, Foo&> rhs) const {
        std::string str1 = lhs.first;
        boost::algorithm::to_lower(str1);
        std::string str2 = rhs.first;
        boost::algorithm::to_lower(str2);
        return (str1 < str2);
    }
};

// map key to Foo
std::vector<std::pair<std::string, Foo*> > tempFoos;
{
   std::vector<std::string> keys = getKeys(foos);
   std::vector<std::string>::iterator begin = keys.begin();
   std::vector<std::string>::iterator i = keys.begin();
   std::vector<std::string>::iterator end = keys.end();
   for(;i!=end;++i)
   {
       tempFoos.push_back(*i, &foos[distance(begin,i)]);
   }

   std::sort(tempFoos.begin(), tempFoos.end(), CaseInsensitiveComparitor());
}

std::vector<Foo*> sortedFoos;
std::vector<std::pair<std::string, Foo*> >::iterator i = tempFoos.begin();
std::vector<std::pair<std::string, Foo*> >::iterator end = tempFoos.end();   
for(;i!=end;++i)
{
   sortedFoos.push_back(i->second);
}
4

4 に答える 4

8

あなたの試みの代わりに、インデックスの配列を作成することができます

std::vector<size_t> indexes;
for (size_t i = 0; i != keys.size(); ++i) { indexes.push_back(i); }

コンパレータを使用して：

struct Comparator {
    explicit Comparator(const std::vector<string>& keys) : keys(&keys) {}

    bool operator ()(size_t lhs, size_t rhs) const {
        std::string str1 = (*keys)[lhs];
        boost::algorithm::to_lower(str1);
        std::string str2 = (*keys)[rhs];
        boost::algorithm::to_lower(str2);
        return (str1 < str2);
    }
private:
    const std::vector<string>* keys;
};

このインデックス配列を並べ替えます

std::sort(indexes.begin(), indexes.end(), Comparator(keys));

これで、インデックスの間接化を使用して foos および/またはキーを反復できます。

std::vector<Foo*> sortedFoos;
for (size_t i = 0; i != indexes.size(); ++i) {
    sortedFoos.push_back(&foos[indexes[i]]);
}
于 2013-09-05T12:46:26.037 に答える
4

現在、foos を 3 回反復処理し、1 回ソートしています。これが、大規模な配列でアルゴリズムのパフォーマンスを低下させる原因です。次のように変更してみませんか

  1. それを反復して、std::vecotr<Foo*>呼び出された fooPtrVecにポインターを抽出します
  2. Foo* を逆参照するように比較関数を変更し、比較のために Foo のキー フィールドを使用します。関数 YourNewComparisonFunction を呼び出します
  3. std::sort(fooPtrVec.begin(), fooPtrVec.end(), YourNewComparisonFunction())Foo* のベクトルをソートするために使用します
于 2013-09-05T13:22:42.987 に答える
0

セットを使用してキーをソートし、それらをカスタム コンテナーにカプセル化して、より便利に使用できます。

class Foo
{
  public :
    Foo(const std::string & key) : key(key) {}
    const std::string & get_key() const { return key; }
  private :
    std::string key;
};

std::ostream & operator<<(std::ostream & stream, const Foo & foo) { stream << foo.get_key(); return stream; }

class SortedFoo
{
  typedef std::set<std::pair<std::string,Foo*> > SortedFoos;
  SortedFoos mFoos;

public :
  SortedFoo(std::vector<Foo> & foos)
  {
    const std::vector<Foo>::iterator end = foos.end();
    for(std::vector<Foo>::iterator iter = foos.begin(); iter != end; ++iter)
    {
      mFoos.insert(std::make_pair(boost::algorithm::to_lower_copy(iter->get_key()), &(*iter)));
    }
  }

  class Iterator : public std::iterator<std::forward_iterator_tag, Foo>
  {
    private:
      Iterator(SortedFoos::iterator iter) : mIter(iter) {}
      SortedFoos::iterator mIter;

    public :
      Iterator & operator ++ () { ++mIter; return *this; }
      bool operator != (const Iterator & other) const { return mIter != other.mIter; }
      Foo & operator * () { return *mIter->second; }
      Foo * operator -> () { return mIter->second; }

      friend class SortedFoo;
  };

  typedef Iterator iterator;

  iterator begin() { return Iterator(mFoos.begin()); }
  iterator end() { return Iterator(mFoos.end()); }
};

int main(int argc, const char** argv)
{
  std::vector<Foo> foos;
  foos.push_back(Foo("def"));
  foos.push_back(Foo("Jkl"));
  foos.push_back(Foo("yz "));
  foos.push_back(Foo("pqr"));
  foos.push_back(Foo("Mno"));
  foos.push_back(Foo("ghi"));
  foos.push_back(Foo("vwx"));
  foos.push_back(Foo("Abc"));
  foos.push_back(Foo("stu"));

  SortedFoo sorted(foos);
  std::copy(sorted.begin(), sorted.end(), std::ostream_iterator<Foo>(std::cout, " "));

  return 0;
}

重複したキーがある場合、セットは使用できません。少し変更するだけで、これをベクターに置き換えることができます。

typedef std::vector<std::pair<std::string,Foo*> > SortedFoos;
//...
SortedFoo(std::vector<Foo> & foos)
{
  const std::vector<Foo>::iterator end = foos.end();
  for(std::vector<Foo>::iterator iter = foos.begin(); iter != end; ++iter)
  {
    mFoos.push_back(std::make_pair(boost::algorithm::to_lower_copy(iter->get_key()), &(*iter)));
  }
  std::sort(mFoos.begin(), mFoos.end());
}
//...
于 2013-09-05T13:59:14.420 に答える