按排序顺序迭代std :: vector

Question

我从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);
}

Answer 1

除了您的尝试,您可以创建一个索引数组

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

Answer 2

您当前关心的是对 foos 进行三次迭代并对其进行一次排序。这将使您的算法在大型数组上的性能降低。为什么不将其更改为执行以下操作

1. 迭代它以将指针提取到std::vecotr<Foo*>名为 fooPtrVec 的对象中
2. 更改比较函数以取消引用 Foo* 并使用 Foo 上的键字段进行比较。调用函数 YourNewComparisonFunction
3. 用于std::sort(fooPtrVec.begin(), fooPtrVec.end(), YourNewComparisonFunction())对 Foo* 的向量进行排序