सी ++ मानक std::partitionForwardIterator और BidirectionalIterator के बीच अनुमानित अनुप्रयोगों की विभिन्न संख्याओं के लिए आवश्यक है। ForwardIterator संस्करण के लिए, विधेय आवेदनों की संख्या < = एन, जहां एन = std::distance(first, last), लेकिन BidirectionalIterator संस्करण के लिए, विधेय आवेदनों की संख्या < = एन/2 होगा किया जाएगा। जाहिर है, दोनों संस्करणों में समय जटिलता ओ (एन) है।सी ++ मानक को विभिन्न प्रकार के इटरेटर के लिए विभिन्न जटिलताओं को पूरा करने के लिए std :: विभाजन की आवश्यकता क्यों है?
मेरा सवाल है, यह विभिन्न प्रकार के इटरेटर के लिए अलग-अलग आवश्यकताओं को प्रदान करने के लिए परेशान क्यों है? इस तरह की आवश्यकता बहुत सारे कंपाइलर्स को मजबूर करती है?
उदाहरण: एमएसवीसी, इस तरह की आवश्यकता को पूरा करने के दो तरीकों से std::partition फ़ंक्शन को कार्यान्वित करें, जो बहुत ही सुरुचिपूर्ण प्रतीत नहीं होता है।
एक और सवाल: क्या कोई एल्गोरिथ्म है कि इस गुणांक पर निर्भर करता है कर रहे हैं, जैसे कि जब एन/2 हो जाता है एन, asymptotic जटिलता अलग होगा कि? मेरी समझ के लिए, यदि हम Master's Theorem पर T(n) = aT(n/b) + f(n) के रूप में मानते हैं, तो f(n) में गुणांक इससे कोई फर्क नहीं पड़ता।
सीएफ। MSVC के विभाजन के एक बराबर कार्यान्वयन:
template<class BidirIt, class UnaryPred>
BidirIt partition(BidirIt first, BidirIt last, UnaryPred pred, std::bidirectional_iterator_tag)
{
while (true)
{
while ((first != last) && pred(*first))
{
++first;
}
if (first == last)
{
break;
}
--last;
while ((first != last) && !pred(*last))
{
--last;
}
if (first == last)
{
break;
}
std::iter_swap(first, last);
++first;
}
return first;
}
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred, std::forward_iterator_tag)
{
first = std::find_if_not(first, last, pred);
if (first == last)
{
return first;
}
for (ForwardIt src = std::next(first); src != last; ++src)
{
if (pred(*src))
{
std::iter_swap(first, src);
++src;
}
}
return first;
}
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred)
{
return partition(first, last, pred, typename std::iterator_traits<ForwardIt>::iterator_category());
}
मेरे प्रश्न का उत्तर देने के लिए बहुत बहुत धन्यवाद। जैसा कि बताया गया है, मैंने अनुमानित अनुप्रयोगों की संख्या पर गलती की है। दोनों संस्करण * एन * अनुप्रयोगों के लिए हैं। यह अलग-अलग स्वैप की संख्या है। अब मैं समझ सकता हूं कि मानक की आवश्यकता है क्योंकि यह इष्टतम आवश्यकता है। आपके तरह के उत्तरों के लिए फिर से धन्यवाद। :) –
आपका स्वागत है। यदि उत्तर आपके प्रश्न का उत्तर देता है तो कृपया उत्तर को स्वीकार के रूप में चिह्नित करें। – michalsrb