以排序顺序在std :: vector上进行迭代 [英] Iterate over a std::vector in sorted order

问题描述

我从API接收Foo的向量，如下所示：

I receive from an API a vector of Foo as follows:

std::vector<Foo> foos;

然后我写了一个名为

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

每个Foo对象的std :: string类型的键。

which iterates over the container and plucks out a key of type std::string for each Foo object.

如何以排序顺序遍历foo中的Foo对象，其中排序是在键上以不区分大小写的方式完成的。此外，我不想制作foos的排序副本，因为它的大小很大。

How would you iterate over the Foo objects in foos in sorted order, where sorting is done on the key and in a case insensitive manner. Additionally, I'd prefer not to make a sorted copy of foos since it is large in size.

这是我的尝试，但是我想知道它是否可以做得更好。

Here's my attempt, which works but I'm wondering if it can be done better.

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

推荐答案

三次并排序一次。这就是使得你的算法在大型数组上的性能降低。为什么不改变它来执行以下操作

You care currently iterating over foos three times and sorting it once. This is what will be making your algorithm less performant over large arrays. Why not change it to do the following

1. 遍历它以将指针抽取到 std :: vecotr& Foo *> 调用fooPtrVec


2. 更改您的比较函数以取消引用Foo *，并使用Foo上的键字段进行比较。调用函数YourNewComparisonFunction


3. 使用 std :: sort（fooPtrVec.begin（），fooPtrVec.end（），YourNewComparisonFunction（））以排序Foo *

1. iterate over it to extract the pointers into a std::vecotr<Foo*> called fooPtrVec
2. Change your comparison function to dereference a Foo* and use the key field on Foo for the comparison. Call the function YourNewComparisonFunction
3. use std::sort(fooPtrVec.begin(), fooPtrVec.end(), YourNewComparisonFunction()) to sort the vector of Foo*

这篇关于以排序顺序在std :: vector上进行迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！