实现两种数据结构以迭代不同值的最有效方法是什么

Question

我正在尝试实现一个数据结构来解析数据并进行数据分析

我的数据格式如下

DATE-TIME    DATA  DATA  DATA
31/3/1999 20:40    6  130  19.95
31/3/1999 23:50    3  440  17.95
31/3/1999 23:20    4  300  18.81
31/3/1999 23:30    5  313  18.48
20/7/1999 23:40    20  1000  18.19
31/7/1999 23:40    5  110  18.23
25/5/2023 23:40    0  130  26
22/2/2023 23:20    2  110  33.3
15/2/2023 23:30    3  110  22.2
20/2/2023 23:40    12  110  30.1
31/3/2023 23:40    34  100  0

要求必须按年份或每年的月份访问数据。

必须使用 MAPS 和 BST，向量不是必需的。

我已经用 MAP 和 BST 实现了一个算法，所以目前是这样的

MAP[1999] = BST<THE DATA RELATED TO 1999>
MAP[2023] = BST<THE DATA RELATED TO 2023>

我面临的问题是，如果我想获得 JULY 的示例，我必须遍历整个树才能找到 data.Month == june 的位置

我尝试过类似的事情

MAP[2023] = BST< VECTOR <JAN> <FEB> <MAR> <APR> <MAY> <JUN> <JUL> >

我的理由是我将在 BST 中存储每个月记录的向量。但我意识到 BST 不知道它是什么记录以及如何正确存储向量。另一个问题是我无法从 BST 正确访问 MONTH 向量。

Answer 1

在这种情况下根本没有必要使用映射或多个数据结构。数据的结构非常可预测，因此制作

vector<monthly_data>

就足够了。

因为您知道向量中的第一个条目是哪一年和月份，所以计算您感兴趣的范围是微不足道的。

要获取与特定年份相关的数据，您只需计算该年一月的偏移量并检索指向该数据的指针。以下11条为当年剩余数据。

要获取每年与特定月份相关的数据，您只需计算该月第一个条目的偏移量并检索指向该数据的指针。该条目之后的每 12 个条目将是接下来几年中与该月相关的数据。

struct monthly_data { /* stuff */ };

struct all_data
{
    std::vector<monthly_data> data;
    int start_year;
    int start_month;
};

void do_something_for_every_month_in_a_year(all_data& d, int year)
{
    int year_offset = year - d.start_year;
    int month_offset = -d.start_month;
    int jan_of_year_offset = 12*year_offset + month_offset;

    for (int i = 0; i < 12; ++i) {
        auto& entry = d.data[i + jan_of_year_offset];
        // do something with entry
    }
}

void do_something_with_month_for_every_year(all_data& d, int month)
{
    int month_offset = -d.start_month + month;
    while (true) {
        // break when no more entries
        auto& entry = d.data[month_offset];
        // do something with entry

        month_offset += 12;
    }
}

请注意，上面的代码只是一个概念示例，尚未经过测试。我还省略了对边缘情况的检查。