c++ - 这是标准库错误还是我的错误？

Question

当我尝试编译我正在处理的程序时，出现以下错误:

In file included from /usr/include/c++/4.8.1/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/4.8.1/bits/char_traits.h:39,
                 from /usr/include/c++/4.8.1/string:40,
                 from main.cpp:1:
/usr/include/c++/4.8.1/bits/stl_pair.h: In instantiation of ‘struct std::pair<trie<std::basic_string<char> >::iterator, bool>’:
main.cpp:7:15:   required from here
/usr/include/c++/4.8.1/bits/stl_pair.h:127:17: error: ‘constexpr std::pair<_T1, _T2>::pair(const std::pair<_T1, _T2>&) [with _T1 = trie<std::basic_string<char> >::iterator; _T2 = bool]’ declared to take const reference, but implicit declaration would take non-const
       constexpr pair(const pair&) = default;
                 ^

如果我正确地读取了错误，这听起来像是标准库的问题，尽管我的钱仍然是我的错......

如果重要的话，这里是 main.cpp (trie.h 是我正在处理的一个类):

#include <string>
#include "trie.h"

int main()
{
    trie<std::string> t;
    t.insert("te");
    trie<std::string> u(std::move(t));

    for(auto i: u)
        ;
}

---

编辑:这是相关的特里代码。 trie.h :

template<typename T>
class trie {
public:
    // misc. declarations
    class iterator;
    typedef T key_type;
    typedef T value_type;
    typedef size_t size_type;
    typedef iterator const_iterator;

    // constructors
    trie(trie<T>* const = nullptr, bool = false);
    trie(const trie<T>&, trie<T>* const = nullptr);
    trie(trie<T>&&);
    template<typename InputIt> trie(InputIt, InputIt, trie<T>* const = nullptr);

    // destructor, auto-generated one is fine
    ~trie() =default;

    // ...

    // other members
    std::pair<iterator,bool> insert(const value_type&);

    // ...

private:
    std::map<typename T::value_type, std::unique_ptr<trie<T>>> children;
    trie<T>* parent;
    bool is_leaf = false;
};

#include "trie_iterator.h"

// ...

template<typename T>
std::pair<typename trie<T>::iterator,bool> trie<T>::insert(const value_type& value)
{
  bool inserted = false;
  bool at_leaf = false;
  std::stack<typename iterator::state> parents;
  trie<T>* currentNode{this};

  for(const auto& it = value.begin(); it != value.end(); ++it) {
    bool is_last = (it + 1 == value.end());
    auto childIt = currentNode->children.find(*it);
    if(childIt == currentNode->children.end()) {
      inserted = true;
      if(is_last) {
        // The sequence is new to this trie, so insert it.
        // It is the last element, so don't create a new trie.
        parents.emplace(
          currentNode,
          currentNode->children.emplace({*it, {nullptr}}).first
        );
      }
      else {
        // Create a new trie and follow it.
        std::unique_ptr<trie<T>> p(new trie<T>(currentNode));
        currentNode = currentNode->children.emplace(*it, std::move(p)).first->second;
      }
    }
    else {
      if(is_last) {
        if(childIt->second != nullptr) {
          inserted = true;
          at_leaf = true;
          childIt->second->is_leaf = true;
        }
        // Done.  Build a return value.
        // TODO
      }
      else {
        if(childIt->second == nullptr) {
          childIt->second = new trie<T>(currentNode);
          inserted = true;
        }
        currentNode = childIt->second;
      }
    }
  }
  // Build pair and return it
  return {{std::move(parents), value, at_leaf}, inserted};
}

对于这段代码的长度，我深表歉意；请注意实现insert没关系；无论如何，错误都会出现，包括空 insert body 。

这是 trie<T>::iterator类:

template<typename T>
class trie<T>::iterator {
    friend class trie<T>;
    // TODO: Either this structure or trie::parent is not needed
    struct state {
        state(const trie<T>* const node, const typename std::map<typename T::value_type, std::unique_ptr<trie<T>>>::const_iterator& node_map_it ) :
            node{node}, node_map_it{node_map_it} {}
        bool operator==(const state& other) const {
            return node == other.node && node_map_it == other.node_map_it;
        }
        const trie<T>* node;
        typename std::map<typename T::value_type, std::unique_ptr<trie<T>>>::const_iterator node_map_it;
    };
    enum class fall_to {left, right};
public:
    iterator() =default;
    iterator(trie<T>* node) {
        parents.emplace(node, node->children.cbegin());
        at_end = (parents.top().node_map_it == parents.top().node->children.cend());
        at_leaf = parents.top().node->is_leaf;
        fall_down();
    }
    ~iterator() =default;
    iterator(typename trie<T>::iterator& other) =default;
    iterator(typename trie<T>::iterator&& other) :
        parents{std::move(other.parents)},
        built{std::move(other.built)}
    {}
    iterator& operator=(typename trie<T>::iterator other) {
        swap(*this, other);
        return *this;
    }

    void swap(typename trie<T>::iterator& other) {
        std::swap(parents, other.parents);
        std::swap(built, other.built);
    }
    static void swap(typename trie<T>::iterator& a, typename trie<T>::iterator& b) { a.swap(b); }

    const T& operator*() const { return built; }
    const T* operator->() const { return &built; }

    void operator++() {
        if(at_leaf)
            at_leaf = false;
        else
            while(++parents.top().node_map_it == parents.top().node->children.cend())
                walk_up();
        fall_down();
    }
    void operator--() {
        if(at_leaf)
            walk_up();
        while(parents.top().node_map_it-- == parents.top().node->children.cbegin()) {
            at_leaf = parents.top().node->is_leaf;
            if(at_leaf)
                // No need to fall down.
                return;
            walk_up();
        }
        fall_down(fall_to::right);
    }

    bool operator==(const typename trie<T>::iterator& other) const {
        return parents.top() == other.parents.top() && at_end == other.at_end;
    }
    bool operator!=(const typename trie<T>::iterator& other) const { return !operator==(other); }
private:
    iterator(const std::stack<state>& parents, const T& built, bool at_end) :
        parents{parents}, built{built}, at_end{at_end} {}
    void inline fall_down(const enum fall_to fall = fall_to::left) {
        // TODO: This function could possibly be made smaller.
        trie<T>* child;
        if(at_leaf)
            return;
        while((child = parents.top().node_map_it->second.get()) != nullptr) {
            built.push_back(parents.top().node_map_it->first);
            if(fall == fall_to::left) {
                parents.emplace(child, child->children.cbegin());
                at_leaf = child->is_leaf;
                if(at_leaf)
                    return;
            }
            else // fall_to::right
                parents.emplace(child, --child->children.cend());
        }
        // One final push_back to put the final element (the one that has no
        // children) in built.
        built.push_back(parents.top().node_map_it->first);
    }
    void inline walk_up() {
        built.pop_back();
        parents.pop();
    }

    std::stack<state> parents;
    // TODO: we could switch the use of push_back and pop_back for insert and erase
    // using an end iterator, to gain some additional compatibility.
    T built;
    bool at_end;
    bool at_leaf;
};

Answer 1

该错误告诉您:

/usr/include/c++/4.8.1/bits/stl_pair.h:127:17: error: ‘constexpr std::pair<_T1, _T2>::pair(const std::pair<_T1, _T2>&) [with _T1 = trie<std::basic_string<char> >::iterator; _T2 = bool]’ declared to take const reference, but implicit declaration would take non-const
   constexpr pair(const pair&) = default;

换句话说，为pair生成的隐式复制构造函数将具有签名pair(pair&)而不是pair(constpair&)。根据cppreference

Implicitly-declared copy constructor

If no user-defined copy constructors are provided for a class type (struct, class, or union), the compiler will always declare a copy constructor as an inline public member of its class. This implicitly-declared copy constructor has the form T::T(const T&) if all of the following is true:

• all direct and virtual bases of T have copy constructors with references to const or to - const volatile as their first parameters
• all non-static members of T have copy constructors with references to const or to const volatile as their first parameters

Otherwise, the implicitly-declared copy constructor is T::T(T&). (Note that due to these rules, the implicitly-declared copy constructor cannot bind to a volatile lvalue argument)

很可能您的迭代器没有使用 iterator(const iterator&) 声明其复制构造函数。