How to sort a list of string‑based dates in C++

2 Answers

0 votes
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <optional>


/*
    Sorting string-based dates in C++ using the standard library.

    This program demonstrates:
    - Converting date strings into std::tm using std::get_time
    - Modular parsing and sorting functions
    - Error handling for malformed dates
    - Multiple test cases, including edge cases
    - Notes on performance, memory, and pitfalls inside the code

    Format used: "DD Mon YYYY" (e.g., "24 Jun 2020")
*/


// ------------------------------------------------------------
// Parse a date string into std::tm
// ------------------------------------------------------------
std::optional<std::tm> parse_date(const std::string& s) {
    /*
        Converts a date string into a std::tm structure.

        Uses std::get_time, which is safe and does not execute arbitrary code.
        If parsing fails, returns std::nullopt so the caller can decide how to handle it.

        Complexity: O(length of string)
        Pitfall: std::get_time is locale-dependent; using "%d %b %Y" requires English month abbreviations.
    */

    std::tm tm{};
    std::istringstream iss(s);

    iss >> std::get_time(&tm, "%d %b %Y");
    if (!iss.fail()) {
        return tm;
    }
    return std::nullopt;
}


// ------------------------------------------------------------
// Sort a list of date strings
// ------------------------------------------------------------
std::vector<std::string> sort_dates(const std::vector<std::string>& dates) {
    /*
        Steps:
        1. Parse each date into std::tm.
        2. Store (tm, original string) pairs.
        3. Sort by tm.
        4. Return sorted original strings.

        Complexity:
            - Parsing: O(n)
            - Sorting: O(n log n)
            - Total: O(n log n)

        Memory:
            - Temporary vector of parsed results proportional to input size.

        Pitfalls:
            - Invalid dates must be handled.
            - Mixed formats will fail parsing.
    */

    struct Parsed {
        std::tm tm;
        std::string original;
    };

    std::vector<Parsed> parsed;
    parsed.reserve(dates.size());

    for (const auto& d : dates) {
        auto tm_opt = parse_date(d);
        if (!tm_opt) {
            throw std::runtime_error("Invalid date: " + d);
        }
        parsed.push_back({*tm_opt, d});
    }

    std::sort(parsed.begin(), parsed.end(),
              [](const Parsed& a, const Parsed& b) {
                  // Compare tm fields lexicographically
                  // std::tm stores year since 1900, month 0–11, etc.
                  if (a.tm.tm_year != b.tm.tm_year) return a.tm.tm_year < b.tm.tm_year;
                  if (a.tm.tm_mon  != b.tm.tm_mon)  return a.tm.tm_mon  < b.tm.tm_mon;
                  return a.tm.tm_mday < b.tm.tm_mday;
              });

    std::vector<std::string> result;
    result.reserve(parsed.size());
    for (const auto& p : parsed) {
        result.push_back(p.original);
    }

    return result;
}


// ------------------------------------------------------------
// Test harness
// ------------------------------------------------------------
void run_test(const std::string& name, const std::vector<std::string>& dates) {
    std::cout << "\nTest case: " << name << "\n";
    std::cout << "Input:\n";
    for (const auto& d : dates) std::cout << "  " << d << "\n";

    try {
        auto sorted = sort_dates(dates);
        std::cout << "Sorted:\n";
        for (const auto& d : sorted) std::cout << "  " << d << "\n";
    } catch (const std::exception& ex) {
        std::cout << "Error: " << ex.what() << "\n";
    }
}


// ------------------------------------------------------------
// Main
// ------------------------------------------------------------
int main() {
    /*
        Multiple test cases:
        - Normal dates
        - Already sorted
        - Reverse sorted
        - Duplicate dates
        - Invalid date
        - Empty list
    */

    run_test("Normal case",
             {"24 Jun 2020", "25 Dec 2019", "26 Jul 2019",
              "20 Jan 2020", "27 Oct 2019", "31 Dec 2018"});

    run_test("Already sorted",
             {"01 Jan 2018", "02 Jan 2018", "03 Jan 2018"});

    run_test("Reverse sorted",
             {"31 Dec 2020", "01 Jun 2020", "01 Jan 2020"});

    run_test("Duplicates",
             {"24 Jun 2020", "24 Jun 2020", "23 Jun 2020"});

    run_test("Invalid date",
             {"24 Jun 2020", "not-a-date", "25 Dec 2019"});

    run_test("Empty list", {});
}


/*
run:


Test case: Normal case
Input:
  24 Jun 2020
  25 Dec 2019
  26 Jul 2019
  20 Jan 2020
  27 Oct 2019
  31 Dec 2018
ERROR!
Sorted:
  31 Dec 2018
  26 Jul 2019
  27 Oct 2019
  25 Dec 2019
  20 Jan 2020
  24 Jun 2020

Test case: Already sorted
Input:
  01 Jan 2018
  02 Jan 2018
  03 Jan 2018
Sorted:
  01 Jan 2018
  02 Jan 2018
  03 Jan 2018

Test case: Reverse sorted
Input:
  31 Dec 2020
  01 Jun 2020
  01 Jan 2020
Sorted:
  01 Jan 2020
  01 Jun 2020
  31 Dec 2020

Test case: Duplicates
Input:
  24 Jun 2020
  24 Jun 2020
  23 Jun 2020
Sorted:
  23 Jun 2020
  24 Jun 2020
  24 Jun 2020

Test case: Invalid date
Input:
  24 Jun 2020
  not-a-date
  25 Dec 2019
Error: Invalid date: not-a-date

Test case: Empty list
Input:
Sorted:

*/

 



answered Sep 23 by avibootz
edited Sep 23 by avibootz
0 votes
#include <algorithm>
#include <chrono>
#include <exception>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>


/*
    Program goal:
    -------------
    Sort a list of date strings in a predictable, safe, and efficient manner.
    We convert each string into a std::chrono::sys_days (a civil-calendar day),
    which provides strong type guarantees and avoids manual date arithmetic.

    Supported format:
    -----------------
    "YYYY-MM-DD" (ISO 8601). This format is unambiguous and easy to parse.

    Architecture notes:
    -------------------
    - Parsing is isolated in a dedicated function for clarity and testability.
    - Sorting uses std::sort with a custom comparator that relies on parsed dates.
    - Error handling: invalid dates are detected and reported.
    - Complexity: O(n log n) for sorting; O(n) for parsing.
    - Memory: minimal; only stores parsed dates alongside original strings.
    - Security: no unsafe pointer arithmetic; uses standard library facilities.
    - Tests: main() includes multiple test cases, including edge cases.
*/

// Convert "YYYY-MM-DD" into std::chrono::sys_days.
// Throws std::runtime_error on malformed input.
std::chrono::sys_days parse_date(const std::string& s) {
    std::istringstream iss(s);
    int y, m, d;
    char dash1, dash2;

    if (!(iss >> y >> dash1 >> m >> dash2 >> d) || dash1 != '-' || dash2 != '-') {
        throw std::runtime_error("Invalid date format: " + s);
    }

    // Explicit casts prevent narrowing warnings.
    const auto year  = std::chrono::year{y};
    const auto month = std::chrono::month{static_cast<unsigned>(m)};
    const auto day   = std::chrono::day{static_cast<unsigned>(d)};

    std::chrono::year_month_day ymd{year, month, day};

    if (!ymd.ok()) {
        throw std::runtime_error("Invalid calendar date: " + s);
    }

    return std::chrono::sys_days{ymd};
}


// Sort a vector of date strings by converting each to sys_days.
// Returns a new sorted vector; does not mutate the input.
std::vector<std::string> sort_dates(const std::vector<std::string>& dates) {
    // Pair each string with its parsed date for efficient comparison.
    struct Entry {
        std::string original;
        std::chrono::sys_days parsed;
    };

    std::vector<Entry> entries;
    entries.reserve(dates.size());

    // Parse all dates; report errors immediately.
    for (const auto& s : dates) {
        try {
            entries.push_back({s, parse_date(s)});
        } catch (const std::exception& e) {
            // In production code, you might log or propagate.
            // Here we rethrow to keep behavior explicit.
            throw;
        }
    }

    // Sort by parsed date.
    std::sort(entries.begin(), entries.end(),
              [](const Entry& a, const Entry& b) {
                  return a.parsed < b.parsed;
              });

    // Extract sorted strings.
    std::vector<std::string> result;
    result.reserve(entries.size());
    for (const auto& e : entries) {
        result.push_back(e.original);
    }

    return result;
}

// Helper to print a vector of strings.
void print_list(const std::vector<std::string>& v) {
    for (const auto& s : v) {
        std::cout << "  " << s << "\n";
    }
}

int main() {
    try {
        std::cout << "Test Case 1: Basic chronological order\n";
        std::vector<std::string> dates1{
            "2024-01-05",
            "2023-12-31",
            "2024-01-01",
            "2022-07-15"
        };
        auto sorted1 = sort_dates(dates1);
        print_list(sorted1);

        std::cout << "\nTest Case 2: Already sorted input\n";
        std::vector<std::string> dates2{
            "2020-01-01",
            "2020-01-02",
            "2020-01-03"
        };
        auto sorted2 = sort_dates(dates2);
        print_list(sorted2);

        std::cout << "\nTest Case 3: Edge cases (leap year)\n";
        std::vector<std::string> dates3{
            "2020-02-29",
            "2019-02-28",
            "2021-03-01"
        };
        auto sorted3 = sort_dates(dates3);
        print_list(sorted3);

        std::cout << "\nTest Case 4: Invalid date detection\n";
        std::vector<std::string> dates4{
            "2024-13-01",   // invalid month
            "2024-02-30",   // invalid day
            "not-a-date"    // malformed
        };
        // This will throw; we catch below.
        auto sorted4 = sort_dates(dates4);
        print_list(sorted4);

    } catch (const std::exception& e) {
        // Error handling: print message and continue.
        std::cerr << "\nError: " << e.what() << "\n";
    }
}



/*
run:

Test Case 1: Basic chronological order
  2022-07-15
  2023-12-31
  2024-01-01
  2024-01-05

Test Case 2: Already sorted input
  2020-01-01
  2020-01-02
  2020-01-03

Test Case 3: Edge cases (leap year)
  2019-02-28
  2020-02-29
  2021-03-01

Test Case 4: Invalid date detection

Error: Invalid calendar date: 2024-13-01

*/

 



answered Sep 23 by avibootz
...