How to Organize a List Using Structs in C++

The C++ standard library's list implementation provides a powerful way to sort a list of objects.

Linked lists are useful for dynamic lists of objects that will change frequently. A linked list can perform list insertions and deletions in constant time, while dynamic arrays perform these tasks in linear time. This benefit for insertion and deletion comes at a price of having a slower access time, as the list must be traversed each time a different index is desired. This lack of random access means that you cannot use a standard sorting algorithm such as "qsort," which is an implementation of the quick sort algorithm found in the C++ standard library. Luckily, the designers of std::list provided specific sorting tools that are well documented and straightforward to use.

Instructions

1. Include the standard library's list header into your code file. This may already be included if you have defined the list object in your source code.

   #include <list>

2. Modify the implementation of the structure you will be sorting to overload the "<" operator. This operator is used by std::list when sorting the list. Ensure that you select the proper data field to sort on, otherwise the sorting results may not be as expected.

   // This is an example structure. Modify your existing structure to utilize the < operator

   struct MyStruct

   {

   int m_dataToSortOn;

   bool operator < (const MyStruct & rhs)

   {

   return this.m_dataToSortOn < rhs.m_dataToSortOn;

   }

   };

3. Call the "sort" method on your list object. This will sort the list of objects based on the output of the "<" operator.

   // Sort the list of data

   myList.sort();

Tips & Warnings

• You can change the sorting criteria for your structure by modifying the comparison operator to use a different data field for the comparison.

• You can also supply a comparison function to the list's sort method. This should take two parameters, and return a boolean value indicating if parameter one is less than parameter two.

• The comparison operator expects that the "<" operator is implemented for whichever data field you are using for the comparison. If you are comparing objects of a custom type, ensure that the custom type has implemented the "<" operator as well.

References

• CPlusPlus.com - list
• CPlusPlus.com - list::sort

Resources

• CPlusPlus.com - list::sort