2
当我尝试编译程序我的工作，我得到以下错误：这是一个标准库错误，还是我的？
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正文。
这里是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;
};
看起来像'trie'的一些问题 – Kunal
请尝试创建一个重现错误的最小完整示例。删除与您所问的问题无关的所有内容。这是我们可以可靠诊断问题的唯一方法。 –
你在trie.insert（）中使用了一对吗？我想这是导致问题的原因。发布您的特里代码。 –