如何编写更简洁高效的按字典序添加元素的Link类add_ordered_函数？

Hey there! Great job getting your add_ordered_ function working after debugging—tackling exercises from Programming: Principles and Practice Using C++ is always a solid way to build your fundamentals. Let's break down a cleaner, more efficient implementation for your ordered insertion function, plus some tweaks to make it even more flexible.

First, let's recap your Link structure to set the context:

template<typename T>
struct Link {
    T val;
    Link* prev;
    Link* succ;
    Link(const T& value, Link* p = nullptr, Link* s = nullptr) 
        : val{value}, prev{p}, succ{s} {}
    Link* add_ordered_(Link*);
};

Clean, Efficient Implementation #

The core goal of add_ordered_ is to insert a new node into the doubly linked list in lexicographical (dictionary) order, with minimal redundant checks and optimal traversal. Here's a streamlined version:

template<typename T>
Link<T>* Link<T>::add_ordered_(Link<T>* new_node) {
    if (!new_node) return this; // Guard against null input

    // Case 1: Insert at the head (new node is smaller than all existing nodes)
    if (new_node->val < val) {
        new_node->succ = this;
        prev = new_node;
        return new_node; // Return the new list head
    }

    // Traverse to find the insertion point: first node >= new_node's value
    Link<T>* curr = this;
    while (curr->succ && curr->succ->val < new_node->val) {
        curr = curr->succ;
    }

    // Insert the new node after curr
    new_node->succ = curr->succ;
    if (curr->succ) {
        curr->succ->prev = new_node;
    }
    curr->succ = new_node;
    new_node->prev = curr;

    return this; // Original head remains valid
}

Why This Works Better #

• Optimal Time Complexity: We only traverse the list once to find the insertion point (O(n) time, which is the best possible for a doubly linked list since we can't binary search an unindexed structure).
• Clear Boundary Handling: Explicitly handles inserting at the head (the only case where the list head changes) and gracefully handles inserting in the middle or at the tail without extra checks.
• Concise Pointer Adjustments: The insertion logic avoids redundant pointer assignments and covers all edge cases (like inserting at the end of the list, where curr->succ is nullptr).

Bonus: Make It Flexible #

If you want to support custom sorting (not just lexicographical order), you can abstract the comparison logic using a template parameter. This makes the function reusable for any ordering:

#include <functional> // For std::less

template<typename T>
struct Link {
    T val;
    Link* prev;
    Link* succ;
    Link(const T& value, Link* p = nullptr, Link* s = nullptr) 
        : val{value}, prev{p}, succ{s} {}
    
    // Overload with custom comparator
    template<typename Compare = std::less<T>>
    Link* add_ordered_(Link* new_node, Compare comp = Compare{});
};

template<typename T>
template<typename Compare>
Link<T>* Link<T>::add_ordered_(Link<T>* new_node, Compare comp) {
    if (!new_node) return this;

    if (comp(new_node->val, val)) {
        new_node->succ = this;
        prev = new_node;
        return new_node;
    }

    Link<T>* curr = this;
    while (curr->succ && comp(curr->succ->val, new_node->val)) {
        curr = curr->succ;
    }

    new_node->succ = curr->succ;
    if (curr->succ) {
        curr->succ->prev = new_node;
    }
    curr->succ = new_node;
    new_node->prev = curr;

    return this;
}

Now you can use it for lexicographical order (default) or reverse order like this:

// Reverse order insertion
link->add_ordered_(new_node, std::greater<std::string>());

内容的提问来源于stack exchange，提问作者TosinAl