* Matrices:: Matrices.
* Indexed objects:: Handling indexed quantities.
* Non-commutative objects:: Algebras with non-commutative products.
+* Hash Maps:: A faster alternative to std::map<>.
@end menu
of the metric tensor.
-@node Non-commutative objects, Methods and Functions, Indexed objects, Basic Concepts
+@node Non-commutative objects, Hash Maps, Indexed objects, Basic Concepts
@c node-name, next, previous, up
@section Non-commutative objects
@end example
-@node Methods and Functions, Information About Expressions, Non-commutative objects, Top
+@node Hash Maps, Methods and Functions, Non-commutative objects, Basic Concepts
+@c node-name, next, previous, up
+@section Hash Maps
+@cindex hash maps
+@cindex @code{exhashmap} (class)
+
+For your convenience, GiNaC offers the container template @code{exhashmap<T>}
+that can be used as a drop-in replacement for the STL
+@code{std::map<ex, T, ex_is_less>}, using hash tables to provide faster,
+typically constant-time, element look-up than @code{map<>}.
+
+@code{exhashmap<>} supports all @code{map<>} members and operations, with the
+following differences:
+
+@itemize @bullet
+@item
+no @code{lower_bound()} and @code{upper_bound()} methods
+@item
+no reverse iterators, no @code{rbegin()}/@code{rend()}
+@item
+no @code{operator<(exhashmap, exhashmap)}
+@item
+the comparison function object @code{key_compare} is hardcoded to
+@code{ex_is_less}
+@item
+the constructor @code{exhashmap(size_t n)} allows specifying the minimum
+initial hash table size (the actual table size after construction may be
+larger than the specified value)
+@item
+the method @code{size_t bucket_count()} returns the current size of the hash
+table
+@item
+@code{insert()} and @code{erase()} operations invalidate all iterators
+@end itemize
+
+
+@node Methods and Functions, Information About Expressions, Hash Maps, Top
@c node-name, next, previous, up
@chapter Methods and Functions
@cindex polynomial
@subsection Accessing subexpressions
-@cindex @code{nops()}
-@cindex @code{op()}
@cindex container
-@cindex @code{relational} (class)
Many GiNaC classes, like @code{add}, @code{mul}, @code{lst}, and
@code{function}, act as containers for subexpressions. For example, the
subexpressions of a sum (an @code{add} object) are the individual terms,
and the subexpressions of a @code{function} are the function's arguments.
-GiNaC provides two ways of accessing subexpressions. The first way is to use
-the two methods
+@cindex @code{nops()}
+@cindex @code{op()}
+GiNaC provides several ways of accessing subexpressions. The first way is to
+use the two methods
@example
size_t ex::nops();
@code{indexed} objects, @code{op(0)} is the base expression and @code{op(i)},
@math{i>0} are the indices.
+@cindex iterators
+@cindex @code{const_iterator}
The second way to access subexpressions is via the STL-style random-access
iterator class @code{const_iterator} and the methods
If the expression has no subexpressions, then @code{begin() == end()}. These
iterators can also be used in conjunction with non-modifying STL algorithms.
-Here is an example that (non-recursively) prints all the subexpressions of a
+Here is an example that (non-recursively) prints the subexpressions of a
given expression in three different ways:
@example
@}
@end example
-Additionally, the left-hand and right-hand side expressions of objects of
+@cindex @code{const_preorder_iterator}
+@cindex @code{const_postorder_iterator}
+@code{op()}/@code{nops()} and @code{const_iterator} only access an
+expression's immediate children. GiNaC provides two additional iterator
+classes, @code{const_preorder_iterator} and @code{const_postorder_iterator},
+that iterate over all objects in an expression tree, in preorder or postorder,
+respectively. They are STL-style forward iterators, and are created with the
+methods
+
+@example
+const_preorder_iterator ex::preorder_begin();
+const_preorder_iterator ex::preorder_end();
+const_postorder_iterator ex::postorder_begin();
+const_postorder_iterator ex::postorder_end();
+@end example
+
+The following example illustrates the differences between
+@code{const_iterator}, @code{const_preorder_iterator}, and
+@code{const_postorder_iterator}:
+
+@example
+@{
+ symbol A("A"), B("B"), C("C");
+ ex e = lst(lst(A, B), C);
+
+ std::copy(e.begin(), e.end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // @{A,B@}
+ // C
+
+ std::copy(e.preorder_begin(), e.preorder_end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // @{@{A,B@},C@}
+ // @{A,B@}
+ // A
+ // B
+ // C
+
+ std::copy(e.postorder_begin(), e.postorder_end(),
+ std::ostream_iterator<ex>(cout, "\n"));
+ // A
+ // B
+ // @{A,B@}
+ // C
+ // @{@{A,B@},C@}
+@}
+@end example
+
+@cindex @code{relational} (class)
+Finally, the left-hand side and right-hand side expressions of objects of
class @code{relational} (and only of these) can also be accessed with the
methods
@}
@end example
+Alternatively, you could use pre- or postorder iterators for the tree
+traversal:
+
+@example
+lst gather_indices(const ex & e)
+@{
+ gather_indices_visitor v;
+ for (const_preorder_iterator i = e.preorder_begin();
+ i != e.preorder_end(); ++i) @{
+ i->accept(v);
+ @}
+ return v.get_result();
+@}
+@end example
+
@node Polynomial Arithmetic, Rational Expressions, Visitors and Tree Traversal, Methods and Functions
@c node-name, next, previous, up
git://www.ginac.de / ginac.git / blobdiff