c++ - क्या करता है std:: वेक्टर स्मृति में दिखता है?




memory vector (4)

मैंने पढ़ा कि std::vector को सन्निहित होना चाहिए। मेरी समझ यह है, कि इसके तत्वों को एक साथ संग्रहित किया जाना चाहिए, मेमोरी में नहीं फैलाना चाहिए। मैंने केवल इस तथ्य को स्वीकार किया है और इस ज्ञान का उपयोग किया है जब उदाहरण के लिए इसके data() पद्धति का उपयोग करके अंतर्निहित सन्निहित स्मृति प्राप्त करने के लिए।

हालाँकि, मैं एक ऐसी स्थिति में आया था, जहाँ वेक्टर की स्मृति अजीब तरीके से व्यवहार करती है:

std::vector<int> numbers;
std::vector<int*> ptr_numbers;
for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
}

मुझे उम्मीद थी कि यह मुझे कुछ संख्याओं का वेक्टर और इन संख्याओं को इंगित करने वाला वेक्टर प्रदान करेगा। हालाँकि, जब ptr_numbers पॉइंटर्स की सामग्री को सूचीबद्ध करते हैं, तो अलग और प्रतीत होता है यादृच्छिक संख्याएं हैं, जैसे कि मैं स्मृति के गलत हिस्सों तक पहुंच रहा हूं।

मैंने हर कदम पर सामग्री की जाँच करने की कोशिश की है:

for (int i = 0; i < 8; i++) {
    numbers.push_back(i);
    ptr_numbers.push_back(&numbers.back());
    for (auto ptr_number : ptr_numbers)
       std::cout << *ptr_number << std::endl;
    std::cout << std::endl;
}

परिणाम लगभग इस तरह दिखता है:

1

some random number
2

some random number
some random number
3

तो ऐसा लगता है कि जब मैं numbers वेक्टर पर push_back() हूं, तो इसके पुराने तत्व अपना स्थान बदलते हैं।

तो इसका सही अर्थ क्या है, कि std::vector एक सन्निहित कंटेनर है और इसके तत्व क्यों चलते हैं? क्या यह शायद उन्हें एक साथ संग्रहीत करता है, लेकिन उन सभी को एक साथ स्थानांतरित करता है, जब अधिक स्थान की आवश्यकता होती है?

संपादित करें: क्या std::vector सन्निहित केवल C ++ 17 के बाद से है? (मेरे पिछले दावे पर टिप्पणी को भविष्य के पाठकों के लिए प्रासंगिक रखने के लिए।)


तो इसका सही अर्थ क्या है, कि std :: वेक्टर एक सन्निहित कंटेनर है और इसके तत्व क्यों चलते हैं? क्या यह शायद उन्हें एक साथ संग्रहीत करता है, लेकिन उन सभी को एक साथ स्थानांतरित करता है, जब अधिक स्थान की आवश्यकता होती है?

ठीक यही है कि यह कैसे काम करता है और क्यों अपील करने वाले तत्व वास्तव में सभी पुनरावृत्तियों के साथ-साथ मेमोरी स्थानों को अमान्य कर देते हैं जब एक वास्तविक स्थान लेता है। यह केवल C ++ 17 के बाद से मान्य नहीं है, यह तब से अब तक का मामला है।

इस दृष्टिकोण से कुछ लाभ हैं:

  • यह बहुत कैश-फ्रेंडली है और इसलिए कुशल है।
  • data() विधि का उपयोग अंतर्निहित रॉ मेमोरी को एपीआई के लिए किया जा सकता है जो कच्चे पॉइंटर्स के साथ काम करता है।
  • push_back , reserve या नई मेमोरी को आवंटित करने की लागत निरंतर समय के साथ कम हो जाती है, क्योंकि समय के साथ ज्यामितीय विकास में वृद्धि होती है (प्रत्येक बार push_back कहा जाता है, यह क्षमता libc ++ और libstdc ++ में दोगुनी है, और 1.5 के कारक द्वारा लगभग बढ़ जाती है। MSVC)।
  • यह सबसे प्रतिबंधित पुनरावृत्ति श्रेणी, अर्थात, यादृच्छिक अभिगम पुनरावृत्तियों के लिए अनुमति देता है, क्योंकि डेटा को संचित रूप से संग्रहीत करने पर शास्त्रीय सूचक अंकगणित अच्छी तरह से काम करता है।
  • एक और से एक वेक्टर उदाहरण का निर्माण बहुत सस्ता है।

इन निहितार्थों को इस तरह के मेमोरी लेआउट का नकारात्मक पहलू माना जा सकता है:

  • तत्वों के लिए सभी पुनरावृत्तियों और संकेत वेक्टर के संशोधनों पर अमान्य हैं जो एक वास्तविक स्थान है। यह सूक्ष्म कीड़े को जन्म दे सकता है जब उदाहरण तत्वों को मिटाते हुए एक वेक्टर के तत्वों पर पुनरावृत्ति करते हैं।
  • push_front (जैसा कि std::list या std::deque provide) जैसे std::deque प्रदान नहीं किए जाते हैं ( insert(vec.begin(), element) काम करता है, लेकिन संभवतः महंगा है), और साथ ही कई वेक्टर इंस्टेंस के कुशल मर्जिंग / स्प्लिसिंग ।

That इस ओर इशारा करने के लिए @ फ्रांस्वाएंड्रीक्स को धन्यवाद।


उत्तर

यह एक एकल सन्निहित भंडारण (1d सरणी) है। हर बार जब यह क्षमता से बाहर हो जाता है तो यह वास्तविक हो जाता है और संग्रहीत वस्तुओं को नए बड़े स्थान पर ले जाया जाता है - यही कारण है कि आप संग्रहित वस्तुओं के पते बदलते रहते हैं।

यह हमेशा से यही रहा है, C++17 बाद से नहीं।

टी एल; डॉ

स्टोरेज ज्यामितीय रूप से बढ़ रहा है ताकि push_back() O(1) push_back() O(1) push_back() की आवश्यकता को सुनिश्चित किया जा सके। C ++ स्टैंडर्ड लाइब्रेरी ( GCC , STLPort , STLPort ) और 1.5 ( Cap n + 1 = Cap n + Cap n / 2 ) के अधिकांश कार्यान्वयन में वृद्धि कारक 2 ( Cap n + 1 = Cap n + Cap n ) है। MSVC संस्करण।

यदि आप इसे vector::reserve(N) और पर्याप्त रूप से बड़े N साथ पूर्व-आवंटित करते हैं, तो जब आप नए जोड़ते हैं, तो संग्रहीत वस्तुओं के पते नहीं बदलेंगे।

अधिकांश व्यावहारिक अनुप्रयोगों में आमतौर पर एक-दूसरे का अनुसरण करते हुए पहले कुछ वास्तविकताओं को छोड़ने के लिए कम से कम 32 तत्वों को पूर्व-आबंटित करने लायक होता है। (0 → 1 → 2 → 4 → 8 → 16)।

इसे धीमा करने के लिए कभी-कभी व्यावहारिक भी होता है, अंकगणित विकास नीति ( कैप एन + 1 = कैप एन + कॉन्सट ) पर स्विच करें, या कुछ बड़े आकार के बाद पूरी तरह से रोकें ताकि यह सुनिश्चित हो सके कि आवेदन बेकार नहीं गया है या मेमोरी से बाहर नहीं निकला है।

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


वास्तविक संरचना के संदर्भ में, एक std::vector स्मृति में कुछ इस तरह दिखता है:

struct vector {    // Simple C struct as example (T is the type supplied by the template)
  T *begin;        // vector::begin() probably returns this value
  T *end;          // vector::end() probably returns this value
  T *end_capacity; // First non-valid address
  // Allocator state might be stored here (most allocators are stateless)
};

LLVM द्वारा उपयोग किए गए libc++ कार्यान्वयन से प्रासंगिक कोड स्निपेट

एक std::vector की कच्ची मेमोरी सामग्री को प्रिंट करना:
(यदि आप नहीं जानते कि आप क्या कर रहे हैं तो ऐसा न करें!)

#include <iostream>
#include <vector>

struct vector {
    int *begin;
    int *end;
    int *end_capacity;
};

int main() {
    union vecunion {
        std::vector<int> stdvec;
        vector           myvec;
        ~vecunion() { /* do nothing */ }
    } vec = { std::vector<int>() };
    union veciterator {
        std::vector<int>::iterator stditer;
        int                       *myiter;
        ~veciterator() { /* do nothing */ }
    };

    vec.stdvec.push_back(1); // Add something so we don't have an empty vector

    std::cout
      << "vec.begin          = " << vec.myvec.begin << "\n"
      << "vec.end            = " << vec.myvec.end << "\n"
      << "vec.end_capacity   = " << vec.myvec.end_capacity << "\n"
      << "vec's size         = " << vec.myvec.end - vec.myvec.begin << "\n"
      << "vec's capacity     = " << vec.myvec.end_capacity - vec.myvec.begin << "\n"
      << "vector::begin()    = " << (veciterator { vec.stdvec.begin() }).myiter << "\n"
      << "vector::end()      = " << (veciterator { vec.stdvec.end()   }).myiter << "\n"
      << "vector::size()     = " << vec.stdvec.size() << "\n"
      << "vector::capacity() = " << vec.stdvec.capacity() << "\n"
      ;
}

std::vector एक सन्निहित कंटेनर होने का मतलब है कि आप क्या सोचते हैं इसका मतलब है।

हालांकि, एक वेक्टर पर कई ऑपरेशन मेमोरी के उस पूरे टुकड़े को फिर से ढूँढ सकते हैं।

एक सामान्य मामला यह है कि जब आप इसमें तत्व जोड़ते हैं, तो वेक्टर को विकसित होना चाहिए, यह सभी तत्वों को फिर से आवंटित कर सकता है और स्मृति के दूसरे सन्निहित टुकड़े में कॉपी कर सकता है।





contiguous