Mercurial > code
changeset 291:f4fc723429fe
TreeNode: improve performances by taking the value to the stack instead of a second unique_ptr
author | David Demelier <markand@malikania.fr> |
---|---|
date | Thu, 13 Nov 2014 13:21:53 +0100 |
parents | 7433ebe6a8b0 |
children | 30a969b658c1 9b3270513f40 |
files | C++/TreeNode.h |
diffstat | 1 files changed, 47 insertions(+), 30 deletions(-) [+] |
line wrap: on
line diff
--- a/C++/TreeNode.h Thu Nov 13 13:08:49 2014 +0100 +++ b/C++/TreeNode.h Thu Nov 13 13:21:53 2014 +0100 @@ -52,14 +52,17 @@ template <typename U> class HasEqualsTo { public: + using Yes = char [2]; + using No = char [1]; + static_assert(sizeof (char) != sizeof (long), "buy a new compiler"); template <typename Value> - static constexpr auto check(Value *u) -> decltype(*u == *u, char(0)); + static constexpr Yes &check(Value *u, decltype(*u == *u) * = nullptr); - static constexpr long check(...); + static constexpr No &check(...); - static constexpr const bool value = sizeof (check((U *)0)) == sizeof (char); + static constexpr const bool value = sizeof (check((U *)0)) == sizeof (Yes); }; public: @@ -78,39 +81,53 @@ template <typename T> class TreeNode { private: - struct Object { - std::unique_ptr<T> value; - + class Object { + public: + virtual T &get() = 0; virtual std::unique_ptr<Object> clone() const = 0; }; - template <typename U> + template <typename Value> struct Proxy final : public Object { - inline Proxy(U &&u) + private: + Value m_value; + + Proxy(const Proxy &) = delete; + Proxy &operator=(const Proxy &) = delete; + Proxy(Proxy &&) = delete; + Proxy &operator=(Proxy &&) = delete; + + public: + inline Proxy(Value &&value) + : m_value(std::move(value)) { - this->value = std::make_unique<U>(std::move(u)); } - inline Proxy(const U &u) + inline Proxy(const Value &value) + : m_value(value) { - this->value = std::make_unique<U>(u); } template <typename... Args> inline Proxy(Args&&... args) + : m_value(std::forward<Args>(args)...) { - this->value = std::make_unique<U>(std::forward<Args>(args)...); + } + + T &get() override + { + return m_value; } std::unique_ptr<Object> clone() const override { - return std::make_unique<Proxy<U>>(static_cast<const U &>(*this->value)); + return std::make_unique<Proxy<Value>>(m_value); } }; using Container = std::deque<std::unique_ptr<Object>>; - TreeNode *m_parent { nullptr }; + TreeNode *m_parent{nullptr}; Container m_children; public: @@ -134,7 +151,7 @@ { for (const auto &c : other.m_children) { m_children.push_back(c->clone()); - m_children.back()->value->m_parent = this; + m_children.back()->get().m_parent = this; } } @@ -149,7 +166,7 @@ { // Update children to update to *this for (auto &c : m_children) - c->value->m_parent = this; + c->get().m_parent = this; other.m_children.clear(); } @@ -165,7 +182,7 @@ for (const auto &c : other.m_children) { m_children.push_back(c->clone()); - m_children.back()->value->m_parent = this; + m_children.back()->get().m_parent = this; } return *this; @@ -182,7 +199,7 @@ // Update children to update to *this for (auto &c : m_children) - c->value->m_parent = this; + c->get().m_parent = this; other.m_children.clear(); @@ -198,7 +215,7 @@ inline void push(const Value &child) { m_children.push_front(std::make_unique<Proxy<Value>>(child)); - m_children.front()->value->m_parent = this; + m_children.front()->get().m_parent = this; } /** @@ -212,7 +229,7 @@ using Type = typename std::decay<Value>::type; m_children.push_front(std::make_unique<Proxy<Type>>(std::move(child))); - m_children.front()->value->m_parent = this; + m_children.front()->get().m_parent = this; } /** @@ -224,7 +241,7 @@ void pushNew(Args&&... args) { m_children.emplace_front(std::make_unique<Proxy<T>>(std::forward<Args>(args)...)); - m_children.front()->value->m_parent = this; + m_children.front()->get().m_parent = this; } /** @@ -236,7 +253,7 @@ inline void append(const Value &child) { m_children.push_back(std::make_unique<Proxy<Value>>(child)); - m_children.back()->value->m_parent = this; + m_children.back()->get().m_parent = this; } /** @@ -250,7 +267,7 @@ using Type = typename std::decay<Value>::type; m_children.push_back(std::make_unique<Proxy<Type>>(std::move(child))); - m_children.back()->value->m_parent = this; + m_children.back()->get().m_parent = this; } /** @@ -262,7 +279,7 @@ void appendNew(Args&&... args) { m_children.emplace_back(std::make_unique<Proxy<T>>(std::forward<Args>(args)...)); - m_children.back()->value->m_parent = this; + m_children.back()->get().m_parent = this; } /** @@ -347,7 +364,7 @@ void remove(T &value) { m_children.erase(std::remove_if(m_children.begin(), m_children.end(), [&] (auto &p) { - return p->value.get() == &value; + return &p->get() == &value; }), m_children.end()); } @@ -361,7 +378,7 @@ void removeSame(const Value &value, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr) { m_children.erase(std::remove_if(m_children.begin(), m_children.end(), [&] (auto &p) { - return *p->value == value; + return p->get() == value; }), m_children.end()); } @@ -383,7 +400,7 @@ int indexOf(const T &child) const noexcept { for (unsigned i = 0; i < m_children.size(); ++i) - if (m_children[i]->value.get() == &child) + if (&m_children[i]->get() == &child) return i; return -1; @@ -400,7 +417,7 @@ int indexOfSame(const Value &value, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr) const noexcept { for (unsigned i = 0; i < m_children.size(); ++i) - if (*m_children[i]->value == value) + if (m_children[i]->get() == value) return i; return -1; @@ -415,7 +432,7 @@ */ T &operator[](int index) { - return static_cast<T &>(*m_children.at(index)->value); + return static_cast<T &>(m_children.at(index)->get()); } /** @@ -427,7 +444,7 @@ */ const T &operator[](int index) const { - return static_cast<const T &>(*m_children.at(index)->value); + return static_cast<const T &>(m_children.at(index)->get()); } };