कौन सी डेटा संरचना कुशल हटाने और यादृच्छिक पहुंच का समर्थन करता है?

Question

मैं एक डेटा संरचना की तलाश में हूं जिसमें मैं कुशलता से वस्तुओं को हटा सकता हूं और यादृच्छिक पहुंच का भी समर्थन करता हूं।

मुझे कुशल सम्मिलन की भी आवश्यकता है, लेकिन तत्वों का क्रम महत्वपूर्ण नहीं है, मैंने सोचा कि मैं स्टोर करने के लिए अधिकतम तत्वों के लिए स्मृति को प्रीलोकेट कर सकता हूं और फिर अंत में हमेशा नया तत्व डाल सकता हूं ताकि कोई पुनर्वितरण या अन्य तत्वों की चाल आवश्यक है।

मेरे सर्वोत्तम ज्ञान के लिए, एक लिंक्ड सूची हटाने के लिए सही होगी लेकिन इसके तत्वों तक पहुंचने से ओ (एन) समय लग सकता है। दूसरी तरफ, एक सरल सरणी (उदाहरण के लिए vector सी ++ में) में यादृच्छिक पहुंच संपत्ति है लेकिन इस तरह की संरचना से तत्व को हटाने से ओ (एन) की जटिलता है।

असल में, यादृच्छिक पहुंच आवश्यकता वास्तव में मुझे जो चाहिए उससे ज्यादा मजबूत है। मुझे केवल यादृच्छिक रूप से समान रूप से संरचना का एक तत्व चुनने में सक्षम होना चाहिए। स्पष्ट रूप से कुशल पहुंच संपत्ति का मतलब ऑपरेशन की दक्षता का तात्पर्य है, लेकिन मुझे यकीन नहीं है कि क्या वे दो बराबर हैं।

अग्रिम धन्यवाद!

Answer 1

मेरा मानना ​​है कि आपके प्रश्न में जिस समाधान का संकेत है, वह वास्तव में आपको एक छोटी सी जानकारी को छोड़कर चाहिए।

आप का सुझाव दिया:

मैंने सोचा कि मैं तत्वों की अधिकतम संख्या के लिए स्मृति preallocate कर सकते हैं यह स्टोर करने के लिए हो सकता है और उसके बाद हमेशा अंत में नए तत्व डाल ताकि कोई पुनः आबंटन या अन्य तत्वों के इस कदम के लिए आवश्यक है ।

आप प्रविष्टियों में से एक उचित अधिकतम संख्या की स्थापना कर सकते हैं वास्तव में, तो मैं तुम्हें एक सरणी पूर्व आवंटित की है कि संख्या के साथ सुझाव है (उदाहरण के लिए std::array का उपयोग कर यदि अधिकतम संकलन समय पर जाना जाता है, या एक std::vector अन्यथा) प्रविष्टियों, एक तत्व गिनती की स्थापना (वर्तमान में संग्रहीत तत्वों की संख्या की गणना करने के लिए), और आगे बढ़ना इस प्रकार है:

1. शुरू में आप के लिए 0
2. गिनती सेट आप एक तत्व सम्मिलित करते हैं, तो आप इसे अंत में जोड़ने और गणना
3. जब आप एक तत्व हटाने के बाद आप पिछले तत्व साथ यह स्वैप और गिनती
4. रैंडम एक्सेस के लिए घटती (भावना आप इसे वर्णित में, यानी सचमुच एक तत्व बेतरतीब ढंग से उठा) आप 0 और गिनती के बीच एक यादृच्छिक संख्या का निर्धारण , और उस तत्व

केवल विस्तार मैं बदल तत्व विलोपन, जो मैं तुम्हें पिछले तत्व साथ स्विच पदों के रूप में लागू करने का सुझाव है लेने।

संभव कार्यान्वयन:

#include <vector> 
#include <utility> 
#include <iostream> 

template <typename Elem> 
class randomaccesstable 
{ 
public: 
    randomaccesstable(std::size_t initial_size) 
    : data_(initial_size) , count_(0) 
    { } 

    randomaccesstable &push_back(const Elem &elem) 
    { 
    if (count_ < data_.size()) 
     data_[count_++] = elem; 
    else { 
     data_.push_back(elem); 
     ++count_; 
    } 
    return *this; 
    } 

    randomaccesstable &remove(const std::size_t index) 
    { 
    if (index < count_) 
    { 
     std::swap(data_[index],data_[count_-1]); 
     --count_; 
    } 
    return *this; 
    } 

    const Elem &operator[](const std::size_t index) const 
    { return data_[index]; } 

    Elem &operator[](const std::size_t index) 
    { return data_[index]; } 

    std::size_t size() const 
    { return count_; } 

private: 
    std::vector<Elem> data_; 
    std::size_t  count_; 
}; 

int main() 
{ 
    randomaccesstable<int> table(10); 
    table.push_back(3); 
    table.push_back(12); 
    table.push_back(2); 

    for (std::size_t i = 0 ; i < table.size() ; ++i) 
    std::cout << table[i] << ' '; 
    std::cout << '\n'; 

    table.remove(1); // this removes the entry for 12, swapping it for 2 

    for (std::size_t i = 0 ; i < table.size() ; ++i) 
    std::cout << table[i] << ' '; 
    std::cout << '\n'; 

    return 0; 
} 

Answer 2

मैं hash table का उपयोग करने का सुझाव दूंगा। वहां आप लगातार जटिलता के साथ तत्व हटा सकते हैं और देख सकते हैं। सी ++ में आप std::unordered_map (सी ++ 11) या boost::unordered_map (प्री-सी ++ 11) और जावा - HashMap का उपयोग कर सकते हैं।