STL Map sorting

Question

UPDATED: I have followed John's guidance and modified his code which solved my problem via creating a comparator function and and insert it to the Compare parameter in STL map. Since my string date are strictly in the shown format, using substr will be fine. My output and codes are below for your reference.

Date            Total Sales
01JAN1900       $4
20JAN1902       $40
18NOV1912       $2500
19NOV1912       $2500
19OCT1923       $25
01JAN1991       $22
15NOV1991       $300
Grand Total:    $5391


 struct CompareDates 
:
  public std::binary_function <bool, std::string, std::string>
{
  bool operator() (const std::string& lhs, const std::string& rhs)
  {


     if(lhs.substr(5,4) < rhs.substr(5,4))
     {
         return true;

     }
     else if (lhs.substr(5,4) == rhs.substr(5,4) && lhs.substr(2,3) < rhs.substr(2,3))
     {
         return true;
     }
     else if (lhs.substr(5,4) == rhs.substr(5,4) && lhs.substr(2,3) == rhs.substr(2,3) && lhs.substr(0,2) < rhs.substr(0,2))
     {
         return true;

     }
     else
     {
         return false;
     }


  }
};

map<string, double,CompareDates> dailyDatePrices;

Initial Problem: I am required to sort raw data into a daily report format. As such I have used STL map to store the date as the key and the item price as the value. From what I read, STL map is automatically sorted. However I do not want it to be sorted by map as it will generate the undesired current report output stated below. I will want to sort based on the string date(earliest to latest) and will want it to be that exact format. I have used vector and function comparator to sort the date already before using map. Is there any way to go about doing it? Thanks!

Raw Data
STRAW:10:15NOV1991
TOY:10:15NOV1991
BARLEY:5:01OCT1992

Undesired Current Report Output
01OCT1992 5
15NOV1991 20

Expected Report Output
15NOV1991 20
01OCT1992 5

Answer 1

A std::map is sorted. There is no way to construct a map that isn't sorted.

The problem isn't the fact that the map is sorted. The problem is how your keys are designed.

You've said that your key is a date, but what it really is is a string. How can the map know that the data in the string is actually a date, and that it should sort somehow by the year first, then the month, then the day? It can't. You have to tell it to do this.

Change your keys to be strings in this format:

YYYYMMDD

where Y, M and D are all numeric. Don't try to use NOV for november -- use 11 instead.

You could also use unsigned longs for the key instead of strings. This would make comparison quicker, but computing the values is a bit trickier.

---

If you must stick to the original format for they keys, then you have a bit of work to do. The map is sorted according to the map's comparator, which is specified as one of it's template parameters:

[C++03 Example]

struct CompareDates 
:
  public std::binary_function <bool, std::string, std::string>
{
  bool operator() (const std::string& lhs, const std::string& rhs)
  {
    // return true if lhs < rhs
    // return false otherwise

    // step 1:  compare years.  if lhs.year < rhs.year, return true.  else, continue
    // step 2: compare months.  if lhs.month < rhs.month, return true.  else, continue.
    //    note:  don't just compare the strings, else "AUG" < "JAN" etc
    // step 3: compare days.  if lhs.day < rhs.day, return true.  else, return false.
  }
};

Since this appears to be homework, I'll let you fill in the missing bits above. :)

Using this comparator to compare keys, you can instantiate a map that does the correct sorting automatically:

std::map <Key, Value, CompareDates> myMap;

Answer 2

If all you want to do is sort the map in reverse order to what it currently uses, you just give it a std::greater comparator instead of the default, std::less.

std::map<date, other_type, std::greater<date>> example;
// Otherwise use example

Example:

#include <iostream>
#include <functional>
#include <map>

int main() {
    std::map<int, float, std::greater<int>> example;
    example.emplace(std::make_pair(10, 10.0));
    example.emplace(std::make_pair(12, 12.0));

    for (auto const& entry : example)
    {
        std::cout << "Key: " << entry.first << " " << entry.second << std::endl;
    }

    return 0;
}

http://ideone.com/9Guuil

Answer 3

One way to go about lexical sorting temporal data is to convert it to the following form:

From: 01OCT1992
To: 1992-10-01

Now the default operator< for comparing string will work when sorting dates, since earlier dates will always be lexicographically less.

Answer 4

To me, a clear design is to just define a Date class with proper day/month/year data members (and public accessors, with proper check to field values, e.g. check that months must be in range 1...12, etc.).

Then you can overload operator< defining a proper sorting on Date instances.

And then you can simply have a std::map<Date, int> (where int is used to store prices), and things will work simply "out of the box", thanks to proper sorting definition on the Date map-key.

If you want to format dates in a particular way, you can define a function that takes a Date as input, and returns the formatted date string (this can be modified basing on internationalization/localization issues; I think it's important to separate this output formatting aspect from the "business logic").

Compilable code follows (simply tested with VS2012):

#include <iostream> // for std::cout, std::endl
#include <map>      // for std::map
#include <sstream>  // for std::ostringstream
#include <string>   // for std::string
#include <vector>   // for std::vector
using namespace std;

// A simple date.
// In real world code, this should be a class with private
// date members, and proper accessors.
struct Date {
    int day;
    int month;
    int year;

    Date() : day(0), month(0), year(0) {}

    Date(int d, int m, int y)
        : day(d), month(m), year(y)
    {}
};

// Define proper sorting for dates
bool operator<(const Date& d1, const Date& d2) {
    // First compare years
    if (d1.year < d2.year)
        return true;
    if (d1.year > d2.year)
        return false;

    // Same year, compare months
    if (d1.month < d2.month)
        return true;
    if (d1.month > d2.month)
        return false;

    // Same year and month, compare days
    return (d1.day < d2.day);
}

// Format dates in a specific format
string FormatDate(const Date& date) {
    // NOTE: bounds checking for day and month omitted.

    ostringstream os;

    if (date.day < 10)
        os << '0';
    os << date.day;

    static const char* monthNames[] = {
        "JAN", "FEB", "MAR", "APR",
        "MAY", "JUN", "JUL", "AUG",
        "SEP", "OCT", "NOV", "DEC"
    }; 
    os << monthNames[date.month - 1];

    os << date.year;

    return os.str();
}

struct Item {
    string type;
    int price;
    Date date;

    Item(const string& t, int p, const Date& d)
        : type(t), price(p), date(d)
    {}
};


int main() {
    vector<Item> items;
    items.push_back(Item("STRAW", 10, Date(15, 11, 1991)));
    items.push_back(Item("TOY",   10, Date(15, 11, 1991)));
    items.push_back(Item("BARLEY", 5, Date( 1, 10, 1992)));

    map<Date, int> priceData;
    for (const auto& item : items) {
        auto where = priceData.find(item.date);
        if (where != priceData.end()) {
            where->second += item.price;
        } else {
            priceData[item.date] = item.price;
        }
    }

    for (const auto& e : priceData) {
        cout << FormatDate(e.first) << " " << e.second << endl;
    } 
}

---

Output:

15NOV1991 20
01OCT1992 5