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

Solution 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;

Solution 2

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.

Solution 3

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

Solution 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

View more solutions

Comments

[Billy ONeal]

Oooh. Didn't consider that. +1

[Slava]

-1 your answer almost completely unrelated to the question. It is funny how people blindly +1

[WhozCraig]

+1 Provided the comparator is smart enough, in a pinch the OP doesn't have to change the keys at all; the comparator can xform them during comparison-only. Expensive, yes, but at least workable. Solid answer.

[John Dibling]

@WhozCraig: Certainly workable. It's a lot of work, though, and bug-prone. If OP cannot change the keys for whatever reason, that't probably what I'd do.

[Billy ONeal]

@Slava: I don't see how it is almost completely unrelated. The only difference between the OP's desired output and actual output is that the actual output is in the reverse order. (s)he has provided no other information describing what is going on. John's answer (where the OP just used a string instead of a proper date type) is also likely, which is why he got a +1 from me.

[WhozCraig]

@JohnDibling Yup, only reason I brought it up. I would, of course, prefer having naturally sortable keys as you describe here, and strongly advise the OP consider it.

[Admin]

Hi there thanks for the reply, i have thought of using numeric before. But let's say if i were to strictly follow that the string date format e.g. "01OCT1992" is there any other alternatives?

[John Dibling]

@user3165815: Yes, what WhozCraig said. But like I said it's a lot of work and error-prone. Do you have to stick to that format?

[Slava]

Yes formally you may provide your answer for provided data, but it is pretty obvious, that OP wants to sort data chronologically, not blindly reverse that 2 lines. So -1

[Admin]

@JohnDibling yes i will probably need to stick to that format cause it's shown as an example for my assignment..

[John Dibling]

@user3165815: Well then you've got some work to do. See my edit.

[Admin]

@JohnDibling great, thank you for showing me where to start off! will report back when i'm done :)

[Admin]

I have finished up the code u left and got it worked out and left a reference on my question. Thanks again!