2013-03-23 13 views
7

सभी में एक क्रमबद्ध कंटेनर है,क्या एसटीएल

क्या एसटीएल में एक सॉर्टेड कंटेनर है? मेरा मतलब है कि निम्नलिखित है:

मेरे पास एक std :: वेक्टर है जहां फू एक कस्टम बनाया गया वर्ग है। मेरे पास कुछ प्रकार का तुलनित्र भी है जो वर्ग फू के खेतों की तुलना करेगा।

अब, मेरी कोड में कहीं मैं कर रहा हूँ:

std::sort(myvec.begin(), myvec.end(), comparator); 

जो नियम मैं तुलनित्र में परिभाषित के अनुसार वेक्टर सॉर्ट होगा।

अब मैं उस वेक्टर में कक्षा फू का एक तत्व डालना चाहता हूं। मैं मैं सिर्फ लिखने के लिए पसंद करते हैं सकता है:

mysortedvector.push_back(Foo()); 

और क्या होगा कि वेक्टर अपनी जगह पर तुलनित्र के अनुसार इस नए तत्व डाल देंगे है।

इसके बजाय, अभी मैं लिखने के लिए है:

myvec.push_back(Foo()); 
std::sort(myvec.begin(), myvec.end(), comparator); 

जो, बस समय की बर्बादी है, क्योंकि वेक्टर पहले से ही क्रमबद्ध हो जाता है और सभी मैं की जरूरत है उचित रूप से नए तत्व जगह है।

अब, मेरे कार्यक्रम की प्रकृति के कारण, मैं std :: map <> का उपयोग नहीं कर सकता क्योंकि मेरे पास कोई कुंजी/मूल्य जोड़े नहीं है, बस एक साधारण वेक्टर है।

यदि मैं stl :: सूची का उपयोग करता हूं तो मुझे फिर से प्रत्येक सम्मिलन के बाद सॉर्ट करने की आवश्यकता होती है।

आपके द्वारा प्रदान किए जा सकने वाले किसी भी सुझाव के लिए धन्यवाद।

+2

के बारे में क्या 'std :: set' बना सकते हैं? – us2012

+0

यदि आपको पता था कि यह कहां जाएगा, तो आप डालने() – james82345

+0

@ us2012 का उपयोग कर सकते हैं, मैंने std :: set को देखा।समस्या यह है कि उन ऑब्जेक्ट को ग्रिड में प्रस्तुत किया जाएगा, जहां उपयोगकर्ता उन्हें सभी वर्ग के सदस्य के आधार पर सॉर्ट कर सकता है और उन्हें फिट बैठने के तरीके में संशोधित कर सकता है। चूंकि std :: सेट सदस्य परिभाषा के आधार पर हैं, यह कंटेनर मेरे लिए नहीं है। – Igor

उत्तर

21

हाँ, std::set, std::multiset, std::map, और std::multimap सभी डिफ़ॉल्ट तुलना आपरेशन के रूप में std::less का उपयोग कर हल कर रहे हैं। अंतर्निहित अंतर्निहित डेटा-संरचना आमतौर पर एक संतुलित बाइनरी खोज पेड़ है जैसे कि लाल-काले पेड़। इसलिए यदि आप इन डेटा-स्ट्रक्चर्स में कोई तत्व जोड़ते हैं और फिर निहित तत्वों पर पुनरावृत्त करते हैं, तो आउटपुट क्रमबद्ध क्रम में होगा। डेटा-स्ट्रक्चर में एन तत्व जोड़ने की जटिलता ओ (एन लॉग एन) होगी, या किसी भी सामान्य ओ (लॉग एन) जटिलता प्रकार का उपयोग करके एन तत्वों के वेक्टर को सॉर्ट करने जैसा ही होगा।

आपके विशिष्ट परिदृश्य में, क्योंकि आपके पास कुंजी/मूल्य जोड़े नहीं हैं, std::set या std::multiset शायद आपकी सबसे अच्छी शर्त है।

+0

बहुत अच्छी व्याख्या! – Arun

0

मैं कार्यक्षमता नहीं लगता कि एसटीएल में मौजूद है, एक std :: वेक्टर केवल प्रकार विभाजन, nth_element, stable_partition, partial_sort, stable_sort साथ और तरह

आप फिर भी एसटीडी के लिए एक आवरण :: वेक्टर

#include <vector> 

template <class T> 
class VectorSortWrapper 
{ 
public: 
    std::vector<T> m_VectorSorted; 

    void InsertSortedAscending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() <= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

    void InsertSortedDecending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() >= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

}; 
+0

ऐसे बूस्ट कंटेनर हैं जो http://www.boost.org/doc/libs/1_51_0/doc/html/container/non_standard_containers.html – james82345

+1

सहायता कर सकते हैं जब आप कहते हैं कि "कार्यक्षमता एसटीएल में मौजूद नहीं है", I मुझे लगता है कि आप एक क्रमबद्ध डालने एल्गोरिदम के बारे में बात कर रहे हैं? ... जैसा कि मैंने अपने जवाब में बताया है, सॉर्ट किए गए कंटेनर हैं ... – Jason

+0

@ जेसन हां, std :: vector के लिए कोई सम्मिलित एल्गोरिदम नहीं है। – james82345