Iterate over std :: vector in sorted order

Question

I get the Foo vector from the API as follows:

std::vector<Foo> foos; 

Then I wrote a function called

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

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

How would you iterate over Foo objects in foos in sorted order, where sorting is done by key and case insensitive. In addition, I would prefer not to make a sorted copy of foos, since it is large.

Here's my attempt, which works, but I wonder if this 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

You make sure to repeat three times three times and sort them once. This is what makes your algorithm less efficient for large arrays. Why not change it to do the following

• std::vecotr<Foo*> over it to extract pointers in std::vecotr<Foo*> called fooPtrVec
• Change the compare function to find Foo * and use the key field for Foo to compare. Call YourNewComparisonFunction
• use std::sort(fooPtrVec.begin(), fooPtrVec.end(), YourNewComparisonFunction()) to sort the vector Foo *

Answer 2

As an alternative to your attempt, you can create an array of indices

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

using the 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 an array of indices

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

Now you can iterate through foos and / or keys with index pointers:

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

Answer 3

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

you need to increase your i, not your end!

Answer 4

You can use the key sorting kit for you and encapsulate them in a custom container for more convenient use:

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

If you have duplicate keys, you cannot use the set. You can replace it with a vector with only a few changes:

 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()); } //...