Отвечать

Короткий ответ: да и нет.

Общий указатель в C ++ не нарушает оптимизацию хвостового вызова, но усложняет создание такой рекурсивной функции, которую компилятор может преобразовать в цикл.

Подробности

Предотвращение переполнения стека при рекурсивном построении длинного списка

Я вспомнил, что shared_ptr имеет деструктор, а C ++ имеет RAII. Это затрудняет создание оптимизируемого хвостового вызова, как это обсуждалось в Can Tail Оптимизация звонков и RAII сосуществуют? вопрос.

@KennyOstrom предложил использовать обычный указатель для решения этой проблемы.

static const List* insertBulk_(unsigned amount, const List* tail=nullptr) {
    return amount? insertBulk_(amount - 1, new List{tail})
                 : tail;
}

Используется следующий конструктор

List(const List* tail): tail{tail} {}

Когда tail из List является экземпляром shared_ptr, хвостовой вызов успешно оптимизирован.

Предотвращение переполнения стека при разрушении

Требуется индивидуальная стратегия уничтожения. К счастью, shared_ptr позволяет нам установить его, поэтому я спрятал деструктор List, сделав его private, и использую его для уничтожения списка.

static void destroy(const List* list) {
    if (!list) return;

    shared_ptr<const List> tail = list->tail;
    delete list;
    for (; tail && tail.use_count() == 1; tail = tail->tail);
}

Конструктор должен передать эту функцию разрушения в tail список инициализации

List(const List* tail): tail{tail, List::destroy} {}

Как избежать утечки памяти

В случае исключений у меня не будет должной очистки, поэтому проблема еще не решена. Я хочу использовать shared_ptr, потому что это безопасно, но теперь я не использую его для заголовка текущего списка до конца построения.

Необходимо следить за «голым» указателем до тех пор, пока он не превратится в общий указатель, и освободить его в случае крайней необходимости. Давайте передадим ссылку на указатель хвоста вместо самого указателя на insertBulk_. Это позволит видеть последний хороший указатель за пределами функции.

static const List* insertBulk_(unsigned amount, const List*& tail) {
    if (!amount) {
        const List* result = tail;
        tail = nullptr;
        return result;
    }
    return insertBulk_(amount - 1, tail = new List{tail});
}

Тогда нужен аналог Finally, чтобы автоматизировать уничтожение указателя, который в случае исключения даст утечку.

static const shared_ptr<const List> insertBulk(unsigned amount) {
    struct TailGuard {
        const List* ptr;
        ~TailGuard() {
            List::destroy(this->ptr);
        }
    } guard{};
    const List* result = insertBulk_(amount, guard.ptr);
    return amount? shared_ptr<const List>{result, List::destroy}
                 : nullptr;
}

Решение

Теперь, думаю, проблема решена:

• g++ и clang++ успешно оптимизируют рекурсивное создание длинных списков;
• списки по-прежнему используют shared_ptr;
• обычные указатели кажутся в безопасности.

Исходный код

Окончательный код

#include <memory>
#include <cassert>

using std::shared_ptr;

class List {
    private:
        const shared_ptr<const List> tail;

        /**
         * I need a `tail` to be an instance of `shared_ptr`.
         * Separate `List` constructor was created for this purpose.
         * It gets a regular pointer to `tail` and wraps it
         * into shared pointer.
         *
         * The `tail` is a reference to pointer,
         * because `insertBulk`, which called `insertBulk_`,
         * should have an ability to free memory
         * in the case of `insertBulk_` fail
         * to avoid memory leak.
         */
        static const List* insertBulk_(unsigned amount, const List*& tail) {
            if (!amount) {
                const List* result = tail;
                tail = nullptr;
                return result;
            }
            return insertBulk_(amount - 1, tail = new List{tail});
        }
        unsigned size_(unsigned acc=1) const {
            return this->tail? this->tail->size_(acc + 1) : acc;
        }
        /**
         * Destructor needs to be hidden,
         * because it causes stack overflow for long lists.
         * Custom destruction method `destroy` should be invoked first.
         */
        ~List() {}
    public:
        /**
         * List needs custom destruction strategy,
         * because default destructor causes stack overflow
         * in the case of long lists:
         * it will recursively remove its items.
         */
        List(const List* tail): tail{tail, List::destroy} {}
        List(const shared_ptr<const List>& tail): tail{tail} {}
        List(const List&) = delete;
        List() = delete;

        unsigned size() const {
            return this->size_();
        }

        /**
         * Public iterface for private `insertBulk_` method.
         * It wraps `insertBulk_` result into `shared_ptr`
         * with custom destruction function.
         *
         * Also it creates a guard for tail,
         * which will destroy it if something will go wrong.
         * `insertBulk_` should store `tail`,
         * which is not yet wrapped into `shared_ptr`,
         * in the guard, and set it to `nullptr` in the end
         * in order to avoid destruction of successfully created list.
         */
        static const shared_ptr<const List> insertBulk(unsigned amount) {
            struct TailGuard {
                const List* ptr;
                ~TailGuard() {
                    List::destroy(this->ptr);
                }
            } guard{};
            const List* result = insertBulk_(amount, guard.ptr);
            return amount? shared_ptr<const List>{result, List::destroy}
                         : nullptr;
        }
        /**
         * Custom destruction strategy,
         * which should be called in order to delete a list.
         */
        static void destroy(const List* list) {
            if (!list) return;

            shared_ptr<const List> tail = list->tail;
            delete list;

            /**
             * Watching references count allows us to stop,
             * when we reached the node,
             * which is used by another list.
             *
             * Also this prevents long loop of construction and destruction,
             * because destruction calls this function `destroy` again
             * and it will create a lot of redundant entities
             * without `tail.use_count() == 1` condition.
             */
            for (; tail && tail.use_count() == 1; tail = tail->tail);
        }
};

int main() {
    /**
     * Check whether we can create multiple lists.
     */
    const shared_ptr<const List> list{List::insertBulk(1E6)};
    const shared_ptr<const List> longList{List::insertBulk(1E7)};
    /**
     * Check whether we can use a list as a tail for another list.
     */
    const shared_ptr<const List> composedList{new List{list}, List::destroy};
    /**
     * Checking whether creation works well.
     */
    assert(list->size() == 1E6);
    assert(longList->size() == 1E7);
    assert(composedList->size() == 1E6 + 1);
    return 0;
}

Укороченная версия исходного кода

Класс List без комментариев и проверок в функции main

#include <memory>

using std::shared_ptr;

class List {
    private:
        const shared_ptr<const List> tail;

        static const List* insertBulk_(unsigned amount, const List*& tail) {
            if (!amount) {
                const List* result = tail;
                tail = nullptr;
                return result;
            }
            return insertBulk_(amount - 1, tail = new List{tail});
        }
        ~List() {}
    public:
        List(const List* tail): tail{tail, List::destroy} {}
        List(const shared_ptr<const List>& tail): tail{tail} {}
        List(const List&) = delete;
        List() = delete;

        static const shared_ptr<const List> insertBulk(unsigned amount) {
            struct TailGuard {
                const List* ptr;
                ~TailGuard() {
                    List::destroy(this->ptr);
                }
            } guard{};
            const List* result = insertBulk_(amount, guard.ptr);
            return amount? shared_ptr<const List>{result, List::destroy}
                         : nullptr;
        }
        static void destroy(const List* list) {
            if (!list) return;

            shared_ptr<const List> tail = list->tail;
            delete list;

            for (; tail && tail.use_count() == 1; tail = tail->tail);
        }
};