सी ++ std :: मानचित्र या std :: सेट - कुशलतापूर्वक डुप्लिकेट डालें

Question

मेरे पास डुप्लिकेट से भरा डेटा का एक गुच्छा है और मैं डुप्लिकेट को खत्म करना चाहता हूं। आप जानते हैं, उदा। [1, 1, 3, 5, 5, 5, 7] [1, 3, 5, 7] बन जाता है।

ऐसा लगता है कि मैं इसे संभालने के लिए या तो std :: map या std :: सेट का उपयोग कर सकता हूं। हालांकि मुझे यकीन नहीं है कि यह तेजी से (ए) कंटेनर में सभी मानों को सम्मिलित करता है, या (बी) जांचें कि क्या वे पहले से ही कंटेनर में मौजूद हैं और केवल अगर वे नहीं करते हैं तो डालें - क्या आवेषण बहुत कुशल हैं? यहां तक ​​कि यदि कोई बेहतर तरीका है ... क्या आप ऐसा करने का एक तेज़ तरीका सुझा सकते हैं?

एक और सवाल - यदि मैं जो डेटा संग्रहीत कर रहा हूं वह पूर्णांक के रूप में छोटा नहीं है, और इसके बजाय एक कस्टम क्लास है, तो std :: नक्शा तेजी से डेटा (हैश?) को तेजी से स्टोर करने के लिए कैसे प्रबंधित करता है ऑपरेटर के माध्यम से उपयोग []?

Answer 1

std::map हैशिंग का उपयोग नहीं करता। std::unordered_map करता है, लेकिन यह सी ++ 11 है। std::map और std::set दोनों आपके द्वारा प्रदान किए गए तुलनित्र का उपयोग करते हैं। क्लास टेम्पलेट्स के पास इस तुलनित्र के लिए डिफ़ॉल्ट है, जो operator< तुलना में उबालता है, लेकिन आप अपना खुद का प्रदान कर सकते हैं।

यदि आपको संग्रहीत करने के लिए एक कुंजी और मूल्य दोनों की आवश्यकता नहीं है (ऐसा लगता है कि आपको नहीं लगता है) तो आपको केवल std::set का उपयोग करना चाहिए, क्योंकि यह अधिक उचित है।

मानक यह नहीं कहता कि डेटा संरचना map एस और set एस हुड के तहत उपयोग करते हैं, केवल प्रमाणित कार्यों में कुछ समय जटिलताएं होती हैं। हकीकत में, अधिकांश कार्यान्वयन मुझे एक पेड़ का उपयोग करने के बारे में पता है।

यह कोई फर्क नहीं समय-जटिलता के लिहाज से यदि आप operator[] या insert का उपयोग करता है, लेकिन इससे पहले कि मैं एक search एक insert द्वारा पीछा किया था यदि आइटम नहीं मिला है मैं insert या operator[] का प्रयोग करेंगे। बाद में सेट में एक आइटम डालने के लिए दो अलग-अलग खोजों का अर्थ होगा।

Answer 2

std::map और std::set के लिए सामान्य कार्यान्वयन रणनीति को मानते हुए, यानी संतुलित द्विआधारी खोज पेड़, दोनों प्रविष्टि और लुकअप को उस जगह को खोजने के लिए एक पेड़ ट्रैवर्सल करना है जहां कुंजी होना चाहिए। इसलिए असफल होने के बाद लुकअप लुकअप लगभग डालने के रूप में लगभग दोगुनी धीमी होगी।

std :: map ऑपरेटर [] के माध्यम से तेज़ी से पहुंच के लिए डेटा को ठीक से स्टोर (हैश?) कैसे प्रबंधित करता है?

एक तुलना समारोह आपके द्वारा निर्दिष्ट (या std::less है, जो अगर आप अपने कस्टम प्रकार पर operator< ओवरलोड काम करता है) के माध्यम से। किसी भी मामले में, std::map और std::set हैश टेबल नहीं हैं।

Answer 3

किसी भी संबंधित कंटेनर पर insert()find() करता है यह देखने के लिए कि ऑब्जेक्ट मौजूद है या फिर ऑब्जेक्ट डालें। बस std::set<T> में तत्वों को सम्मिलित करना उचित रूप से डुप्लिकेट से छुटकारा पाएं।

अपने सेट के आकार और अनन्य मान डुप्लिकेट के अनुपात के आधार पर यह वस्तुओं, std::sort() तो std::vector<T> में डाल दिया, और फिर डुप्लिकेट से छुटकारा पाने के std::vector<T>::erase() के साथ एक साथ std::unique() का उपयोग तेजी से हो सकता है।

Answer 4

आप इसे कितनी बार करना चाहिए?

तो डालने सामान्य है:

//*/ 
std::set<int> store; 
/*/ 
// for hash: 
std::unordered_set<int> store; 
//*/ 
int number; 

if (store.insert(number).second) 
{ 
    // was not in store 
} 

आप एक बार भरें:

std::vector<int> store; 
int number; 

store.push_back(number); 
std::sort(store.begin(),store.end()); 
store.erase(std::unique(store.begin(),store.end()),store.end()); 

// elements are unique 

Answer 5

std::set और std::map दोनों के रूप में तक मुझे पता है लाल, काले पेड़ के रूप में लागू किया जाता है। और शायद केवल सम्मिलन का उपयोग करना तेज़ होगा (तब दोनों क्योंकि आप लुकअप समय को दोगुना कर देंगे)।

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