विषय पर बढ़ें

अंतिम अद्यतन：2026-10-12

STL इटरेटर सोर्स कोड विश्लेषण

0.प्रस्तावना

यह अनुभाग पिछले अनुभाग की traits विशेषता का उपयोग करके iterator के सोर्स कोड का अध्ययन करता है, एक सरल iterator_category कार्यान्वित करता है, तथा iterator के सोर्स कोड स्ट्रक्चर का विश्लेषण करता है।

जानना कि क्या है, यह भी जानना कि क्यों है — सोर्स कोड के सामने कोई रहस्य नहीं बचता!

1.traits मशीन का उपयोग करके एक सरल iterator_category पहचान कार्यान्वित करना

पिछले अनुभाग में इटरेटर की भूमिका बताई गई थी, जो पहले की तरह नीचे के चित्र में दिखाया गया है:

rela

इटरेटर, सीक्वेंस के एलिमेंट्स की ओर इशारा करने वाले पॉइंटर का एक एब्स्ट्रैक्शन है। इटरेटर का उपयोग करके हम सीक्वेंस के किसी एलिमेंट तक पहुँच सकते हैं, सीक्वेंस के किसी एलिमेंट का मान बदल सकते हैं, इटरेटर को आगे या पीछे चला सकते हैं, इत्यादि।

इटरेटर में सामान्यतः पाँच प्रकार के टाइप होते हैं: value_type, difference_type, reference_type, pointer_type — इन सभी को traits तथा संगत पार्शियल स्पेशलाइज़ेशन द्वारा निकालना अपेक्षाकृत सरल है।

परंतु iterator_category सामान्यतः 5 प्रकार के होते हैं, और यह संगत टाइप काफी बड़े पैमाने पर कोड लेखन का कार्य खड़ा कर देता है।

  • एक दिशा में चलने वाला केवल-पठनीय इटरेटर Input Iterator
  • एक दिशा में चलने वाला केवल-लेखनीय इटरेटर Output Iterator
  • एक दिशा में चलने वाला पठन-लेखन इटरेटर Forward Iterator
  • दोनों दिशाओं में चलने वाला पठन-लेखन इटरेटर Bidirectional Iterator

iterator

उदाहरण के लिए: हमने advanceII, advanceBI, advanceRAI कार्यान्वित किए, जो क्रमशः Input Iterator, Bidirectional Iterator तथा Random Access Iterator इटरेटर टाइप के संगत कार्यान्वयन दर्शाते हैं।

template<class Iterator>
void advance(Iterator& i) {
    if (is_random_access_iterator(i))
        advanceRAI(i,n);
    if (is_bidirectional_iterator(i))
        advanceBI(i,n);
    else
        advanceII(i,n);
}

पर इस तरह निष्पादन के समय यह तय होना कि कौन-सा संस्करण उपयोग करना है, प्रोग्राम की दक्षता को प्रभावित करता है। सर्वोत्तम होगा कि संकलन के समय ही सही संस्करण चुन लिया जाए।

और ओवरलोडिंग — फंक्शन की यह कार्यप्रणाली — यह लक्ष्य प्राप्त कर सकती है।

advanceXX() के दोनों फंक्शन पैरामीटर अनिर्धारित टाइप के हैं (क्योंकि दोनों टेम्प्लेट पैरामीटर हैं)। इन्हें समान नाम देकर ओवरलोडेड फंक्शन्स बनाने के लिए, हमें एक ऐसा फंक्शन पैरामीटर जोड़ना होगा जिसका टाइप निर्धारित हो, ताकि फंक्शन ओवरलोडिंग कार्यप्रणाली प्रभावी रूप से चल सके।

डिज़ाइन इस प्रकार है: यदि traits में इटरेटर का प्रकार निकालने की क्षमता है, तो हम इस “इटरेटर टाइप” संगत टाइप को advancexx के तीसरे पैरामीटर के रूप में उपयोग कर सकते हैं; और यह संगत टाइप अवश्य ही एक class type होना चाहिए, केवल संख्या-नंबर जैसी कोई चीज़ नहीं, क्योंकि कंपाइलर को ओवरलोड रेज़ोल्यूशन के लिए इसी पर निर्भर रहना होता है।

अब इसे कार्यान्वित करते हैं; सबसे पहले एक समग्र स्ट्रक्चर आरेख:

itera

निम्नलिखित tag परिभाषित करें:

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件

कुछ tag घोषित करने के बाद, हम advance फंक्शन को ओवरलोड कर सकते हैं; हम इन फंक्शन्स को अंडरस्कोर के साथ परिभाषित करते हैं, जो दर्शाता है कि ये आंतरिक उपयोग के लिए हैं और बाहर से दिखाई नहीं देते।

// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件
// input iterator
template<class inputIterator, class distance>
inline void __advance(inputIterator&i, distance n,
                      input_iterator_tag) {
    std::cout << "input tag" << std::endl;
}
// output iterator
template<class outputIterator, class distance>
inline void __advance(outputIterator&i, distance n,
                      output_iterator_tag) {
    std::cout << "output tag" << std::endl;
}

// forward iterator
template<class ForwardIterator, class Distance>
inline void __advance(ForwardIterator &i, Distance n,
                      forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline void __advance(BidiectionalIterator &i, Distance n,
                      bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;

}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator &i, Distance n,
                      random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;

}

traits मशीन परिभाषित करें:

// traits 型别
template<class I>
struct Iterator_traits {
    typedef typename I::iterator_category iterator_category;
};

// 针对原生指针设计的"偏特化版"
template<class I>
struct Iterator_traits<I *> {
    typedef random_access_iterator_tag iterator_category;
};
template<class I>
struct Iterator_traits<const I *> {
    typedef random_access_iterator_tag iterator_category;
};

बाहरी इंटरफ़ेस उजागर करना:

// 对外接口
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    __advance(i, n, category()); // 各型别的重载
}

class type परिभाषित करें:

// class type
template<class Category>
struct iterator {
    typedef Category iterator_category;
};

अब परीक्षण शुरू करते हैं। हम उपरोक्त परिभाषित class type तथा रॉ (native) पॉइंटर से परीक्षण करते हैं — क्रमशः traits मशीन के सामान्य संस्करण तथा पार्शियल-स्पेशलाइज़्ड संस्करण में प्रवेश कराकर — और देखते हैं कि संगत Tag प्राप्त होता है या नहीं।

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    advance(input, 10);
    advance(output, 10);
    advance(forward, 10);
    advance(bidect, 10);
    advance(random, 10);
    int *p=NULL;
    advance(p,10);
    return 0;
}

आउटपुट परिणाम:

input tag
output tag
forward tag
bidrectional tag
randomaccess tag
randomaccess tag

सब कुछ हमारी अपेक्षा के अनुरूप रहा — traits मशीन के माध्यम से हमें प्रत्येक इटरेटर का tag, तथा रॉ पॉइंटर का tag प्राप्त हुआ।

अब थोड़ा और जटिल सोचते हैं — यदि हम advance का रिटर्न टाइप जानना चाहें, तो क्या करें?

सबसे पहले advance का रिटर्न बदलें:

// 对外接口
template<class InputIterator, class Distance>
inline typename Iterator_traits<InputIterator>::iterator_category
advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    return __advance(i, n, category()); // 各型别的重载
}

इसके तुरंत बाद __advance का रिटर्न बदलें:

// input iterator
template<class inputIterator, class distance>
inline typename Iterator_traits<inputIterator>::iterator_category
__advance(inputIterator &i, distance n,
          input_iterator_tag) {
    std::cout << "input tag" << std::endl;
    return input_iterator_tag();
}

// output iterator
template<class outputIterator, class distance>
inline typename Iterator_traits<outputIterator>::iterator_category
__advance(outputIterator &i, distance n,
          output_iterator_tag) {
    std::cout << "output tag" << std::endl;
    return output_iterator_tag();
}

// forward iterator
template<class ForwardIterator, class Distance>
inline typename Iterator_traits<ForwardIterator>::iterator_category
__advance(ForwardIterator &i, Distance n,
          forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
    return forward_iterator_tag();
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline typename Iterator_traits<BidiectionalIterator>::iterator_category
__advance(BidiectionalIterator &i, Distance n,
          bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;
    return bidiectional_iterator_tag();
}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline typename Iterator_traits<RandomAccessIterator>::iterator_category
__advance(RandomAccessIterator &i, Distance n,
          random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;
    return random_access_iterator_tag();
}

केवल void को संगत traits से बदलना ही पर्याप्त है।

अंत में परीक्षण कोड में परिवर्तन कर, रिटर्न जोड़ें:

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    input_iterator_tag inputIteratorTag = advance(input, 10);
    output_iterator_tag outputIteratorTag = advance(output, 10);
    forward_iterator_tag forwardIteratorTag = advance(forward, 10);
    bidiectional_iterator_tag bidiectionalIteratorTag = advance(bidect, 10);
    random_access_iterator_tag randomAccessIteratorTag = advance(random, 10);
    int *p = NULL;
    random_access_iterator_tag v = advance(p, 10);
    return 0;
}

इस प्रकार एक सरल इटरेटर-टाइप का कंपाइलर-स्तरीय निर्धारण कार्यान्वित हो गया।

2.STL सोर्स कोड विश्लेषण: Iterator

bits/stl_iterator_base_types.h में भी यही है जो ऊपर दिखाया गया है (वास्तव में, ऊपर वाला कोड STL सोर्स कोड का सरलीकृत संस्करण है, बहुत निकट का) — आइए एक साथ देखें।

(1) tag

 ///  Marking input iterators.
  struct input_iterator_tag { };

  ///  Marking output iterators.
  struct output_iterator_tag { };

  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag { };

  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag { };

  /// Random-access iterators support a superset of bidirectional
  /// iterator operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag { };

मैंने ऊपर जो उपयोग किया, वही है।

(2) iterator_traits traits मशीन में पाँच प्रकार शामिल हैं, जबकि ऊपर हमने उनमें से केवल एक कार्यान्वित किया: iterator_category। इसीलिए STL में कंटेनरों तथा एल्गोरिद्म के बीच के सेतु iterator में निम्नलिखित पाँच typedef अनिवार्य रूप से शामिल होने चाहिए।

template<typename _Iterator>
struct iterator_traits
{
  typedef typename _Iterator::iterator_category iterator_category;
  typedef typename _Iterator::value_type        value_type;
  typedef typename _Iterator::difference_type   difference_type;
  typedef typename _Iterator::pointer           pointer;
  typedef typename _Iterator::reference         reference;
};

(3) iterator

ऊपर उल्लिखित class type नीचे वाले का सरलीकृत संस्करण है; तुलना करने पर कोई विशेष अंतर नहीं — बस टेम्प्लेट पैरामीटर कुछ अधिक हैं और typedef अधिक हैं।

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
       typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
  /// One of the @link iterator_tags tag types@endlink.
  typedef _Category  iterator_category;
  /// The type "pointed to" by the iterator.
  typedef _Tp        value_type;
  /// Distance between iterators is represented as this type.
  typedef _Distance  difference_type;
  /// This type represents a pointer-to-value_type.
  typedef _Pointer   pointer;
  /// This type represents a reference-to-value_type.
  typedef _Reference reference;
};

इस प्रकार iterator तथा traits विशेषता का विश्लेषण पूरा हुआ। STL सोर्स कोड के रहस्यों पर मेरे साथ चर्चा के लिए आपका स्वागत है; जैसा 侯捷 शिक्षक ने कहा: सोर्स कोड के सामने कोई रहस्य नहीं बचता।

संबंधित विषय

टिप्पणियाँ