C++ çiftli seçme verisi

Question

Ben şu bilgileri içerir birden çok veri girişlerini vardır: ID_NUMBER isim1 tarih isim2

Böyle bir yapı içine koymak mümkündür:

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

Verilerimde böyle girdilerim var ve sıralamak istiyorum. İlk olarak, alfabetik olarak name1'e göre sıralamak, sonra tarihe göre sıralamak istiyorum. Ancak, tarihe göre sıralama, alfabetik sıralamanın bir alt kümesidir. Aynı adla1 iki girişim varsa, o tarihlere göre bu girişleri sipariş etmek istiyorum. Ayrıca, sıraladığımda, girdinin öğelerinin birlikte kalmasını istiyorum, bu nedenle dört değerin tümü birlikte.

Sorularım şunlardır:

1) Ben bu yüzden bunlardan herhangi biri tarafından ne zaman sıralamak herhangi birlikte dört elementin dizi tutabilir bu verileri tutmak için kullanması gereken veri yapısı ne tür?

2) Bu sıralama işlemini yapmanın en hızlı yolu nedir (kodu yazmak için gereken süre cinsinden). İdeal olarak, önceden oluşturulduğu için, algoritms.h'deki gibi bir şey kullanmak istiyorum.

3) STL, verimli bir şekilde tanımladığım çifte sıralama işlemlerini gerçekleştirebilecek bir veri yapısına sahip mi?

Answer 1

Eğer karşılaştırma yapmak operator< bir aşırı eklemek isteyebilirsiniz dışında sahip yapı, gayet iyi. İşte "o zaman, adıyla tarihini karşılaştırmak" karşılaştırma yapıyorum:

// 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; 
} 

[Düzenleme: "katı zayıf sipariş" denir gerekli Neler. Ne anlama geldiğini ve hangi alternatiflerin mümkün olduğunu öğrenmek istiyorsanız, Dave Abrahams bu konuda C++ Next numaralı telefondan ayrıntılı bir yazı yazdı. Yukarıdaki durumda, ikinin name1 alanlarını karşılaştırarak başlıyoruz. a<b ise, hemen doğru olarak döneriz. Aksi takdirde, a>b için kontrol ederiz ve eğer öyleyse yanlış döndürürüz. Bu noktada, a<b ve a>b'u kaldırdık. Bu nedenle, a==b numaralı telefonu belirledik. Bu durumda, tarihleri ​​test ediyoruz - a<b ise, true olarak dönelim. Aksi halde, false değerini döndürürsek - tarihler eşittir veya b>a, ya da a<b testi yanlıştır. Eğer sıralama, sıralamada yer alması gerekiyorsa (herhangi bir cezaya neden olmazsa), argümanlar değiştirilerek tekrar işlevini çağırabilir. İsimler hala eşit olacak, bu yüzden hala tarihlere inecek - eğer yanlış olursa, tarihler eşittir. Değiştirilen tarihler konusunda doğru olursak, ikinci tarih olarak başlayan şey aslında daha büyüktür. ]

Yapı içinde tanımladığınız operator<, varsayılan olarak kullanılacak sırayı tanımlar.Ne zaman/sizin için başka bir sipariş belirtebilirsiniz istiyorsanız kullanmak tasnif:

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

Bu veri yapısı tam olarak çalışmalıdır. Yapmanız gereken şey, operatörden daha azını geçersiz kılmaktır, sonra hepsini bir haritaya ekleyebilir ve bunlar sıralanabilir. Here is more info on the comparison operators for a map

Güncelleme: daha fazla yansıma üzerine, bir değer kullanmamayı gerektirdiğinden, bir haritayı değil, bir haritayı kullanırdım. Ama burada kanıtı hala bu işleri

Belgesi çalışır geçerli:

#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

Aslında size sette girdileri saklamak istiyorum varsayalım senin sıralama kriterleri

uygulamak için işlev nesnesini kullanabilirsiniz

//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  
}