std::forward_list emplace_after O(1) 怎么样？

Question

我目前正在实施转发列表（单链表）。我注意到 std::forward_list::emplace_after 是 O(1)，所以复杂度是常数：这怎么可能？我问是因为：

你可以让新元素的位置在中间，
据我所知，要找到必须添加新元素的位置的唯一方法是循环遍历列表。

我错过了什么吗？这就是我目前实现该功能的方式。

constexpr void emplace_after(iterator position, Args...args) { // Must be O(1)
    size_type index_position = std::distance(begin(), position);

    Node* temp = m_head;
    for (size_type index{ 0 }; index < index_position; ++index) {
        temp = temp->next;
    }
    Node* next_temp = temp->next;
    Node* current_node = new Node(std::forward<Args>(args)...);
    temp->next = current_node;
    current_node->next = next_temp;

    temp = nullptr;
    next_temp = nullptr;
    m_size += 1;
}

这是我当前的前向迭代器实现：

template<typename T>
struct forward_iterator {
    Node* m_iterator;

    using value_type = T;
    using reference = value_type&;
    using pointer = value_type*;
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;

    constexpr forward_iterator(Node* forw_iter = nullptr) : m_iterator{ forw_iter } {}

    constexpr Node* getNodeAddress() const noexcept {
        return m_iterator;
    }

    constexpr Node* getNodeNextAddress() const noexcept {
        return m_iterator->next;
    }

    constexpr reference operator*() const noexcept {
        return m_iterator->data;
    }

    constexpr pointer operator->() const noexcept {
        return m_iterator;
    }

    constexpr forward_iterator& operator++() noexcept {
        m_iterator = m_iterator->next;
        return *this;
    }

    constexpr forward_iterator operator++(int) noexcept {
        forward_iterator tmp(*this);
        this = (this)->next;
        return tmp;
    }

    constexpr friend bool operator== (const forward_iterator& first, const forward_iterator& second) noexcept {
        return (first.m_iterator == second.m_iterator);
    }

    constexpr friend bool operator!=(const forward_iterator& first, const forward_iterator& second) noexcept {
        return !(first.m_iterator == second.m_iterator);
    }
};

Answer 1

std::forward_list<T,Allocator>::emplace_after的参数是一个迭代器，也就是说你需要先找到位置再放置。因此，它只需要恒定的时间。

Answer 2

迭代器让你在 O(1) 时间内到达它们引用的节点。

如果您的迭代器没有，请修复它。

Answer 3

您似乎对迭代器在单向链表中的工作方式存在误解。它们不仅仅是您可以（并且必须）搜索的标识符，它们应该以某种方式指向实际节点。

插图：

Iterator ------------------+
                           |
                           V 
[Head] -> Node -> Node -> Node -> Node -> Node -> nullptr

这意味着您的 class iterator 应该包含一个 Node *（编辑：因为它已经包含）

那么你的 emplace_back 可以是这样的：

constexpr void emplace_after(iterator position, Args... args)
{   
    Node* temp = position.getNodeAddress(); // retrieve the node position is referring

    Node* next_temp = temp->next;
    Node* current_node = new Node(std::forward<Args>(args)...);
    temp->next = current_node;
    current_node->next = next_temp;

    temp = nullptr;
    next_temp = nullptr;
    m_size += 1;
}

std::forward_list emplace_after O(1) 怎么样？

How is std::forward_list emplace_after O(1)?

c++

linked-list

list

forward-list