Sorted Insert into an STL Vector

C++ has an accompanying library called the “Standard Template Library” (STL) which bundles up lots of useful algorithms and makes them able to be used with generic types through templating.

In a recent application, I have been using a vector<PackageInfoRef> as an instance variable in a class. This choice was because the collection would grow and I also need index-based access to the collection. The inserts into the vector ensure that the collection is always totally ordered.

To achieve the ordering, the insert location into the collection is important. Inititally it seems that a binary-search technique would make sense to find the correct insertion point, but actually there is an STL method to help with this called lower_bound. Here is the code that finds the insertion point;

std::vector<PackageInfoRef>::const_iterator itInsertionPt
    = std::lower_bound(
        fPackages.begin(),
        fPackages.end(),
        package,
        &_IsPackageBefore); 

This makes use of a method that returns true if packageA should come earlier than packageB;

static bool _IsPackageBefore(const PackageInfoRef& packageA,
    const PackageInfoRef& packageB)
{
    int c = packageA->Title().ICompare(packageB->Title());
    if (c == 0)
        c = packageA->Name().Compare(packageB->Name());
    return c < 0;
}

The value of itInsertionPt is one after the last item that returned true from the method _IsPackageBefore. Now inserting into the vector is easy;

fPackages.insert(itInsertionPt, package);

The lower_bound method has thus saved alot of code required to do this sorted insert operation.