सी ++: कई तत्वों के कुशल प्राप्त/पॉट के साथ कतार?

Question

तो, मुझे लगता है कि सी ++ में इसके लिए एक अच्छा, अंतर्निहित समाधान होना चाहिए, लेकिन मुझे यकीन नहीं है कि यह क्या है।

मुझे एक कतार की आवश्यकता है (आदर्श रूप से थ्रेड-सुरक्षित, लेकिन यदि आवश्यकता हो तो मैं सिंक्रनाइज़ेशन में इसे लपेट सकता हूं) जो कि बाइट्स के समूहों को कुशलता से संभालता है - विभिन्न आकारों के पढ़ने/लिखने की अनुमति देता है।

तो, इंटरफ़ेस उदा।

//removes the first bytesToRead elements from the front of the queue and places them in array; returns the actual number of bytes dequeued 
int dequeue(unsigned char *array, int bytesToRead) 
//Adds bytesToWrite elements from array to the end of the queue; does nothing and returns 0 if this would exceed the queue's max size 
int enqueue(unsigned char *array, int bytesToWrite) 

मैं एक अपने आप को बहुत अधिक कठिनाई के बिना लिख ​​सकते हैं, लेकिन यह इस तरह लगता है कुछ है कि आसानी से शेल्फ से किया है होना चाहिए।

एसटीएल में सबसे अच्छी बात यह है कि यह एक स्ट्रिंगबफ हो सकता है - मुझे हाथ से sgetc/pubseekoff पर कॉल जोड़ना होगा, लेकिन ऐसा लगता है जैसे यह काम करेगा।

मैं वर्तमान कतार कार्यान्वयन के लिए ड्रॉप-इन प्रतिस्थापन के रूप में ऐसा करने के लिए देख रहा हूं जो एक प्रदर्शन समस्या है; इस कार्यान्वयन में पढ़ना कतार में डेटा की मात्रा पर ओ (एन) है। (यह एक बहुत भोली कार्यान्वयन है - कतार में शेष डेटा की एक सरणी कॉपी में हर विपंक्ति का परिणाम है।)

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

तो सभी उपलब्ध डेटा पुनः प्राप्त करना चाहिए , मेरे प्रश्न: 1) स्ट्रिंगबफ पर्याप्त है? क्या बफर में डेटा की मात्रा के सापेक्ष पढ़ने/लिखने के संचालन ओ (1) हैं, मानते हैं कि कोई आकार बदलने की आवश्यकता नहीं है? (जाहिर है, वे संभावित रूप से अनुरोधित वस्तुओं की संख्या पर ओ (एन) होंगे।)

2) क्या कोई अन्य वर्ग है जिसे मैं नहीं देख रहा हूं जो पर्याप्त होगा?

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

Answer 1

क्या आप std::stringstream का उपयोग कर सकते हैं जहां आप write के साथ कतार में धक्का देते हैं और read के साथ कतार को पॉप करते हैं? ,

class queue { 
     std::deque<unsigned char> data; 
public: 
    int enqueue(unsigned char *array, int bytesToWrite) { 
     data.insert(data.end(), array, array+bytesToWrite); 
    } 

    int dequeue(unsigned char *array, int bytesToRead) { 
     std::copy(data.begin(), data.begin()+bytesToRead, array); 
     // or, for C++11: std::copy_n(data.begin(), bytesToRead, array); 

     data.erase(data.begin(), data.begin()+bytesToRead); 
    } 
}; 

खेद है कि मैं काफी महत्वाकांक्षी पर्याप्त समय नहीं महसूस कर रहा हूँ पर ताला लगा है और बदले मूल्यों आप के लिए कहा जोड़ने के लिए, लेकिन न तो बहुत किया जाना चाहिए:

Answer 2

हममम ... आप की कोशिश की स्पष्ट है मुश्किल। हालांकि, आपके रिटर्न वैल्यू के साथ झुकाव करने के बजाय, मैं इटरेटर्स का उपयोग करने के लिए इंटरफ़ेस बदलूंगा (या, यदि आप वास्तव में जोर देते हैं, वेक्टर का संदर्भ)।

यह डाले गए/हटाए गए तत्वों की संख्या पर रैखिक होने की गारंटी है।

Answer 3

जैसा कि सुझाव दिया गया है, std::stringstream शायद सबसे आसान और सबसे अच्छा समाधान है।

एक और विकल्प std::deque है, यह आपको वह दक्षता देगा जो आपको चाहिए (कतार के किसी भी छोर से सभी पढ़ने/लिखने के लिए लगातार आवंटित किया जाता है, और यदि क्षमता समाप्त हो जाती है तो आम तौर पर पुनर्वितरण के ओ (एन) से बहुत कम होती है)।एकमात्र कमी यह है कि std::deque पॉइंटर अंकगणित का समर्थन नहीं करता है (क्योंकि सभी तत्व जरूरी नहीं हैं (भाग में)), इसलिए आप ब्लॉक पढ़ने/लिखने के संचालन को करने में सक्षम नहीं होंगे, आपको निम्नानुसार पुन: प्रयास करना होगा:

std::deque<unsigned char> buf; 

int dequeue(unsigned char *array, int bytesToRead) { 
    int result = std::min(bytesToRead, buf.size()); 
    std::copy(buf.begin(), buf.begin() + result, array); 
    buf.erase(buf.begin(), buf.begin() + result); 
    return result; 
}; 

int enqueue(unsigned char *array, int bytesToWrite) { 
    buf.insert(buf.end(), array, array + bytesToWrite); 
    return bytesToWrite; 
}; 

आपको बाद में कार्यान्वयन जांच करनी चाहिए यदि अधिकतम क्षमता तक पहुंच जाती है और परिणामस्वरूप परिणामी मूल्य समायोजित किया जाता है।

Answer 4

यदि आप वास्तव में तेज़ कुशल कार्यान्वयन चाहते हैं, तो मैं एक साधारण परिपत्र बफर कार्यान्वयन के साथ जाऊंगा जिसका अर्थ है कि आप एक या दो प्रतियों में अपना पढ़ सकते हैं (इस पर निर्भर करता है कि आप अपने बफर के अंत/शुरुआत के माध्यम से लपेट रहे हैं या नहीं)। यह आपको memcpy का उपयोग करने की अनुमति देता है जो मेरे अनुभव में लगभग हमेशा आपकी प्रतिलिपि बनाने के लिए बहुत से तत्वों के माध्यम से लूपिंग करता है।

यदि प्रदर्शन जेरी के जवाब के साथ जाता है तो प्रदर्शन कम महत्वपूर्ण होता है।