C++ sorting a vector or linked list

Question

I have an input file that I want to sort based on timestamp which is a substring of each record. I want to store multiple attributes of the

The list is currently about 1000 records. But, I want it to be able to scale up a bit just in case.

When I did it with a Linked List by searching the entire list for insertion it took about 20 seconds. Now, just filling up a vector and outputting to file is taking 4 seconds (does that sound too long)?

I would like to use merge sort or quick sort (merge sort appears to be a little easier to me). The trouble that I'm running into is that I don't see many examples of implementing these sorts using objects rather than primitive data types.

I could use either a vector or Linked list. The feedback that I've gotten from this site has been most helpful so far. I'm hoping that someone can sprinkle on the magic pixie dust to make this easier on me :)

Any links or examples on the easiest way to do this with pretty decent performance would be most appreciated. I'm getting stuck on how to implement these sorts with objects because I'm newbie at C++ :)

Here's what my new code looks like (no sorting yet):

class CFileInfo  
{  
    public:  
    std::string m_PackLine;  
    std::string m_FileDateTime;  
    int m_NumDownloads;  
};  
void main()  
{  
    CFileInfo packInfo;  
    vector<CFileInfo> unsortedFiles;  
    vector<CFileInfo>::iterator Iter;  
    packInfo.m_PackLine = "Sample Line 1";  
    packInfo.m_FileDateTime = "06/22/2008 04:34";  
    packInfo.m_NumDownloads = 0;  
    unsortedFiles.push_back(packInfo);  
    packInfo.m_PackLine = "Sample Line 2";  
    packInfo.m_FileDateTime = "12/05/2007 14:54";  
    packInfo.m_NumDownloads = 1;  
    unsortedFiles.push_back(packInfo);  
    for (Iter = unsortedFiles.begin(); Iter != unsortedFiles.end(); ++Iter )   
    {  
        cout << " " << (*Iter).m_PackLine;  
    }  
}  

Answer 1

I'm not sure I understood your question correctly, is your problem defining the sort functor? The STL sort is generally implemented as an introspective sort which is very good for most of the cases.

struct sort_functor
{
    bool operator()(const CFileInfo & a, const CFileInfo & b) const
    {

        // may be a little bit more subtle depending on what your strings look like
        return a.m_FileDateTime < b.m_FileDateTime;
    }
}

std::sort(unsortedFiles.begin(), unsortedFile.end(), sort_functor());

or using boost::lambda

std::sort(unsortedFiles.begin(), 
    unsortedFile.end(),
    bind(&CFileInfo::m_FileDateTime, _1) < bind(&CFileInfo::m_FileDateTime, _2));

Was it the needed information?