Iterating in a sorted manner over a std::vector<std::pair<T,U> > object

Question

I am reading a object from a database of type Foo, as defined below. This object is a vector of Foo Members, where a Foo Members consists of a string id and a container object.

typedef std::pair<std::string, Container> FooMember;
typedef std::vector<FooMember> Foo;

I wish to iterate over a Foo object in its sorted form, where sorting is done with respect to the id. To do this I am using the following function to create first a sorted version of the object. As you can see, the object is sorted in a case insensitive manner. Is there a better way for me to iterate over this object compared to how I am currently doing it?

Foo sortedFoo(Foo& value) const {
    Foo returnValue;
    returnValue.reserve(value.size());

    // use a map to sort the items
    std::map<std::string, FooMember> sortedMembers;
    {
        Foo::iterator i = value.begin();
        Foo::iterator end = value.end();
        for(; i!=end; ++i) {
            std::string name = i->first;
            boost::algorithm::to_lower(name);
            sortedMembers[name] = *i;
        }
    }

    // convert the map to a vector of its values in sorted order
    std::map<std::string, FooMember >::iterator i = sortedMembers.begin();
    std::map<std::string, FooMember >::iterator end = sortedMembers.end();
    for(; i!=end; ++i) {
        returnValue.push_back(i->second);
    }
    return returnValue;
}

Answer 1

You can use std::sort

#include <algorithm>

bool comparator(const FooMember& i, const FooMember& j)
{
    std::string str1 = i.first;
    boost::algorithm::to_lower(str1);
    std::string str2 = j.first;
    boost::algorithm::to_lower(str2);
    return (str1 < str2); 
}

void sortFoo(Foo& value) {
    std::sort (value.begin(), value.end(), comparator);
}

Or, you can keep Foo objects in a std::map<std::string, Foo> from the beginning so they remain always sorted.

Answer 2

Yes: Copy the vector, then use std::sort with a custom comparison predicate:

struct ByIdCaseInsensitive {
  bool operator ()(const FooMember& lhs, const FooMember& rhs) const {
    return boost::algorithm::to_lower_copy(lhs.first) <
           boost::algorithm::to_lower_copy(rhs.first);
  }
};

Way more efficient than filling a map, and then copying back to a vector.

The predicate would be even better if it used a proper Unicode collation algorithm, but that isn't available in the standard library or Boost.

Answer 3

The best way would be to use std::sort with a custom comparator for FooMembers:

bool cmp(const FooMember& lhs, const FooMember& rhs);

Foo sortedFoo(const Foo& value) const
{
  Foo tmp = value;
  return std::sort(tmp.begin(), tmp.end(), cmp);
}

where the comparison can be implemented with the help of std::lexicographical_compare and tolower:

#include <cctype> // for std::tolower

bool ci_cmp(char a, char b)
{
  return std::tolower(a) < std::tolower(b);
}

#include <algorithm> // for std::sort, std::lexicographical_compare

bool cmp(const FooMember& lhs, const FooMember& rhs) 
{
  return std::lexicographical_compare(lhs.first.begin(),
                                      lhs.first.end(),
                                      rhs.first.begin(),
                                      rhs.first.end(),
                                      ci_cmp);
}

Answer 4

You can also use std::sort with a lambda expression:

std::sort(value.begin(), value.end(), [](const FooMember &lhs, const FooMember &rhs)
{
    std::string str1 = i.first, str2 = j.first;
    boost::algorithm::to_lower(str1);
    boost::algorithm::to_lower(str2);
    return str1 < str2; 
});

Or use the version provided by erelender. It's up to you.

Answer 5

Semantically std::vector<std::pair<T,U> > is a std::map<T,U> (but implementations are usually different). If you can re-design Foo, you probably better do it. As side effect, you will get sorting for free.

typedef std::map<std::string, Container> Foo;