For fun: AC C++ custom iterator + std::stable_partition


  • 0
    M

    C++ algorithms such as std::stable_partition allow user-defined iterators, so I thought to give it a try.
    Edit: I see now that this is incorrect code, even though it's accepted by LC. The problem is that stable_partition, unlike std::partition, doesn't formally support forward iterators.

        struct myiter
            : public std::iterator<std::forward_iterator_tag, int>
        {
            myiter(ListNode* node = nullptr) : node(node) {}
    
            int& operator->() { return node->val; }
            int& operator*() { return node->val; }
    
            const int operator->() const { return node->val; }
            const int operator*() const { return node->val; }
          
            myiter& operator++() { node = node->next; return *this; }
            myiter  operator++(int) { auto copy = *this; node = node->next; return copy; }
    
            ListNode* node;
        };
    
        bool operator==(myiter lhs, myiter rhs) { return lhs.node == rhs.node; }
        bool operator!=(myiter lhs, myiter rhs) { return !(lhs == rhs); }
    
        class Solution {
        public:
            ListNode* partition(ListNode* head, int x) {
                std::stable_partition(
                    myiter(head), myiter(nullptr),
                    [&](int val) { return val < x; });
    
                return head;
            }
        };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.