summaryrefslogtreecommitdiff
path: root/libcutl/cutl/container
diff options
context:
space:
mode:
Diffstat (limited to 'libcutl/cutl/container')
-rw-r--r--libcutl/cutl/container/any.hxx152
-rw-r--r--libcutl/cutl/container/graph.hxx217
-rw-r--r--libcutl/cutl/container/graph.txx349
-rw-r--r--libcutl/cutl/container/key.hxx71
-rw-r--r--libcutl/cutl/container/map-iterator.hxx69
-rw-r--r--libcutl/cutl/container/multi-index.hxx15
-rw-r--r--libcutl/cutl/container/pointer-iterator.hxx126
7 files changed, 999 insertions, 0 deletions
diff --git a/libcutl/cutl/container/any.hxx b/libcutl/cutl/container/any.hxx
new file mode 100644
index 0000000..5dd1c25
--- /dev/null
+++ b/libcutl/cutl/container/any.hxx
@@ -0,0 +1,152 @@
+// file : cutl/container/any.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+#ifndef CUTL_CONTAINER_ANY_HXX
+#define CUTL_CONTAINER_ANY_HXX
+
+#include <memory> // std::auto_ptr
+#include <typeinfo> // std::type_info
+
+#include <cutl/exception.hxx>
+
+#include <cutl/details/export.hxx>
+
+namespace cutl
+{
+ namespace container
+ {
+ class LIBCUTL_EXPORT any
+ {
+ public:
+ struct LIBCUTL_EXPORT typing: exception {};
+
+ public:
+ any ()
+ {
+ }
+
+ template <typename X>
+ any (X const& x)
+ : holder_ (new holder_impl<X> (x))
+ {
+ }
+
+ any (any const& x)
+ : holder_ (x.holder_->clone ())
+ {
+ }
+
+ template <typename X>
+ any&
+ operator= (X const& x)
+ {
+ holder_.reset (new holder_impl<X> (x));
+ return *this;
+ }
+
+ any&
+ operator= (any const& x)
+ {
+ holder_.reset (x.holder_->clone ());
+ return *this;
+ }
+
+ public:
+ template <typename X>
+ X&
+ value ()
+ {
+ if (holder_impl<X>* p = dynamic_cast<holder_impl<X>*> (holder_.get ()))
+ return p->value ();
+ else
+ throw typing ();
+ }
+
+ template <typename X>
+ X const&
+ value () const
+ {
+ if (holder_impl<X>* p = dynamic_cast<holder_impl<X>*> (holder_.get ()))
+ return p->value ();
+ else
+ throw typing ();
+ }
+
+ std::type_info const&
+ type_info () const
+ {
+ return holder_->type_info ();
+ }
+
+ public:
+ bool
+ empty () const
+ {
+ return holder_.get () == 0;
+ }
+
+ void
+ reset ()
+ {
+ return holder_.reset ();
+ }
+
+ private:
+ class LIBCUTL_EXPORT holder
+ {
+ public:
+ virtual
+ ~holder () {}
+
+ virtual holder*
+ clone () const = 0;
+
+ virtual std::type_info const&
+ type_info () const = 0;
+ };
+
+ template <typename X>
+ class holder_impl: public holder
+ {
+ public:
+ holder_impl (X const& x)
+ : x_ (x)
+ {
+ }
+
+ virtual holder_impl*
+ clone () const
+ {
+ return new holder_impl (x_);
+ }
+
+ virtual std::type_info const&
+ type_info () const
+ {
+ return typeid (x_);
+ }
+
+ X const&
+ value () const
+ {
+ return x_;
+ }
+
+ X&
+ value ()
+ {
+ return x_;
+ }
+
+ private:
+ X x_;
+ };
+
+ private:
+ std::auto_ptr<holder> holder_;
+ };
+ }
+}
+
+#endif // CUTL_CONTAINER_ANY_HXX
diff --git a/libcutl/cutl/container/graph.hxx b/libcutl/cutl/container/graph.hxx
new file mode 100644
index 0000000..9c1afe2
--- /dev/null
+++ b/libcutl/cutl/container/graph.hxx
@@ -0,0 +1,217 @@
+// file : cutl/container/graph.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+#ifndef CUTL_CONTAINER_GRAPH_HXX
+#define CUTL_CONTAINER_GRAPH_HXX
+
+#include <map>
+
+#include <cutl/exception.hxx>
+#include <cutl/shared-ptr.hxx>
+
+#include <cutl/details/export.hxx>
+
+namespace cutl
+{
+ namespace container
+ {
+ struct LIBCUTL_EXPORT no_edge: exception {};
+ struct LIBCUTL_EXPORT no_node: exception {};
+
+ template <typename N, typename E>
+ class graph
+ {
+ public:
+ typedef N node_base;
+ typedef E edge_base;
+
+ public:
+ template <typename T>
+ T&
+ new_node ();
+
+ template <typename T, typename A0>
+ T&
+ new_node (A0 const&);
+
+ template <typename T, typename A0, typename A1>
+ T&
+ new_node (A0 const&, A1 const&);
+
+ template <typename T, typename A0, typename A1, typename A2>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&,
+ A5 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&,
+ A5 const&, A6 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&,
+ A5 const&, A6 const&, A7 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7, typename A8>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&,
+ A5 const&, A6 const&, A7 const&, A8 const&);
+
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7, typename A8, typename A9>
+ T&
+ new_node (A0 const&, A1 const&, A2 const&, A3 const&, A4 const&,
+ A5 const&, A6 const&, A7 const&, A8 const&, A9 const&);
+
+ // Non-const versions.
+ //
+ template <typename T, typename A0>
+ T&
+ new_node (A0&);
+
+ template <typename T, typename A0, typename A1>
+ T&
+ new_node (A0&, A1&);
+
+ template <typename T, typename A0, typename A1, typename A2>
+ T&
+ new_node (A0&, A1&, A2&);
+
+ public:
+ template <typename T, typename L, typename R>
+ T&
+ new_edge (L&, R&);
+
+ template <typename T, typename L, typename R,
+ typename A0>
+ T&
+ new_edge (L&, R&, A0 const&);
+
+ template <typename T, typename L, typename R,
+ typename A0, typename A1>
+ T&
+ new_edge (L&, R&, A0 const&, A1 const&);
+
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2>
+ T&
+ new_edge (L&, R&, A0 const&, A1 const&, A2 const&);
+
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3>
+ T&
+ new_edge (L&, R&, A0 const&, A1 const&, A2 const&, A3 const&);
+
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3,
+ typename A4>
+ T&
+ new_edge (L&, R&, A0 const&, A1 const&, A2 const&, A3 const&,
+ A4 const&);
+
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3,
+ typename A4, typename A5>
+ T&
+ new_edge (L&, R&, A0 const&, A1 const&, A2 const&, A3 const&,
+ A4 const&, A5 const&);
+
+ // Functions to reset edge's nodes.
+ //
+ public:
+ template <typename TE, typename TN>
+ void
+ reset_left_node (TE& edge, TN& node)
+ {
+ edge.set_left_node (node);
+ }
+
+ template <typename TE, typename TN>
+ void
+ reset_right_node (TE& edge, TN& node)
+ {
+ edge.set_right_node (node);
+ }
+
+ // Functions to add edges to a node.
+ //
+ public:
+ template <typename TN, typename TE>
+ void
+ add_edge_left (TN& node, TE& edge)
+ {
+ node.add_edge_left (edge);
+ }
+
+ template <typename TN, typename TE>
+ void
+ add_edge_right (TN& node, TE& edge)
+ {
+ node.add_edge_right (edge);
+ }
+
+ // Functions to delete edges and nodes. In order to delete a
+ // a node without leaving any dangling edges you need to make
+ // sure that each edge pointing to it is either deleted or reset
+ // to some other node.
+ //
+ public:
+ template <typename T, typename L, typename R>
+ void
+ delete_edge (L& left_node, R& right_node, T& edge);
+
+ void
+ delete_node (node_base& node)
+ {
+ if (nodes_.erase (&node) == 0)
+ throw no_node ();
+ }
+
+ public:
+ graph () {}
+
+ private:
+ graph (graph const&);
+
+ graph&
+ operator= (graph const&);
+
+ protected:
+ typedef shared_ptr<node_base> node_ptr;
+ typedef shared_ptr<edge_base> edge_ptr;
+
+ typedef std::map<node_base*, node_ptr> nodes;
+ typedef std::map<edge_base*, edge_ptr> edges;
+
+ nodes nodes_;
+ edges edges_;
+ };
+ }
+}
+
+#include <cutl/container/graph.txx>
+
+#endif // CUTL_CONTAINER_GRAPH_HXX
diff --git a/libcutl/cutl/container/graph.txx b/libcutl/cutl/container/graph.txx
new file mode 100644
index 0000000..bb8fe47
--- /dev/null
+++ b/libcutl/cutl/container/graph.txx
@@ -0,0 +1,349 @@
+// file : cutl/container/graph.txx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+namespace cutl
+{
+ namespace container
+ {
+
+ // Nodes.
+ //
+
+ template <typename N, typename E>
+ template <typename T>
+ T& graph<N, E>::
+ new_node ()
+ {
+ shared_ptr<T> node (new (shared) T);
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename A0>
+ T& graph<N, E>::
+ new_node (A0 const& a0)
+ {
+ shared_ptr<T> node (new (shared) T (a0));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2, a3));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2, a3, a4));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4, A5 const& a5)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2, a3, a4, a5));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4, A5 const& a5, A6 const& a6)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2, a3, a4, a5, a6));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4, A5 const& a5, A6 const& a6, A7 const& a7)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2, a3, a4, a5, a6, a7));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7, typename A8>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4, A5 const& a5, A6 const& a6, A7 const& a7,
+ A8 const& a8)
+ {
+ shared_ptr<T> node (
+ new (shared) T (a0, a1, a2, a3, a4, a5, a6, a7, a8));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2,
+ typename A3, typename A4, typename A5, typename A6,
+ typename A7, typename A8, typename A9>
+ T& graph<N, E>::
+ new_node (A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3,
+ A4 const& a4, A5 const& a5, A6 const& a6, A7 const& a7,
+ A8 const& a8, A9 const& a9)
+ {
+ shared_ptr<T> node (
+ new (shared) T (a0, a1, a2, a3, a4, a5, a6, a7, a8, a9));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ // Non-const versions.
+ //
+ template <typename N, typename E>
+ template <typename T, typename A0>
+ T& graph<N, E>::
+ new_node (A0& a0)
+ {
+ shared_ptr<T> node (new (shared) T (a0));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1>
+ T& graph<N, E>::
+ new_node (A0& a0, A1& a1)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename A0, typename A1, typename A2>
+ T& graph<N, E>::
+ new_node (A0& a0, A1& a1, A2& a2)
+ {
+ shared_ptr<T> node (new (shared) T (a0, a1, a2));
+ nodes_[node.get ()] = node;
+
+ return *node;
+ }
+
+ // Edges.
+ //
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R>
+ T& graph<N, E>::
+ new_edge (L& l, R& r)
+ {
+ shared_ptr<T> edge (new (shared) T);
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0)
+ {
+ shared_ptr<T> edge (new (shared) T (a0));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0, typename A1>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0, A1 const& a1)
+ {
+ shared_ptr<T> edge (new (shared) T (a0, a1));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0, A1 const& a1, A2 const& a2)
+ {
+ shared_ptr<T> edge (new (shared) T (a0, a1, a2));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0, A1 const& a1, A2 const& a2,
+ A3 const& a3)
+ {
+ shared_ptr<T> edge (new (shared) T (a0, a1, a2, a3));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3,
+ typename A4>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0, A1 const& a1, A2 const& a2,
+ A3 const& a3, A4 const& a4)
+ {
+ shared_ptr<T> edge (new (shared) T (a0, a1, a2, a3, a4));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R,
+ typename A0, typename A1, typename A2, typename A3,
+ typename A4, typename A5>
+ T& graph<N, E>::
+ new_edge (L& l, R& r, A0 const& a0, A1 const& a1, A2 const& a2,
+ A3 const& a3, A4 const& a4, A5 const& a5)
+ {
+ shared_ptr<T> edge (new (shared) T (a0, a1, a2, a3, a4, a5));
+ edges_[edge.get ()] = edge;
+
+ edge->set_left_node (l);
+ edge->set_right_node (r);
+
+ l.add_edge_left (*edge);
+ r.add_edge_right (*edge);
+
+ return *edge;
+ }
+
+
+ template <typename N, typename E>
+ template <typename T, typename L, typename R>
+ void graph<N, E>::
+ delete_edge (L& l, R& r, T& edge)
+ {
+ typename edges::iterator i (edges_.find (&edge));
+
+ if (i == edges_.end () ||
+ nodes_.find (&l) == nodes_.end () ||
+ nodes_.find (&r) == nodes_.end ())
+ throw no_edge ();
+
+ r.remove_edge_right (edge);
+ l.remove_edge_left (edge);
+
+ edge.clear_right_node (r);
+ edge.clear_left_node (l);
+
+ edges_.erase (i);
+ }
+ }
+}
diff --git a/libcutl/cutl/container/key.hxx b/libcutl/cutl/container/key.hxx
new file mode 100644
index 0000000..42f0fe5
--- /dev/null
+++ b/libcutl/cutl/container/key.hxx
@@ -0,0 +1,71 @@
+// file : cutl/container/key.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompkeying LICENSE file
+
+#ifndef CUTL_CONTAINER_KEY_HXX
+#define CUTL_CONTAINER_KEY_HXX
+
+namespace cutl
+{
+ namespace container
+ {
+ // A modifiable map key wrapper that can be used to implement multi-
+ // index containers, as discussed in the following post:
+ //
+ // http://www.codesynthesis.com/~boris/blog/2012/09/11/emulating-boost-multi-index-with-std-containers/
+ //
+ template <class T1, class T2 = void, class T3 = void>
+ struct key;
+
+ template <class T1>
+ struct key<T1, void, void>
+ {
+ mutable const T1* p1;
+
+ key (): p1 (0) {}
+ key (const T1& r1): p1 (&r1) {}
+ void assign (const T1& r1) const {p1 = &r1;}
+
+ bool operator< (const key& x) const {return *p1 < *x.p1;}
+ };
+
+ template <class T1, class T2>
+ struct key<T1, T2, void>
+ {
+ mutable const T1* p1;
+ mutable const T2* p2;
+
+ key (): p1 (0), p2 (0) {}
+ key (const T1& r1, const T2& r2): p1 (&r1), p2 (&r2) {}
+ void assign (const T1& r1, const T2& r2) const {p1 = &r1; p2 = &r2;}
+
+ bool operator< (const key& x) const
+ {
+ return *p1 < *x.p1 || (!(*x.p1 < *p1) && *p2 < *x.p2);
+ }
+ };
+
+ template <class T1, class T2, class T3>
+ struct key
+ {
+ mutable const T1* p1;
+ mutable const T2* p2;
+ mutable const T3* p3;
+
+ key (): p1 (0), p2 (0), p3 (0) {}
+ key (const T1& r1, const T2& r2, const T3& r3)
+ : p1 (&r1), p2 (&r2) , p3 (&r3) {}
+ void assign (const T1& r1, const T2& r2, const T3& r3) const
+ {p1 = &r1; p2 = &r2; p3 = &r3;}
+
+ bool operator< (const key& x) const
+ {
+ return (*p1 < *x.p1 ||
+ (!(*x.p1 < *p1) && (*p2 < *x.p2 ||
+ (!(*x.p2 < *p2) && *p3 < *x.p3))));
+ }
+ };
+ }
+}
+
+#endif // CUTL_CONTAINER_KEY_HXX
diff --git a/libcutl/cutl/container/map-iterator.hxx b/libcutl/cutl/container/map-iterator.hxx
new file mode 100644
index 0000000..051ffb5
--- /dev/null
+++ b/libcutl/cutl/container/map-iterator.hxx
@@ -0,0 +1,69 @@
+// file : cutl/container/map-iterator.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+#ifndef CUTL_CONTAINER_MAP_ITERATOR_HXX
+#define CUTL_CONTAINER_MAP_ITERATOR_HXX
+
+namespace cutl
+{
+ namespace container
+ {
+ // Map iterator adapter that can be used to implement multi-index
+ // containers, as discussed in the following post:
+ //
+ // http://www.codesynthesis.com/~boris/blog/2012/09/11/emulating-boost-multi-index-with-std-containers/
+ //
+ template <typename M>
+ struct map_iterator: M::iterator
+ {
+ typedef typename M::iterator base_iterator;
+ typedef typename M::value_type::second_type value_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
+
+ map_iterator () {}
+ map_iterator (base_iterator i): base_iterator (i) {}
+
+ reference
+ operator* () const
+ {
+ return base_iterator::operator* ().second;
+ }
+
+ pointer
+ operator-> () const
+ {
+ return &base_iterator::operator-> ()->second;
+ }
+ };
+
+ template <typename M>
+ struct map_const_iterator: M::const_iterator
+ {
+ typedef typename M::iterator base_iterator;
+ typedef typename M::const_iterator base_const_iterator;
+ typedef const typename M::value_type::second_type value_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
+
+ map_const_iterator () {}
+ map_const_iterator (base_iterator i): base_const_iterator (i) {}
+ map_const_iterator (base_const_iterator i): base_const_iterator (i) {}
+
+ reference
+ operator* () const
+ {
+ return base_const_iterator::operator* ().second;
+ }
+
+ pointer
+ operator-> () const
+ {
+ return &base_const_iterator::operator-> ()->second;
+ }
+ };
+ }
+}
+
+#endif // CUTL_CONTAINER_MAP_ITERATOR_HXX
diff --git a/libcutl/cutl/container/multi-index.hxx b/libcutl/cutl/container/multi-index.hxx
new file mode 100644
index 0000000..5249647
--- /dev/null
+++ b/libcutl/cutl/container/multi-index.hxx
@@ -0,0 +1,15 @@
+// file : cutl/container/multi-index.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+#ifndef CUTL_CONTAINER_MULTI_INDEX_HXX
+#define CUTL_CONTAINER_MULTI_INDEX_HXX
+
+// Multi-index containers support. See the following post for details:
+//
+// http://www.codesynthesis.com/~boris/blog/2012/09/11/emulating-boost-multi-index-with-std-containers/
+//
+#include <cutl/container/key.hxx>
+#include <cutl/container/map-iterator.hxx>
+
+#endif // CUTL_CONTAINER_MULTI_INDEX_HXX
diff --git a/libcutl/cutl/container/pointer-iterator.hxx b/libcutl/cutl/container/pointer-iterator.hxx
new file mode 100644
index 0000000..7059558
--- /dev/null
+++ b/libcutl/cutl/container/pointer-iterator.hxx
@@ -0,0 +1,126 @@
+// file : cutl/container/pointer-iterator.hxx
+// copyright : Copyright (c) 2009-2013 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+#ifndef CUTL_CONTAINER_POINTER_ITERATOR_HXX
+#define CUTL_CONTAINER_POINTER_ITERATOR_HXX
+
+#include <iterator> // std::iterator_traits
+
+#include <cutl/meta/remove-p.hxx>
+
+namespace cutl
+{
+ namespace container
+ {
+ template <typename I>
+ class pointer_iterator
+ {
+ public:
+ typedef
+ typename meta::remove_p<typename std::iterator_traits<I>::value_type>::r
+ value_type;
+
+ typedef
+ typename std::iterator_traits<I>::iterator_category
+ iterator_category;
+
+ typedef
+ typename std::iterator_traits<I>::difference_type
+ difference_type;
+
+ typedef value_type& reference;
+ typedef value_type* pointer;
+ typedef I base_iterator;
+
+ public:
+ pointer_iterator ()
+ : i_ () // I can be of a pointer type.
+ {
+ }
+
+ pointer_iterator (I const& i)
+ : i_ (i)
+ {
+ }
+
+ public:
+ reference
+ operator* () const
+ {
+ return **i_;
+ }
+
+ pointer
+ operator-> () const
+ {
+ return *i_;
+ }
+
+ I const&
+ base () const
+ {
+ return i_;
+ }
+
+ public:
+ // Forward iterator requirements.
+ //
+ pointer_iterator&
+ operator++ ()
+ {
+ ++i_;
+ return *this;
+ }
+
+ pointer_iterator
+ operator++ (int)
+ {
+ pointer_iterator r (*this);
+ ++i_;
+ return r;
+ }
+
+ pointer_iterator&
+ operator-- ()
+ {
+ --i_;
+ return *this;
+ }
+
+ pointer_iterator
+ operator-- (int)
+ {
+ pointer_iterator r (*this);
+ --i_;
+ return r;
+ }
+
+ private:
+ I i_;
+ };
+
+ template <typename I>
+ inline bool
+ operator== (pointer_iterator<I> const& a, pointer_iterator<I> const& b)
+ {
+ return a.base () == b.base ();
+ }
+
+ template <typename I>
+ inline bool
+ operator!= (pointer_iterator<I> const& a, pointer_iterator<I> const& b)
+ {
+ return a.base () != b.base ();
+ }
+
+ template <typename I>
+ inline typename pointer_iterator<I>::difference_type
+ operator- (pointer_iterator<I> const& a, pointer_iterator<I> const& b)
+ {
+ return a.base () - b.base ();
+ }
+ }
+}
+
+#endif // CUTL_CONTAINER_POINTER_ITERATOR_HXX