एकाधिक प्रॉक्सी कक्षाएं एसटीएल-सबूत बिटकवेक्टर बना सकती हैं?

Question

यह well known है कि std::vector<bool> मानक की कंटेनर आवश्यकताओं को पूरा नहीं करता है, मुख्य रूप से क्योंकि पैक किया गया प्रतिनिधित्व T* x = &v[i] को एक पॉइंटर को एक बूल पर लौटने से रोकता है।

मेरा प्रश्न है: क्या यह संदर्भ/हटाया जा सकता है जब संदर्भ_प्रॉक्सी operator& के पते को ओवररेड करता है ताकि pointer_proxy लौटाया जा सके?

पॉइंटर-प्रॉक्सी में अधिकांश कार्यान्वयन में संदर्भ_प्रॉक्सी के समान डेटा हो सकता है, अर्थात् पैक किए गए डेटा में एक पॉइंटर और ब्लॉक के अंदर विशेष बिट को अलग करने के लिए एक मुखौटा। Pointer_proxy का संकेत तब संदर्भ_प्रैक्सी उत्पन्न करेगा। अनिवार्य रूप से दोनों प्रॉक्सी "वसा" पॉइंटर्स हैं, जो डिस्क-आधारित प्रॉक्सी कंटेनर की तुलना में अभी भी हल्के वजन वाले हैं।

T* x = &v[0] के बजाय auto x = &v[0] कर सकता है, और बिना 0 समस्याओं के if(*x) का उपयोग कर सकता है। मैं भी लिखने के लिए for(auto b: v) { /* ... */ }

प्रश्न सक्षम होने के लिए करना चाहते हैं: होगा एसटीएल के एल्गोरिदम के साथ इस तरह के एक बहु प्रॉक्सी दृष्टिकोण काम करता है? या कुछ एल्गोरिदम वास्तव में आवश्यकता पर भरोसा करते हैं कि x को वास्तविक bool* होना चाहिए? या क्या लगातार कई उपयोगकर्ता परिभाषित रूपांतरण आवश्यक हैं जो इसे काम करने से रोकते हैं? उपरोक्त कार्यान्वयन स्केच को पूरी तरह से पूरा करने की कोशिश करने से पहले मैं इस तरह के किसी भी बाधा को जानना चाहता हूं।

---

अद्यतन (@HowardHinnant के उत्तर के आधार पर और इस ancient discussion comp.std.C++ पर)

आप एक लंबा रास्ता लगभग builtin प्रकार की नकल करने के लिए आ सकते हैं: किसी भी प्रकार के टी के लिए , प्रॉक्सी की एक जोड़ी (जैसे context_proxy और iterator_proxy) को इस अर्थ में पारस्परिक रूप से सुसंगत बनाया जा सकता है कि context_proxy :: ऑपरेटर &() और iterator_proxy :: ऑपरेटर *() एक-दूसरे के विपरीत हैं।

हालांकि, कुछ बिंदु पर एक प्रॉक्सी वापस वस्तुओं टी * या टी & की तरह व्यवहार करने के लिए नक्शे की जरूरत है। इटरेटर प्रॉक्सी के लिए, कोई ऑपरेटर अधिभारित कर सकता है ->() और टेम्पलेट टी के इंटरफेस को सभी कार्यक्षमता को दोबारा लागू किए बिना एक्सेस करें। हालांकि, संदर्भ प्रॉक्सी के लिए हैं, तो ऑपरेटर ओवरलोड) की आवश्यकता होगी। (, और कहा कि वर्तमान सी में अनुमति नहीं है ++ (हालांकि Sebastian Redl presented such a proposal on BoostCon 2013)। आप संदर्भ प्रॉक्सी के अंदर एक .Get() सदस्य की तरह एक वर्बोज़ काम के आसपास बना सकते हैं, या संदर्भ के अंदर टी के इंटरफेस के सभी लागू (यह क्या वेक्टर :: bit_reference के लिए किया जाता है), लेकिन यह या तो निर्मित वाक्य रचना खो देंगे या उपयोगकर्ता द्वारा परिभाषित रूपांतरणों को प्रस्तुत करें जिनमें टाइप रूपांतरणों के लिए बिल्टिन सेमेन्टिक्स नहीं हैं (आपके पास प्रति तर्क में एक उपयोगकर्ता द्वारा परिभाषित रूपांतरण हो सकता है)।

Answer 1

:

यहाँ तुलना (एक संस्करण बिटस्ट्रीम में किसी भी मनमाना बिंदु पर शुरू थोड़ा अतिरिक्त सेटअप तर्क की आवश्यकता होगी करने में सक्षम) के लिए समाप्त करने के लिए शुरू से ही बिट्स के माध्यम से जाने के लिए एक ही रास्ता है,

मेरा प्रश्न है: संदर्भ_प्रॉक्सी pointer_proxy वापस करने के लिए ऑपरेटर & के पता-पते को ओवरलोड करता है, तो इसका उपचार/कम किया जा सकता है?

libc++ वास्तव में ऐसा करता है।

#include <vector> 
#include <cassert> 

int main() 
{ 
    std::vector<bool> v(1); 
    std::vector<bool>::pointer pb = &v[0]; 
    assert(*pb == false); 
    *pb = true; 
    assert(v[0] == true); 
    std::vector<bool>::const_pointer cbp = pb; 
    assert(*cbp == true); 
    v[0] = false; 
    assert(*cbp == false); 
} 

यह भी तरीके कि vector<int> के लिए एक ही प्रकार की नकल में const_pointer और const_reference तक फैली। यह libC++ के लिए एक गैर-अनुरूप एक्सटेंशन है। लेकिन यह सामान्य जेनेरिक कोड बनाता है जिसे vector<bool> पर तुरंत संकलित और व्यवहार करने की संभावना अधिक हो सकती है।

सवाल: होगा एसटीएल के एल्गोरिदम के साथ इस तरह के एक बहु प्रॉक्सी दृष्टिकोण काम करता है? या कुछ एल्गोरिदम वास्तव में आवश्यकता पर भरोसा करते हैं कि एक्स को असली बूल * होना चाहिए? या क्या बहुत सारे उपयोगकर्ता परिभाषित रूपांतरण आवश्यक हैं जो इसे काम करने से रोकते हैं?

सभी libC++ के एल्गोरिदम vector<bool> के साथ काम करते हैं। उनमें से कुछ quite spectacular performance के साथ।

#include <vector> 
#include <cassert> 

int main() 
{ 
    std::vector<bool> v(1); 
    bool b = true; 
    assert(v[0] == false); 
    assert(b == true); 
    std::swap(b, v[0]); 
    assert(v[0] == true); 
    assert(b == false); 
} 

यह बहुत आसान कार्यान्वयन को पूरा करने के लिए है: विशेष चाहिए में एक एल्गोरिथ्म विशेष उपचार जो मानक दुर्भाग्य से जनादेश नहीं है। एक को यह सुनिश्चित करने की ज़रूरत है कि swapbool और vector<bool>::reference के किसी भी संयोजन के लिए काम करता है। लेकिन मुझे नहीं पता कि libC++ के अलावा कोई भी कार्यान्वयन यह करता है, और यह C++ 11 द्वारा अनिवार्य नहीं है।

बिट्स की एक सरणी अद्भुत डेटा संरचना है। लेकिन दुर्भाग्य से यह सी ++ मानक में खराब रूप से निर्दिष्ट है। libC++ कुछ हद तक निष्कासित हो गया है यह दिखाने के लिए कि यह एक बहुत ही उपयोगी और उच्च प्रदर्शन डेटा संरचना हो सकती है। आशा है कि भविष्य में सी ++ मानक सी ++ प्रोग्रामर के लाभ के लिए इस दिशा में माइग्रेट हो सकता है।

Answer 2

ऑफहैंड मैं पहले कहूंगा कि यह वास्तव में प्रत्येक व्यक्ति एसटीएल कार्यान्वयन के विवरण पर अधिक निर्भर करेगा क्योंकि यह आधिकारिक तौर पर मानक आवश्यकता के अनुरूप नहीं है जो * * संदर्भ_ प्रकार टी * के अंतराल के रूप में है। तो संभावित कार्यान्वयन मुद्दों के बारे में:

मुख्य कारण कोड के किसी भी भाग कंटेनर की सूचक होने पर स्पष्ट रूप से निर्भर होगा एक असलीbool* है अगर algo सूचक अंकगणित उपयोग कर रहा था, जिस स्थिति में सूचक प्रकार के आकार बन जाता है प्रासंगिक। पॉइंटर अंकगणित हालांकि इटरेटर इंटरफ़ेस को बाईपास करेगा और इस प्रकार पूरे एसटीएल कंटेनर-बाय-इटरेटर डिज़ाइन के मुख्य उद्देश्य को हरा देगा।std :: vector <> स्वयं को सी ++ 11 में संगत होने की गारंटी है, जो एसटीएल एल्गोस और कंपाइलर दोनों के अनुकूलित विशेषज्ञता को अनुमति देता है (:), जिनमें से दोनों आंतरिक रूप से पॉइंटर अंकगणितीय का उपयोग कर सकते हैं। यदि आपका प्रकार std :: वेक्टर से नहीं लिया गया है तो यह कोई मुद्दा नहीं होना चाहिए; सब कुछ सिर्फ इसके बजाय इटेटरेटर विधि मानना ​​चाहिए।

हालांकि! एसटीएल कोड अभी भी पॉइंटर्स पॉइंटर अंकगणित के उद्देश्य के लिए नहीं बल्कि किसी अन्य उद्देश्य के लिए ले सकता है। इस मामले में समस्या सी ++ वाक्यविन्यास है। उदाहरण के लिए, अपने खुद के सवाल के हवाले से:

बजाय

T* x = &v[0] एक तो कर सकता है auto x = &v[0]

एसटीएल में कोई टेम्प्लेटेड कोड भी एक ही बात करना होगा ... और उस पर पूरी तरह से संभावना नहीं लगता है इस बिंदु पर एसटीएल कार्यान्वयन auto का व्यापक उपयोग करेगा। अन्य स्थितियां हो सकती हैं कि एसटीएल चतुर आर-वैल्यू कास्टिंग ट्रिक्स करने का प्रयास करता है जो असफल हो जाते हैं क्योंकि यह विसंगतिपूर्ण संदर्भ प्रकारों की अपेक्षा नहीं कर रहा है।

for(auto b: v) { /* ... */ } के संबंध में: मुझे कोई कारण नहीं दिखता है जो काम नहीं करना चाहिए। मुझे लगता है कि यह कोड उत्पन्न करेगा जो उसी संस्करण से बहुत कम कुशल होगा जो आप 15 मिनट (या उससे कम) में खुद को रोल कर सकते हैं। ओपी में इंट्रिनिक्स का उल्लेख करने के बाद से मैं इसे केवल इसलिए लाता हूं, जो प्रदर्शन के लिए कुछ विचार करता है। आप इंट्रिनिक्स का उपयोग करके इसे बाहर करने में सक्षम नहीं होंगे। ऐसा कुछ भी नहीं है जो आंतरिक रूप से बिट्स की सरणी को पार करने के लिए एक सरल बिटवाइफ्ट शिफ्ट को पार कर सकता है। अधिकतर अतिरिक्त ओवरहेड कंपाइलर जनरेटिंग कोड से इटेटरेटर पॉइंटर और मास्क वैल्यू को अपडेट करने के लिए होगा, और फिर अगले पुनरावृत्ति पर मास्क वैल्यू को फिर से लोड करें। यह आपके द्वारा किए जा रहे प्रयासों को जादुई रूप से कम करने में सक्षम नहीं होगा और इसे आपके लिए अनुक्रमिक शिफ्ट ऑप में बदल देगा। यह कम से कम पॉइंट अपडेट + लिखने का चरण लूप के बाहर एक रजिस्टर में कैश करके ऑप्टिमाइज़ करने में सक्षम हो सकता है, हालांकि ईमानदारी से मैं अपने अनुभवों के आधार पर बहुत संदिग्ध होगा।

uint64_t* pBitSet = &v[-1]; // gets incremented on first iteration through loop. 
uint64_t curBitSet = v[0]; 

for (int i=0; i<v.length(); ++i) { 
    if ((i % 64) == 0) { 
     curBitSet = *(++pBitSet); 
    } 
    int bit = curBitSet & 1; 
    curBitSet >>= 1; 

    // do stuff based on 'bit' here. 
}