Перебрать std::vector в отсортированном порядке

Вы заботитесь о том, чтобы в настоящее время перебирать foos три раза и сортировать его один раз. Это то, что сделает ваш алгоритм менее производительным на больших массивах. Почему бы не изменить его, чтобы сделать следующее

1. перебрать его, чтобы извлечь указатели в std::vecotr<Foo*> с именем fooPtrVec
2. Измените функцию сравнения, чтобы разыменовать Foo*, и используйте ключевое поле в Foo для сравнения. Вызовите функцию YourNewComparisonFunction
3. используйте std::sort(fooPtrVec.begin(), fooPtrVec.end(), YourNewComparisonFunction()) для сортировки вектора Foo*

В качестве альтернативы вашей попытке вы можете создать массив индексов

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

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

вы должны увеличить свой я не ваш конец!

Вы можете использовать набор для сортировки ключей и инкапсулировать их в пользовательский контейнер для более удобного использования:

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