मानक आवंटकों को आवंटित स्मृति आवंटित करने की आवश्यकता है?

Question

मुझे सी ++ 11 मानक में कोई संकेत नहीं मिल रहा है कि किसी मानक-अनुरूप आवंटक को एक सूचक स्मृति ब्लॉक में वापस करने के लिए आवश्यक है या नहीं।

std::vector (23.3.6.1/1) पर संगत भंडारण आवश्यकता को ऐसा लगता है (अन्यथा ऐसा लगता है कि std::vector का उपयोग मनमाने ढंग से मानक-अनुरूप आवंटक के साथ करना असंभव होगा)। लेकिन किसी भी स्पष्टीकरण का स्वागत किया जाएगा।

एक बराबर सवाल यह है: मैं हमेशा (संभवतः एक सादे कच्चे सी ++ सूचक के रूप में उदाहरण के here के लिए वर्णित करने के लिए सामान्य pointer प्रकार allocate() द्वारा वापस परिवर्तित करने के बाद) स्मृति सूचक arithmetics के माध्यम से allocate() द्वारा दिया ब्लॉक के माध्यम से स्थानांतरित कर सकते हैं?

Answer 1

हां, यह संगत होना चाहिए, इस अर्थ में कि allocator::pointer पर पॉइंटर अंकगणित अपेक्षित कार्य करता है।

यदि आप इसके बारे में सोचते हैं, तो स्मृति शायद ही कभी शारीरिक रूप से संगत हो जाती है। यह केवल संगत दिखता है क्योंकि आधुनिक सीपीयू की वर्चुअल मेमोरी है, और इस वर्चुअल मेमोरी के भीतर व्याख्या की गई है।

Answer 2

यह contiguous द्वारा आपके माध्य पर निर्भर करता है। जैसा कि आपके प्रोग्राम द्वारा देखा गया स्मृति निश्चित रूप से संगत होगा, या यह ऑफसेट/इंडेक्स को सरणी में गणना करने के लिए "सही काम नहीं करेगा", और इस तरह की। यदि आप 10 पूर्णांक मान आवंटित करते हैं, तो आप ptr[0] को पहले व्यक्ति बनने के लिए चाहते हैं, और ptr[9] अंतिम होने के लिए - ptr केवल एक ही सूचक है, यह केवल स्मृति के एक एकल, संगत ब्लॉक को इंगित कर सकता है।

वास्तविक शारीरिक स्मृति में, हुड के तहत, यह संगत हो सकता है या नहीं - यह ओएस के लिए कुछ निर्धारित करने और निर्णय लेने के लिए कुछ है, और यह एप्लिकेशन मेमोरी को "कहीं भी" दे सकता है।

Answer 3

एक संभाजक A देखते हुए, मैं कहूँगा कि Aसन्निहित स्मृति प्रदान करता है, तो किसी भी pA::allocate(n) द्वारा दिया, के लिए std::addressof(*p) + k == std::addressof(*(p + k))k अंतराल [0,n) और std::addressof(*(p + n - 1)) + 1 == std::addressof(*p) + n में है जब।

मुझे नहीं इस संपत्ति संभाजक आवश्यकताओं (§17.6.3.5 [allocator.requirements]) में आवश्यक किया जा रहा है, लेकिन मैं कल्पना नहीं कर सकते इसके बिना vector (और विशेष रूप vector::data()) को लागू करने के लिए कैसे। या तो (ए) मुझे आवंटन आवश्यकताओं में कुछ याद आ रहा है, (बी) आवंटन आवश्यकताओं को अनिर्धारित किया गया है, या (सी) vector सामान्य आवश्यकताओं से परे अपने आवंटक पर अतिरिक्त आवश्यकता लागू कर रहा है।

#include <cstddef> 
#include <iostream> 
#include <iterator> 
#include <limits> 
#include <memory> 

template <typename T> 
class ScaledPointer : public std::iterator<std::random_access_iterator_tag, T> { 
    T* ptr; 
public: 
    ScaledPointer() = default; 
    ScaledPointer(T* ptr) : ptr(ptr) {} 
    template <typename U> 
    explicit ScaledPointer(U* ptr) : ptr(static_cast<T*>(ptr)) {} 
    template <typename U> 
    explicit ScaledPointer(const ScaledPointer<U>& other) : 
    ptr(static_cast<T*>(other.ptr)) {} 

    explicit operator bool() const { return bool{ptr}; } 

    T& operator *() const { 
    return *ptr; 
    } 
    T* operator ->() const { 
    return ptr; 
    } 

    T& operator [] (std::ptrdiff_t n) const { 
    return ptr[2 * n]; 
    } 

    ScaledPointer& operator ++() { 
    ptr += 2; 
    return *this; 
    } 
    ScaledPointer operator ++ (int) { 
    ScaledPointer tmp(*this); 
    ++*this; 
    return tmp; 
    } 

    ScaledPointer& operator --() { 
    ptr -= 2; 
    return *this; 
    } 
    ScaledPointer operator -- (int) { 
    ScaledPointer tmp(*this); 
    --*this; 
    return tmp; 
    } 

    template <typename U, typename V> 
    friend bool operator == (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return u.ptr == v.ptr; 
    } 
    template <typename U, typename V> 
    friend bool operator != (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return !(u == v); 
    } 

    template <typename U, typename V> 
    friend bool operator < (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return u.ptr < v.ptr; 
    } 
    template <typename U, typename V> 
    friend bool operator > (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return v < u; 
    } 
    template <typename U, typename V> 
    friend bool operator <= (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return !(v < u); 
    } 
    template <typename U, typename V> 
    friend bool operator >= (const ScaledPointer<U>& u, const ScaledPointer<V>& v) { 
    return !(u < v); 
    } 

    ScaledPointer& operator += (std::ptrdiff_t n) { 
    ptr += 2 * n; 
    return *this; 
    } 
    friend ScaledPointer operator + (const ScaledPointer& u, std::ptrdiff_t n) { 
    ScaledPointer tmp = u; 
    tmp += n; 
    return tmp; 
    } 


    ScaledPointer& operator -= (std::ptrdiff_t n) { 
    ptr -= 2 * n; 
    return *this; 
    } 
    friend ScaledPointer operator - (const ScaledPointer& u, std::ptrdiff_t n) { 
    ScaledPointer tmp = u; 
    tmp -= n; 
    return tmp; 
    } 

    friend std::ptrdiff_t operator - (const ScaledPointer& a, const ScaledPointer& b) { 
    return (a.ptr - b.ptr)/2; 
    } 
}; 

template <typename T> 
class ScaledAllocator { 
public: 
    typedef ScaledPointer<T> pointer; 
    typedef T value_type; 
    typedef std::size_t size_type; 

    pointer allocate(size_type n) { 
    const std::size_t size = (n * (2 * sizeof(T))); 
    void* p = ::operator new(size); 
    std::cout << __FUNCTION__ << '(' << n << ") = " << p << std::endl; 
    std::fill_n((unsigned*)p, size/sizeof(unsigned), 0xFEEDFACEU); 
    return pointer{p}; 
    } 

    void deallocate(pointer p, size_type n) { 
    std::cout << __FUNCTION__ << '(' << &*p << ", " << n << ')' << std::endl; 
    ::operator delete(&*p); 
    } 

    static size_type max_size() { 
    return std::numeric_limits<size_type>::max()/2; 
    } 

    template <typename U, typename V> 
    friend bool operator == (const ScaledAllocator<U>&, const ScaledAllocator<V>&) { 
    return true; 
    } 
    template <typename U, typename V> 
    friend bool operator != (const ScaledAllocator<U>&, const ScaledAllocator<U>&) { 
    return false; 
    } 
}; 

#include <algorithm> 
#include <vector> 

int main() { 
    using namespace std; 
    cout << hex << showbase; 

    vector<unsigned, ScaledAllocator<unsigned>> vec = {0,1,2,3,4}; 
    for_each(begin(vec), end(vec), [](unsigned i){ cout << i << ' '; }); 
    cout << endl; 

    auto p = vec.data(); 
    for(auto i = decltype(vec.size()){0}, n = vec.size(); i < n; ++i) 
    cout << p[i] << ' '; 
    cout << endl; 
} 

जब n आइटमों के लिए स्थान आवंटित करने के लिए कहा, ScaledAllocator2 * n के लिए जगह आवंटित:

यहाँ एक संभाजक कि सन्निहित स्मृति (paste of this code) प्रदान नहीं करता है की एक "सरल" उदाहरण है। इसका सूचक प्रकार इसके पॉइंटर अंकगणित के लिए आवश्यक स्केलिंग भी करता है। असल में, यह 2 एन वस्तुओं की एक सरणी आवंटित करता है और केवल डेटा के लिए भी क्रमांकित स्लॉट का उपयोग करता है।

क्या कोई भी आवंटन आवश्यकता देख सकता है जो ScaledAllocator संतुष्ट करने में विफल रहता है?

संपादित करें: इस सवाल का जवाब समीक्षकों संभाजक आवश्यकताओं तालिका में सदस्य समारोह allocate(n) के प्रभाव के मानक के वर्णन के अर्थ पर टिका है: "मेमोरी प्रकार T की n वस्तुओं लेकिन वस्तुओं का निर्माण नहीं कर रहे हैं के लिए आवंटित किया गया है। " मुझे लगता है कि हम सभी सहमत होंगे कि इसका मतलब है p == allocate(n)p + kk[0,n] में k[0,n) में k के लिए dereferencable है। दूसरे शब्दों में, स्मृति का एक ब्लॉक जो आवंटक के सूचक प्रकार के डोमेन में संगत है।

क्या स्पष्ट नहीं है - हालांकि यह बहुत ही अप्रत्यक्ष रूप से std::vector::data() के विवरण से निहित है - यह है कि स्मृति को कच्चे पॉइंटर्स (मेरे पहले पैराग्राफ में विस्तृत औपचारिक प्रस्ताव) के डोमेन में भी शामिल होना चाहिए। यह अच्छा होगा अगर मानक या तो (ए) सभी आवंटकों को लागू होने वाली संगतता आवश्यकता के बारे में स्पष्ट हो, या (बी) उस आवश्यकता को ContiguousAllocator अवधारणा में जोड़ें और निर्दिष्ट करें कि std::vector को ContiguousAllocator की आवश्यकता है।