Iterate over a std::vector in sorted order [closed]

Question

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

std::vector<Foo> foos;

I have then written a function called

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

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

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

Answer 1

Alternatively to your attempt, you may create an array of indexes

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

using a comparator:

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

sort this indexes array

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

Now you can iterates foos and/or keys with the indexes indirection:

std::vector<Foo*> sortedFoos;
for (size_t i = 0; i != indexes.size(); ++i) {
    sortedFoos.push_back(&foos[indexes[i]]);
}

Answer 2

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. 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*

Answer 3

for(;i!=end;++end)

you have to increment your i not your end!