C++ dữ liệu phân loại đôi với nhiều yếu tố

Question

Tôi có nhiều mục dữ liệu có chứa các thông tin sau: id_number name1 ngày name2

Có thể đặt điều này vào một cấu trúc như thế này:

struct entry { 
    int id_number; 
    string name1; 
    int date; 
    string name2; 
} 

Trong dữ liệu của tôi, tôi có nhiều mục như vậy và tôi muốn sắp xếp. Trước tiên, tôi muốn sắp xếp theo thứ tự bảng chữ cái dựa trên tên1, sau đó sắp xếp theo ngày. Tuy nhiên, sắp xếp theo ngày là tập con của sắp xếp theo thứ tự bảng chữ cái, ví dụ: nếu tôi có hai mục nhập có cùng tên1, thì tôi muốn sắp xếp các mục nhập đó theo ngày. Hơn nữa, khi tôi sắp xếp, tôi muốn các yếu tố của mục nhập ở lại với nhau, vì vậy tất cả bốn giá trị đi cùng nhau.

Câu hỏi của tôi như sau:

1) loại cấu trúc dữ liệu tôi nên sử dụng để lưu dữ liệu này để tôi có thể giữ cho các bộ bốn yếu tố với nhau khi tôi loại vì bất kỳ mục một trong số họ?

2) Cách nhanh nhất để thực hiện việc sắp xếp này (về mặt thời gian để viết mã) là gì. Lý tưởng nhất, tôi muốn sử dụng một cái gì đó giống như sắp xếp trong thuật toán.h vì nó đã được xây dựng trong.

3) STL có một số cấu trúc dữ liệu tích hợp có thể xử lý phân loại kép mà tôi mô tả một cách hiệu quả?

Answer 1

Các struct bạn có là tốt, ngoại trừ việc bạn có thể muốn thêm một tình trạng quá tải của operator< để làm so sánh. Tại đây tôi đang thực hiện so sánh "so sánh theo tên, sau đó ngày":

// Add this as a member function to `entry`. 
bool operator<(entry const &other) const { 
    if (name1 < other.name1) 
     return true; 
    if (name1 > other.name1) 
     return false; 

    // otherwise name1 == other.name1 
    // so we now fall through to use the next comparator. 

    if (date < other.date) 
     return true; 
    return false; 
} 

[Chỉnh sửa: Yêu cầu được gọi là "đặt hàng yếu nghiêm ngặt". Nếu bạn muốn nhận được chi tiết về những gì các phương tiện, và những lựa chọn thay thế là có thể, Dave Abrahams đã viết khá chi tiết đăng bài trên C++ Next về nó.

Trong trường hợp trên, chúng tôi bắt đầu bằng cách so sánh trường name1 của hai trường. Nếu a<b, thì chúng tôi ngay lập tức trả lại giá trị true. Nếu không, chúng tôi kiểm tra a>b và nếu chúng tôi trả về false. Tại thời điểm đó, chúng tôi đã loại bỏ a<b và a>b, vì vậy chúng tôi đã xác định rằng a==b, trong trường hợp đó chúng tôi kiểm tra ngày - nếu a<b, chúng tôi trả về true. Nếu không, chúng tôi trả về false - hoặc các ngày bằng nhau hoặc b>a, một trong hai cách có nghĩa là thử nghiệm cho a<b là sai. Nếu sắp xếp cần sắp xếp (không có ý định chơi chữ) mà trong đó là trường hợp, nó có thể gọi hàm một lần nữa với các đối số được hoán đổi. Các tên vẫn sẽ bằng nhau, vì vậy nó sẽ vẫn đi xuống đến ngày - nếu chúng ta nhận được sai, các ngày bằng nhau. Nếu chúng ta có được sự thật vào những ngày được đổi chỗ, thì những gì bắt đầu khi ngày thứ hai thực sự lớn hơn. ]

operator< bạn xác định trong cấu trúc xác định thứ tự sẽ được sử dụng theo mặc định.Khi/nếu bạn muốn, bạn có thể chỉ định trật tự khác cho việc phân loại để sử dụng:

struct byid { 
    bool operator<(entry const &a, entry const &b) { 
     return a.id_number < b.id_number; 
    } 
}; 

std::vector<entry> entries; 

// sort by name, then date 
std::sort(entries.begin(), entries.end()); 

// sort by ID 
std::sort(entries.begin(), entries.end(), byid()); 

Answer 2

Cấu trúc dữ liệu đó ngay tại đó sẽ hoạt động tốt. Những gì bạn cần làm là ghi đè lên toán tử nhỏ hơn, sau đó bạn chỉ có thể chèn tất cả chúng vào một bản đồ và chúng sẽ được sắp xếp. Here is more info on the comparison operators for a map

Cập nhật: khi phản ánh xa hơn, tôi sẽ sử dụng tập hợp chứ không phải bản đồ vì không cần giá trị. Nhưng ở đây là bằng chứng nó vẫn hoạt động

Proof làm việc này:

#include<string> 
#include<map> 
#include<stdio.h> 
#include <sstream> 


using namespace std; 

struct entry { 
    int m_id_number; 
    string m_name1; 
    int m_date; 
    string m_name2; 

    entry( int id_number, string name1, int date, string name2) : 
     m_id_number(id_number), 
     m_name1(name1), 
     m_date(date), 
     m_name2(name2) 
    { 

    } 

    // Add this as a member function to `entry`. 
    bool operator<(entry const &other) const { 
     if (m_name1 < other.m_name1) 
      return true; 
     if (m_name2 < other.m_name2) 
      return true; 
     if (m_date < other.m_date) 
      return true; 
     return false; 
    } 

    string toString() const 
    { 
     string returnValue; 

     stringstream out; 
     string dateAsString; 

     out << m_date; 
     dateAsString = out.str(); 

     returnValue = m_name1 + " " + m_name2 + " " + dateAsString; 

     return returnValue; 
    } 
}; 


int main(int argc, char *argv[]) 
{ 
    string names1[] = {"Dave", "John", "Mark", "Chris", "Todd"}; 
    string names2[] = {"A", "B", "C", "D", "E", "F", "G"}; 

    std::map<entry, int> mymap; 
    for(int x = 0; x < 100; ++x) 
    { 
     mymap.insert(pair<entry, int>(entry(0, names1[x%5], x, names2[x%7]), 0)); 
    } 

    std::map<entry, int>::iterator it = mymap.begin(); 
    for(; it != mymap.end() ;++it) 
    { 
     printf("%s\n ", it->first.toString().c_str()); 
    } 
    return 0; 
} 

Answer 3

Trên thực tế bạn có thể sử dụng đối tượng chức năng để thực hiện tiêu chí phân loại của bạn

giả sử rằng bạn muốn để lưu trữ các mục trong tập

//EntrySortCriteria.h 
class EntrySortCriteria 
{ 
    bool operator(const entry &e1, const entry &e2) const 
    { 
     return e1.name1 < e2.name1 || 
       (!(e1.name1 < e2.name1) && e1.date < e2.date)) 
    } 
} 

//main.cc 
#include <iostream> 
#include "EntrySortCriteria.h" 

using namespace std; 
int main(int argc, char **argv) 
{ 

    set<entry, EntrySortCriteria> entrySet; 
    //then you can put entries into this set, 
    //they will be sorted automatically according to your criteria 
    //syntax of set: 
    //entrySet.insert(newEntry); 
    //where newEntry is a object of your entry type  
}