Mercurial > code

changeset 291:f4fc723429fe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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());
 	}
 };