c++ - हरण - आईओटीएएन(एसटीएल से लापता एल्गोरिदम) का एक अच्छा कार्यान्वयन क्या होगा




फ्लो चार्ट बनाने की विधि (2)

आप कोड पीढ़ी पर इतना ध्यान केंद्रित कर रहे हैं कि आप इंटरफ़ेस का अधिकार प्राप्त करने में भूल गए थे।

आपको OutputIterator आवश्यकता है, लेकिन क्या होगा अगर आप इसे दूसरी बार कॉल करना चाहते हैं?

list<double> list(2 * N);
iota_n(list.begin(), N, 0);
// umm...
iota_n(list.begin() + N, N, 0); // doesn't compile!
iota_n(list.rbegin(), N, 0); // works, but create 0..N,N-1..0, not 0..N,0..N
auto it = list.begin();
std::advance(it, N);
iota_n(it, N, 0); // works, but ... yuck and ... slow (O(N))

iota_n अंदर, आप अभी भी जानते हैं कि आप कहां हैं, लेकिन आपने उस जानकारी को निकाल दिया है, इसलिए कॉलर लगातार समय पर इसे नहीं प्राप्त कर सकता है

सामान्य सिद्धांत: उपयोगी जानकारी नहीं फेंकें

template <typename OutputIterator, typename SizeType, typename ValueType>
auto iota_n(OutputIterator dest, SizeType N, ValueType value) {
    while (N) {
        *dest = value;
        ++dest;
        ++value;
        --N;
    }
    // now, what do we know that the caller might not know?
    // N? No, it's zero.
    // value? Maybe, but it's just his value + his N
    // dest? Definitely. Caller cannot easily compute his dest + his N (O(N))
    //       So, return it:
    return dest;
}

इस परिभाषा के साथ, उपर्युक्त उदाहरण बस हो जाता है:

list<double> list(2 * N);
auto it = iota_n(list.begin(), N, 0);
auto end = iota_n(it, N, 0);
assert(end == list.end());

सी ++ 11 के साथ, एसटीएल अब एक std::iota फ़ंक्शन (एक संदर्भ देखें) है। std::fill_n विपरीत, std::generate_n , कोई std::iota_n , हालांकि। उस के लिए एक अच्छा कार्यान्वयन क्या होगा? एक सीधा लूप (वैकल्पिक 1) या एक साधारण लैम्ब्डा अभिव्यक्ति (वैकल्पिक 2) के साथ std::generate_n को प्रतिनिधिमंडल?

वैकल्पिक 1)

template<class OutputIterator, class Size, class T>
OutputIterator iota_n(OutputIterator first, Size n, T value)
{
        while (n--)
                *first++ = value++;
        return first;
}

वैकल्पिक 2)

template<class OutputIterator, class Size, class T>
OutputIterator iota_n(OutputIterator first, Size n, T value)
{
        return std::generate_n(first, n, [&](){ return value++; });
}    

क्या दोनों विकल्प कंपाइलर्स को अनुकूलित करने के साथ समान कोड बनाएंगे?

अद्यतन : @ मार्क मट्ज़ के उत्कृष्ट बिंदु को भी शामिल करने के लिए अपने गंतव्य बिंदु पर इटरेटर वापस। यह भी है कि कैसे std::generate_n सी ++ 9 की तुलना में सी ++ 11 में नवीनीकृत हुआ।


यादृच्छिक उदाहरण के रूप में, मैंने निम्नलिखित कोड को g++ -S -O2 -masm=intel (जीसीसी 4.7.1, x86_32) के साथ संकलित किया:

void fill_it_up(int n, int * p, int val)
{
    asm volatile("DEBUG1");
    iota_n(p, n, val);
    asm volatile("DEBUG2");
    iota_m(p, n, val);
    asm volatile("DEBUG3");
    for (int i = 0; i != n; ++i) { *p++ = val++; }
    asm volatile("DEBUG4");
}

यहां iota_n पहला संस्करण है और iota_m दूसरा है विधानसभा सभी तीन मामलों में यह है:

    test    edi, edi
    jle .L4
    mov edx, eax
    neg edx
    lea ebx, [esi+edx*4]
    mov edx, eax
    lea ebp, [edi+eax]
    .p2align 4,,7
    .p2align 3
.L9:
    lea ecx, [edx+1]
    cmp ecx, ebp
    mov DWORD PTR [ebx-4+ecx*4], edx
    mov edx, ecx
    jne .L9

-O3 साथ, तीन संस्करण बहुत समान हैं, लेकिन बहुत अधिक समय (सशर्त चाल और punpcklqdq और इस तरह की तरह)।





iota