क्रमबद्ध तत्वों, लेकिन रखने पर कुछ को

Question

तय समारोह

template <typename Container, typename Comparator, typename Predicate> 
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) 

कंटेनर c सॉर्ट करने के लिए आदेश देने की कसौटी comp के अनुसार है, लेकिन उन तत्वों को संतुष्ट प्रकार के बाद pred अपने मूल स्थान में स्थिर रहते जाएगा (यानी इस तरह से अप्रभावित)।

मैंने इसे फिट करने के लिए त्वरित क्रम को अनुकूलित करने की कोशिश की, लेकिन इसके बारे में सोच नहीं सका। अंत में, मैं कच्चे चयन तरह अनुकूल करने के लिए काम करवाने का फैसला किया:

#include <iostream> 
#include <vector> 

std::vector<int> numbers = {5,7,1,8,9,3,20,2,11}; 

template <typename Container, typename Comparator, typename Predicate> 
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) { // O(n^2), but want O(nlogn) on average (like quick sort or merge sort) 
    const std::size_t N = c.size(); 
    std::size_t i, j, minIndex; 
    for (i = 0; i < N-1; i++) { 
     if (pred(c[i])) 
      continue; // c[i] shall not swap with any element. 
     minIndex = i; 
     for (j = i + 1; j < N; j++) { 
      if (pred(c[j])) 
       continue; // c[j] shall not swap with any element. 
      if (comp(c[j], c[minIndex])) 
       minIndex = j; 
     } 
     if (minIndex != i) 
      std::swap(c[i], c[minIndex]); 
    } 
} 

int main() { 
    sortButKeepSomeFixed (numbers, 
     std::greater<int>(), // Ordering condition. 
     [](int x) {return x % 2 == 0;}); // Those that shall remain fixed. 
    for (int x : numbers) std::cout << x << ' '; // 11 9 7 8 5 3 20 2 1 
} 

लेकिन समय जटिलता हे (एन^2) (मुझे लगता है कि) है। क्या कोई औसत समय पर शायद ओ (एनएलओएनएन) पर जटिलता में सुधार कर सकता है? दूसरे शब्दों में, रिकर्सन या ऐसा कुछ उपयोग करके, एक समग्र बेहतर एल्गोरिदम खोजें?

या शायद pred को संतुष्ट करने वाले तत्वों को निकालने का एक बेहतर विचार है, std::sort के साथ क्या छोड़ा गया है और फिर निकाले गए तत्वों को अपनी मूल स्थिति में वापस रखें? क्या यह और अधिक कुशल होगा, या यह सिर्फ इसे और खराब कर देगा?

अद्यतन: यह बीटा के सुझाव पर आधारित है (pred पास नहीं करने वाले इटरेटर्स को सॉर्ट करना)। लेकिन हालांकि pred पास करने वाले तत्व वास्तव में तय रहते हैं, अंत में सॉर्टिंग सही नहीं है।

template <typename Container, typename Comparator, typename Predicate> 
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) { 
    std::vector<typename Container::iterator> iterators; 
    for (typename Container::iterator it = c.begin(); it != c.end(); ++it) { 
     if (!pred(*it)) 
      iterators.emplace_back(it); 
    } 
    std::vector<typename Container::iterator> originalIterators = iterators; 
    std::sort(iterators.begin(), iterators.end(), 
     [comp](const typename Container::iterator& x, const typename Container::iterator& y) 
     {return comp(*x, *y);}); 
    for (int i = 0; i < originalIterators.size(); i++) 
     *originalIterators[i] = *iterators[i]; 
} 

गलत उत्पादन 11 9 9 8 11 3 20 2 9 है जब यह 11 9 7 8 5 3 20 2 1 होना चाहिए।

Answer 1

बीटा के विचारों के आधार पर इटरेटर का उपयोग करने के लिए सॉर्ट करने के आधार पर, हालांकि मुझे यकीन नहीं है कि समय-जटिलता क्या है। यह सभी कंटेनरों के साथ भी काम नहीं करता है, उदा। std :: set, std :: map।

template <typename Container, typename Comparator, typename Predicate> 
void sortButKeepSomeFixed (Container& c, const Comparator& comp, const Predicate& pred) { 
    std::vector<typename Container::value_type> toSort; 
    std::vector<typename Container::iterator> iterators; 
    for (typename Container::iterator it = c.begin(); it != c.end(); ++it) { 
     if (!pred(*it)) { 
      toSort.emplace_back(*it); 
      iterators.emplace_back(it); 
     } 
    } 
    std::sort(toSort.begin(), toSort.end(), comp); 
    for (std::size_t i = 0; i < toSort.size(); i++) 
     *iterators[i] = toSort[i]; 
} 

std::vector<int> vector = {5,7,1,8,9,3,20,2,11}; 
std::array<int, 9> array = {5,7,1,8,9,3,20,2,11}; 
std::list<int> list  = {5,7,1,8,9,3,20,2,11}; 
std::set<int> set   = {5,7,1,8,9,3,20,2,11}; 
std::map<double, int> map = { {1.5,5}, {1.2,7}, {3.5,1}, {0.5,8}, {5.2,9}, {7.5,3}, {0.1,20}, {1.8,2}, {2.4,11} }; 

template <typename Container> 
void test (Container& container) { 
    sortButKeepSomeFixed (container, 
     std::greater<int>(), // Ordering condition. 
     [](int x) {return x % 2 == 0;}); // Those that shall remain fixed. 
    for (int x : container) std::cout << x << ' '; 
    std::cout << '\n'; 
} 

int main() { 
    test(vector); // 11 9 7 8 5 3 20 2 1 
    test(array); // 11 9 7 8 5 3 20 2 1 
    test(list); // 11 9 7 8 5 3 20 2 1 
    test(set); // Does not compile. 
    sortButKeepSomeFixed (map, 
     [](const std::pair<double, int>& x, const std::pair<double, int>& y) {return x.second > y.second;}, 
     [](const std::pair<double, int>& x) {return x.second % 2 == 0;}); 
    for (const std::pair<double, int>& x : map) 
     std::cout << "(" << x.first << "," << x.second << ") "; // Does not compile. 
} 

सेट और मानचित्र के लिए त्रुटि "केवल-पढ़ने के स्थान का असाइनमेंट" है। कोई भी जानता है कि सेट और मानचित्र के साथ काम करने के लिए इसे कैसे सामान्यीकृत किया जाए?

अपडेट: तो मैं सेट, मैप्स इत्यादि के लिए सुझाव देता हूं ..., बस उन तत्वों को हटा दें जो pred को संतुष्ट करते हैं और Compare के साथ एक नया सेट/मानचित्र/... बनाते हैं, उनके key_compare प्रकार के रूप में। नीचे की तरह लेकिन यह केवल सेट के लिए है। इसे अन्य कंटेनरों में सामान्यीकृत कैसे करें जिनके पास key_compare प्रकार हैं?

template <typename Container, typename Comparator, typename Predicate> 
std::set<typename Container::value_type, Comparator, typename Container::allocator_type> 
     sortButRemoveSomeElements (Container& c, const Comparator&, const Predicate& pred) { 
    std::set<typename Container::value_type, Comparator, typename Container::allocator_type> set; 
    std::vector<typename Container::value_type> keep; 
    for (typename Container::iterator it = c.begin(); it != c.end(); ++it) { 
     if (!pred(*it)) 
      keep.emplace_back(*it); 
    } 
    for (typename Container::value_type x : keep) 
     set.emplace(x); // Sorted by Comparator automatically due to std::set's insertion property. 
    return set; 
} 

परीक्षण:

struct GreaterThan { bool operator()(int x, int y) const {return x > y;} }; 
std::set<int, GreaterThan> newSet = sortButRemoveSomeElements (set, 
    GreaterThan{}, // Ordering condition. 
    [](int x) {return x % 2 == 0;}); // Those that shall be removed. 
for (int x : newSet) std::cout << x << ' '; // 11 9 7 5 3 1 

Answer 2

एक मजेदार एक है यही कारण है कि। मैंने पहली बार custom iterator का उपयोग करके आईएमओ सही दृष्टिकोण को कोड करने का प्रयास किया जो कि भविष्य को संतुष्ट करने वाले तत्वों को छोड़ देता है। यह काफी चुनौतीपूर्ण साबित हुआ, कम से कम एक मोबाइल फोन पर लिख रहा है क्योंकि मैं इसे कर रहा हूं।

असल में, यह एरिक निबेलर के ranges v3 में जो कुछ भी मिल सकता है उसके समान कोड का कारण बनना चाहिए।

लेकिन ऊपर का उपयोग करने का प्रयास करने वाला सरल, सीधा दृष्टिकोण भी है। आपके गैर-कामकाजी समाधान की समस्या यह है कि यह उस अंतिम for लूप में असाइन करते समय मानकों को इंगित करता है (शेष क्रमबद्ध) इटरेटर इंगित करते हैं।यह समस्या मेरी कोड में की तरह एक प्रति, होने से बचा जा सकता है:

int main(int, char **) { 
vector<int> input {1,2,3,4,5,6,7,8,9}; 
vector<reference_wrapper<int>> filtered{begin(input), end(input)}; 
filtered.erase(remove_if(begin(filtered), end(filtered), 
     [](auto e) {return e%2==0;}), end(filtered)); 
vector<int> sorted{begin(filtered), end(filtered)}; 
// change that to contain reference wrappers to see the issue 
sort(begin(sorted), end(sorted), 
     greater<int>{}); 
transform(begin(filtered), end(filtered), 
    begin(sorted), 
    begin(filtered), 
    [](auto to, auto from) { 
     to.get() = from; return to;}); 
copy(begin(input), end(input), 
     ostream_iterator<int>{cout, ", "}); 
return 0; 
} 

Live example here., संशोधित करने से पहले कांटा करने के लिए खेद भूल।

(कि ढेर आवंटित डेटा move उपयोग कर रहे हैं प्रकार के लिए पिछले पर प्रतियां उपयोग करने के बजाय शायद इस्तेमाल किया जाना चाहिए। हालांकि मुझे यकीन है कि क्या आप एक वस्तु से ले जाया करने के लिए प्रदान कर सकते हैं नहीं कर रहा हूँ।)

का उपयोग करना

template <class T> 
class copyable_ref { 
public: 
    copyable_ref(T& ref) noexcept 
    : _ptr(std::addressof(ref)), _copied(false) {} 
    copyable_ref(T&&) = delete; 
    copyable_ref(const copyable_ref& x) noexcept 
    : _ptr (new int(*x._ptr)), _copied (true) { 
    } 
    ~copyable_ref() { 
    if (_copied) { 
     delete _ptr; 
    } 
    } 
    copyable_ref& operator=(const copyable_ref& x) noexcept { 
    *_ptr = *x._ptr; 
    } 
    operator T&() const noexcept { return *_ptr; } 
    T& get() const noexcept { return *_ptr; } 
private: 
    T* _ptr; 
    bool _copied; 
}; 

निर्माण करने पर इस वर्ग के भंडार के लिए सूचक: एक ... बल्कि अजीब ... std::reference_wrapper के बजाय आवरण वर्ग यह possible to achieve the filtered sorting without मान प्रकार के तत्वों के साथ एक सदिश का उपयोग किए (नकल या ले जाया गया) बनाता है मैं टी का तर्क, जिसे प्रतिलिपि असाइनमेंट ऑपरेटर का उपयोग करने पर भी संशोधित किया जाता है। लेकिन जब एक उदाहरण प्रतिलिपि बनाई जाती है, तो संदर्भित (अन्य द्वारा) मान की एक आवंटित प्रतिलिपि बनाई जाती है। इस तरह, यह

Value a, b; 
copyable_ref<Value> ref_a{a}, ref_b{b}; 
copyable_ref<Value> temp{ref_a}; 
ref_a = ref_b; 
ref_b = temp; 
// a and b are swapped 

यह जरूरी हो गया था क्योंकि std::sortswap उपयोग करने के लिए प्रतीत नहीं होता है के समान कोड के साथ दो संदर्भित मान स्वैप करने के लिए संभव है, लेकिन इसके बाद के संस्करण एक के लिए कोड बराबर (ADL या std::swap के माध्यम से पाया जाता है)।

अब अजीब रैपर वर्ग के उदाहरणों और वेक्टर को सॉर्ट करने के साथ वेक्टर को भरकर प्रतिलिपि) प्रतिलिपि बनाकर फ़िल्टर किए गए "दृश्य" को सॉर्ट करना संभव है। जैसा कि उदाहरण में आउटपुट दिखा रहा है, वैल्यू टाइप की अधिकतम एक हीप आवंटित प्रतिलिपि है। आवरण के अंदर संकेत के लिए आवश्यक आकार की गिनती नहीं, तो इस वर्ग निरंतर अंतरिक्ष भूमि के ऊपर के साथ छँटाई सक्षम फ़िल्टर किया गया:

vector<int> input {1,2,3,4,5,6,7,8,9}; 

vector<copyable_ref<int>> sorted; 
sorted.reserve(input.size()); 
for (auto & e : input) { 
    if (e % 2 != 0) { 
     sorted.emplace_back(e); 
    } 
} 
sort(begin(sorted), end(sorted), 
     greater<int>{}); 
copy(begin(input), end(input), 
     ostream_iterator<int>{cout, ", "}); 
cout << endl; 
// 9 2 7 4 5 6 3 8 1 

अंत में, जबकि यह काफी अच्छी तरह से काम करता है, मैं शायद उत्पादन कोड में इसके उपयोग नहीं होता। मैं विशेष रूप से हैरान था कि std::sort मेरा खुद का swap कार्यान्वयन का उपयोग नहीं कर रहा था, जिससे इस साहसी प्रतिलिपि निर्माता का नेतृत्व हुआ।

---

आप सेट और नक्शे के लिए काम करने के लिए अपने कोड सामान्यीकरण नहीं कर सकते: उन डिजाइन द्वारा हल कर रहे हैं, और वे उस निश्चित क्रम ठीक ढंग से काम करने की जरूरत है। और अनियंत्रित रूप, अच्छी तरह से, unordered हैं और इस प्रकार एक आदेश बनाए रख सकते हैं। लेकिन आप हमेशा (जब तक आप कंटेनर को संशोधित नहीं करते हैं) अपने डेटा के क्रमबद्ध "दृश्य" प्रदान करने के लिए वेक्टर के अंदर std::reference_wrapper एस का उपयोग कर सकते हैं।