<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>~/ntl-10.5.0test/doc/vector.cpp.html</title>
<meta name="Generator" content="Vim/8.0">
<meta name="plugin-version" content="vim7.4_v2">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css,pre_wrap,no_foldcolumn,expand_tabs,prevent_copy=">
<meta name="colorscheme" content="macvim">
<style type="text/css">
<!--
pre { white-space: pre-wrap; font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
* { font-size: 1em; }
.Statement { color: #b03060; font-weight: bold; }
.Comment { color: #0000ee; font-style: italic; }
.Type { color: #008b00; font-weight: bold; }
-->
</style>
<script type='text/javascript'>
<!--
-->
</script>
</head>
<body>
<pre id='vimCodeElement'>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment">MODULE: vector</span>
<span class="Comment">SUMMARY:</span>
<span class="Comment">Template class for dynamic-sized vectors.</span>
<span class="Comment">The declaration</span>
<span class="Comment"> Vec<T> v;</span>
<span class="Comment">creates a zero-length vector. To grow this vector to length n,</span>
<span class="Comment">execute</span>
<span class="Comment"> v.SetLength(n)</span>
<span class="Comment">This causes space to be allocated for (at least) n elements, and also causes</span>
<span class="Comment">the default constructor for T to be called to initialize these elements.</span>
<span class="Comment">The current length of a vector is available as v.length().</span>
<span class="Comment">Let n = v.length(). Calling v.SetLength(m) with m <= n sets the current length</span>
<span class="Comment">of v to m (but does not call any destructors or free any space). Calling</span>
<span class="Comment">v.SetLength(m) with m > n will allocate space and initialize as necessary, but</span>
<span class="Comment">will leave the values of the already allocated elements unchanged (although</span>
<span class="Comment">their addresses may change). If T has a user-defined default constructor, that</span>
<span class="Comment">is invoked. Otherwise, the new memory locations are "default initialized". In</span>
<span class="Comment">particular, this means that POD types may be uninitialized.</span>
<span class="Comment">v.MaxLength() is the largest value of n for which v.SetLength(n) was invoked,</span>
<span class="Comment">and is equal to the number of entries that have been initialized.</span>
<span class="Comment">v.SetMaxLength(n) will allocate space for and initialize up to n elements,</span>
<span class="Comment">without changing v.length().</span>
<span class="Comment">When v's destructor is called, all constructed elements will be destructed, and</span>
<span class="Comment">all space will be relinquished.</span>
<span class="Comment">v.allocated() is the number of elements which have been allocated,</span>
<span class="Comment">which may be more than the number elements initialized.</span>
<span class="Comment">Note that if n <= v.allocated(), then v.SetLength(n) is guaranteed</span>
<span class="Comment">not to cause any memory allocation or movement of objects.</span>
<span class="Comment">Space is managed using malloc, realloc, and free. When a vector is grown, a</span>
<span class="Comment">bit more space may be allocated than was requested for efficiency reasons.</span>
<span class="Comment">Note that when a vector is grown, the objects in the vector may have moved,</span>
<span class="Comment">possibly creating dangling references to vector elements. One has to be</span>
<span class="Comment">especially careful of this when using vectors passed as reference parameters</span>
<span class="Comment">that may alias one another.</span>
<span class="Comment">----------------------</span>
<span class="Comment">IMPLEMENTATION DETAILS</span>
<span class="Comment">----------------------</span>
<span class="Comment">A Vec<T> object is just a pointer to the first element of the array. There is</span>
<span class="Comment">a control block immediately before the first element that keeps track of</span>
<span class="Comment">several parameters: </span>
<span class="Comment"> len -- the logical length of the array (returned by length())</span>
<span class="Comment"> init -- the number of elements constructed (returned ny MaxLength())</span>
<span class="Comment"> alloc -- the number of elements for which space has been allocated</span>
<span class="Comment"> (returned by allocated())</span>
<span class="Comment"> fixed -- flag that indicates that the length is fixed </span>
<span class="Comment"> (returned by fixed())</span>
<span class="Comment">Note that 0 <= len <= init <- alloc</span>
<span class="Comment">---------------</span>
<span class="Comment">SPECIALIZATIONS</span>
<span class="Comment">---------------</span>
<span class="Comment">NTL currently defines an optimized specialization Vec<GF2>. There are a few</span>
<span class="Comment">quirks to be aware of. See the documentation file for vec_GF2 for more</span>
<span class="Comment">details.</span>
<span class="Comment">---------------------</span>
<span class="Comment">RANGE-BASED FOR LOOPS</span>
<span class="Comment">---------------------</span>
<span class="Comment">NTL's vectors provide sufficient functionality to enable range-based for-loops</span>
<span class="Comment">(in C++11). The safest ways to use this functionality are to write:</span>
<span class="Comment"> for (auto&& item : vec) { ... } // for read-only or read/write access</span>
<span class="Comment">or</span>
<span class="Comment"> for (T item : vec) { ... } // for access via a copy</span>
<span class="Comment">This is especially true if vec may be of type Vec<GF2>. Again, see the</span>
<span class="Comment">documentation file for vec_GF2 for more details.</span>
<span class="Comment">--------------</span>
<span class="Comment">OTHER FEATURES</span>
<span class="Comment">--------------</span>
<span class="Comment">The i-th vector element (counting from 0) is accessed as v[i]. If the macro</span>
<span class="Comment">NTL_RANGE_CHECK is defined, code is emitted to test if 0 <= i < v.length().</span>
<span class="Comment">This check is not performed by default.</span>
<span class="Comment">For old-time FORTRAN programmers, the i-th vector element (counting from 1) is</span>
<span class="Comment">accessed as v(i).</span>
<span class="Comment">--------------------</span>
<span class="Comment">REALLOCATION DETAILS</span>
<span class="Comment">--------------------</span>
<span class="Comment">When a vector is resized and not enough space has been allocated, then a</span>
<span class="Comment">reallocation process takes place. There are several strategies which can be</span>
<span class="Comment">used, which we list here from least to most efficient.</span>
<span class="Comment">COPY AND DESTROY STRATEGY:</span>
<span class="Comment">This is the same strategy used by the STL prior to C++11. New memory is</span>
<span class="Comment">allocated, and each element of the vector is copied (using a copy constructor)</span>
<span class="Comment">to the new memory, and then all the elements in the old memory is destroyed</span>
<span class="Comment">(using a destructor). While much safer than the Realloc Strategy, it can be a</span>
<span class="Comment">bit slower.</span>
<span class="Comment">MOVE STRATEGY:</span>
<span class="Comment">This is a strategy that is also used by the STL, assuming C++11. New memory is</span>
<span class="Comment">allocated, and each element of the vector is moved (using a move constructor)</span>
<span class="Comment">to the new memory, and then all the elements in the old memory is destroyed</span>
<span class="Comment">(using a destructor). This strategy is only viable if the underlying type has</span>
<span class="Comment">a "nothrow" move constructor. Typically, it will be significantly faster than</span>
<span class="Comment">the Copy and Destroy Strategy.</span>
<span class="Comment">REALLOC STRATEGY:</span>
<span class="Comment">This strategy simply calls the realloc function, which may result in objects</span>
<span class="Comment">being copied bit-wise from one location in memory to another. For most types</span>
<span class="Comment">of objects, even those with non-trivial constructors and destructors, this is</span>
<span class="Comment">perfectly safe, as most objects really don't care what address they are stored</span>
<span class="Comment">at. As an example of where this doesn't work, STL string implementations using</span>
<span class="Comment">a "short string" optimization may consist of an object containing a pointer to</span>
<span class="Comment">a sub-object, which would be invalidated if the object were bit-wise moved from</span>
<span class="Comment">one location to another. This strategy is the fastest of them all.</span>
<span class="Comment">CHOOSING A STRATEGY:</span>
<span class="Comment">In the implementation of Vec<T>, NTL will opt for the Realloc Strategy</span>
<span class="Comment">if one of the two conditions hold:</span>
<span class="Comment"> (i) T has a trivial copy constructor and a trivial destructor, or</span>
<span class="Comment"> (iii) T is a class that has been explicit declared "relocatable".</span>
<span class="Comment">(See below for details on how to declare that a class is relocatable.)</span>
<span class="Comment">Otherwise, NTL will use the Move Strategy if T has a nothrow move costructor.</span>
<span class="Comment">Otherwise, NTL will use the Copy Strategy if T has a copy constructor that is</span>
<span class="Comment">accessible (i.e., not private and not deleted). Otherwise, no reallocation</span>
<span class="Comment">implementation is provided, and a runtime error will be raised if a</span>
<span class="Comment">reallocation is required (this provides maximum flexiblilty and also maximum</span>
<span class="Comment">backward compatibility with previous versions of NTL, even though sometimes a</span>
<span class="Comment">compile-time diagnostic would be preferable).</span>
<span class="Comment">DECLARING A CLASS RELOCATABLE:</span>
<span class="Comment">One can declare T to be relocatable by adding the following line of code</span>
<span class="Comment">immediately after the definition of class T:</span>
<span class="Comment"> NTL_DECLARE_RELOCATABLE((T*))</span>
<span class="Comment">Notice the double parentheses and the "*" --- these are unfortunately </span>
<span class="Comment">necessary. This macro expands as </span>
<span class="Comment"> constexpr bool DeclareRelocatableType(T*) { return true; }</span>
<span class="Comment">Inside the class Vec<T>, this function is invoked with ((T*) 0) as the</span>
<span class="Comment">argument. By declaring relocatability via a function definition in this way,</span>
<span class="Comment">the Vec<T> class will always find (via "Koenig lookup", or ADL) the declaration</span>
<span class="Comment">for T in the namespace in which T is defined (assuming you put the</span>
<span class="Comment">relocatability declaration there as well).</span>
<span class="Comment">You can also declare a template class to be relocatable, as in:</span>
<span class="Comment"> template<class X, class Y></span>
<span class="Comment"> NTL_DECLARE_RELOCATABLE((T<X,Y>*))</span>
<span class="Comment">There is also a macro NTL_DECLARE_RELOCATABLE_WHEN, which leaves off the</span>
<span class="Comment">function body, if you want something other than { return true; }</span>
<span class="Comment">NTL also defines template functions:</span>
<span class="Comment"> template<class T></span>
<span class="Comment"> constexpr bool DeclareRelocatableType(T*) </span>
<span class="Comment"> { return ... ; }</span>
<span class="Comment">where "..." is an expression that returns true if T is a simple type that is</span>
<span class="Comment">safe to relocate, as determined by C++11 type traits. Such simple types</span>
<span class="Comment">include scalar types and simple classes with trivial copy constructor and</span>
<span class="Comment">destructor.</span>
<span class="Comment">NTL already declares as relocatable most if the fundamental types fot which it</span>
<span class="Comment">makes sense to do so.</span>
<span class="Comment">UNSAFE VECTOR MODE:</span>
<span class="Comment">The above describes the default behavior of NTL as of version 11.0. Prior to</span>
<span class="Comment">version 11.0, the default behavior was to only use the Realloc Strategy, which</span>
<span class="Comment">is potentially unsafe. You can revert to this old behavior by configuring</span>
<span class="Comment">NTL_SAFE_VECTORS=off.</span>
<span class="Comment">-------------------------</span>
<span class="Comment">COMPARISON TO STL VECTORS </span>
<span class="Comment">-------------------------</span>
<span class="Comment">When the length of an NTL vector is reduced, no objects are destroyed.</span>
<span class="Comment">In contrast, when the length of an STL vector is reduced, objects are</span>
<span class="Comment">destroyed (effectively, maintaining the invariant len == init).</span>
<span class="Comment">Also, STL vectors never use anything like the Realloc Strategy.</span>
<span class="Comment">----------------------</span>
<span class="Comment">HISTORICAL PERSPECTIVE</span>
<span class="Comment">----------------------</span>
<span class="Comment">When I first started working on NTL around 1990, C++ was a much simpler</span>
<span class="Comment">language. Among other things, there were no templates and no STL, so the Vec</span>
<span class="Comment">class started out (and remained, for many years) a set of macros (indeed, this</span>
<span class="Comment">approach was advocated in the first edition of Stroustrup's book).</span>
<span class="Comment">My thinking at that time was very much "C oriented". The idea of resizing a</span>
<span class="Comment">vector without using realloc never occured to me, and all of the classes I</span>
<span class="Comment">wanted to put in vectors were relocatable. Why would you ever bother making</span>
<span class="Comment">copies of vector elements and destroy the originals when you could just</span>
<span class="Comment">realloc? It wasn't until many years later that I even realized this was</span>
<span class="Comment">somehow questionable practice. Indeed, resizing via malloc is technically</span>
<span class="Comment">undefined behavior, but it's been working for me for over 25 years without</span>
<span class="Comment">problems.</span>
<span class="Comment">Furthermore, because of the poor performance of malloc in those days (which is</span>
<span class="Comment">much better now), I designed the Vec<ZZ_p> class (and a few others) to allocate</span>
<span class="Comment">the underlying ZZ's in blocks. This not only reduces the number of calls to</span>
<span class="Comment">malloc, but it also gives better locality of reference. Experiments in the</span>
<span class="Comment">last couple of years show that this is still benefit to doing this.</span>
<span class="Comment">With all of these design decisions baked into NTL's Vec class, transitioning to</span>
<span class="Comment">STL vectors would be problematic, and is unlikely to ever happen. But as</span>
<span class="Comment">things have evolved, NTL Vec's offers many of the same convenience and safety</span>
<span class="Comment">features as STL vector's.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Comment">// EXCEPTIONS: all functions below do not throw any exceptions,</span>
<span class="Comment">// except as noted</span>
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">class</span> Vec {
<span class="Statement">public</span>:
Vec(); <span class="Comment">// initially length 0</span>
Vec(<span class="Type">const</span> Vec& a);
<span class="Comment">// copy constructor; uses the assignment operator of T</span>
<span class="Comment">// for copying into locations that have already been initialized,</span>
<span class="Comment">// and uses the copy constructor for T for initializing new locations.</span>
<span class="Comment">// EXCEPTIONS: may throw</span>
Vec& <span class="Statement">operator</span>=(<span class="Type">const</span> Vec& a);
<span class="Comment">// assignment; uses the assignment operator of T</span>
<span class="Comment">// for copying into locations that have already been initialized,</span>
<span class="Comment">// and uses the copy constructor for T for initializing new locations.</span>
<span class="Comment">// EXCEPTIONS: weak ES (but if it throws, neither length nor MaxLength</span>
<span class="Comment">// will change, although some previously initialized elements</span>
<span class="Comment">// may have been assigned new values).</span>
Vec(Vec&& a);
<span class="Comment">// move constructor (C++11 only)</span>
<span class="Comment">// declared noexcept unless NTL_EXCEPTIONS flag is set</span>
<span class="Comment">// will revert to copy constructor if a is fixed</span>
Vec& <span class="Statement">operator</span>=(Vec&& a);
<span class="Comment">// move assignment (C++11 only)</span>
<span class="Comment">// declared noexcept unless NTL_EXCEPTIONS flag is set</span>
<span class="Comment">// will revert to copy assignment if *this or a is fixed</span>
<span class="Comment">// NOTE: If neither source nor destination are fixed, these operations will</span>
<span class="Comment">// be fast pointer moves and no exceptions will be thrown. If either are</span>
<span class="Comment">// fixed (say, the row in a Mat<T>), these operations revert to copy</span>
<span class="Comment">// operations, which may either throw an exception (if NTL_EXCEPTIONS is on)</span>
<span class="Comment">// or abort the program (if NTL_EXCEPTIONS is off).</span>
<span class="Comment">// NOTE: In a vector copy assignment x=a, all iterators, references,</span>
<span class="Comment">// and pointers related to x may be invalidated by the assignment.</span>
<span class="Comment">// In a vector move assignment, the same applies to a as well.</span>
<span class="Comment">// BACKWARD COMPATIBILITY: after introducing of "move constructors" in NTL</span>
<span class="Comment">// 10.4, there have been some reports of incompatibilties. Some legacy NTL</span>
<span class="Comment">// clients have been known to assume that x=a does not invalidate pointers</span>
<span class="Comment">// into x, provided x.length() >= a.length() before the assignment. This</span>
<span class="Comment">// assumption is not valid, however, for a move assignment. Because of this</span>
<span class="Comment">// problem, as of NTL 11.0, move assignments have been disabled by default</span>
<span class="Comment">// (this is controlled by the configuration flag NTL_DISABLE_MOVE_ASSIGN).</span>
<span class="Comment">// This affects vectors and matrices, as well as many other types (such as</span>
<span class="Comment">// polynomials) that are implemented in terms of vectors. Move assignment</span>
<span class="Comment">// is not disabled.</span>
~Vec();
<span class="Comment">// destructor: calls T's destructor for all initialized</span>
<span class="Comment">// elements in the vector, and then frees the vector itself</span>
<span class="Type">void</span> SetLength(<span class="Type">long</span> n);
<span class="Comment">// set current length to n, growing vector if necessary</span>
<span class="Comment">// new objects are initialized using the default contructor for T</span>
<span class="Comment">// EXCEPTIONS: strong ES (but the vector may have been</span>
<span class="Comment">// reallocated)</span>
<span class="Type">void</span> SetLength(<span class="Type">long</span> n, <span class="Type">const</span> T& a);
<span class="Comment">// set current length to n, growing vector if necessary</span>
<span class="Comment">// new objects are initialized using the copy contructor for T</span>
<span class="Comment">// EXCEPTIONS: strong ES (but the vector may have been</span>
<span class="Comment">// reallocated)</span>
<span class="Type">template</span><<span class="Type">class</span> F>
<span class="Type">void</span> SetLengthAndApply(<span class="Type">long</span> n, F f);
<span class="Comment">// set current length to n, growing vector if necessary</span>
<span class="Comment">// any new objects are initialized using defauly constructor</span>
<span class="Comment">// for T, and after that, f is applied to each new object x</span>
<span class="Comment">// as f(x).</span>
<span class="Comment">// EXCEPTIONS: strong ES (but the vector may have been</span>
<span class="Comment">// reallocated)</span>
<span class="Type">long</span> length() <span class="Type">const</span>;
<span class="Comment">// current length</span>
T& <span class="Statement">operator</span>[](<span class="Type">long</span> i);
<span class="Type">const</span> T& <span class="Statement">operator</span>[](<span class="Type">long</span> i) <span class="Type">const</span>;
<span class="Comment">// indexing operation, starting from 0.</span>
<span class="Comment">// The first version is applied to non-const Vec<T>,</span>
<span class="Comment">// and returns a non-const reference to a T, while the second version</span>
<span class="Comment">// is applied to a const Vec<T> and returns a const reference to a T.</span>
<span class="Comment">// EXCEPTIONS: may throw if range checking turned on, strong ES</span>
T& <span class="Statement">operator</span>()(<span class="Type">long</span> i);
<span class="Type">const</span> T& <span class="Statement">operator</span>()(<span class="Type">long</span> i) <span class="Type">const</span>;
<span class="Comment">// indexing operation, starting from 1</span>
<span class="Comment">// The first version is applied to non-const Vec<T>,</span>
<span class="Comment">// and returns a non-const reference to a T, while the second version</span>
<span class="Comment">// is applied to a const Vec<T> and returns a const reference to a T.</span>
<span class="Comment">// EXCEPTIONS: may throw if range checking turned on, strong ES</span>
T* elts();
<span class="Type">const</span> T* elts() <span class="Type">const</span>;
<span class="Comment">// returns address of first vector element (or 0 if no space has been</span>
<span class="Comment">// allocated for this vector). If a vector potentially has length 0, it is</span>
<span class="Comment">// safer to write v.elts() instead of &v[0]: the latter is not well defined</span>
<span class="Comment">// by the C++ standard (although this is likely an academic concern).</span>
<span class="Comment">//</span>
<span class="Comment">// The first version is applied to non-const Vec<T>, and returns a non-const</span>
<span class="Comment">// pointer to a T, while the second version is applied to a const Vec<T> and</span>
<span class="Comment">// returns a const reference to a T.</span>
<span class="Type">void</span> swap(Vec& y);
<span class="Comment">// swap with y (fast: just swaps pointers)</span>
<span class="Comment">// EXCEPTIONS: throws if vectors are fixed and lengths do not match, strong ES</span>
<span class="Type">void</span> move(Vec& y);
<span class="Comment">// move y into *this, killing y (fast: just moves pointers)</span>
<span class="Comment">// EXCEPTIONS: strong ES, raises an error if </span>
<span class="Comment">// &y != this and either y or *this are fixed</span>
<span class="Type">void</span> append(<span class="Type">const</span> T& a);
<span class="Comment">// append a to end of vector; uses the assignment operator of T</span>
<span class="Comment">// for copying into locations that have already been initialized,</span>
<span class="Comment">// and uses the copy constructor for T for initializing new locations.</span>
<span class="Comment">// EXCEPTIONS: strong ES if initializing a new element (and in any </span>
<span class="Comment">// case, if an exception throws, length and MaxLength remain </span>
<span class="Comment">// unchanged).</span>
<span class="Type">void</span> append(<span class="Type">const</span> Vec& w);
<span class="Comment">// append w to end of vector; uses the assignment operator of T</span>
<span class="Comment">// for copying into locations that have already been initialized,</span>
<span class="Comment">// and uses the copy constructor for T for initializing new locations.</span>
<span class="Comment">// EXCEPTIONS: strong ES if initializing new elements (and in any </span>
<span class="Comment">// case, if an exception throws, length and MaxLength remain </span>
<span class="Comment">// unchanged).</span>
<span class="Comment">// Alternative access interface </span>
<span class="Type">const</span> T& get(<span class="Type">long</span> i) <span class="Type">const</span>;
<span class="Comment">// v.get(i) returns v[i]</span>
<span class="Type">void</span> put(<span class="Type">long</span> i, <span class="Type">const</span> T& a);
<span class="Comment">// v.put(i, a) equivalent to v[i] = q</span>
<span class="Comment">// Some STL compatibility</span>
<span class="Type">typedef</span> T value_type;
<span class="Type">typedef</span> value_type& reference;
<span class="Type">typedef</span> <span class="Type">const</span> value_type& const_reference;
<span class="Type">typedef</span> value_type *iterator;
<span class="Type">typedef</span> <span class="Type">const</span> value_type *const_iterator;
T* data();
<span class="Type">const</span> T* data() <span class="Type">const</span>;
<span class="Comment">// v.data() same as v.elts()</span>
T* begin();
<span class="Type">const</span> T* begin() <span class="Type">const</span>;
<span class="Comment">// v.begin() same as v.elts()</span>
T* end();
<span class="Type">const</span> T* end() <span class="Type">const</span>;
<span class="Comment">// pointer to (one past) last element (or NULL)</span>
T& at(<span class="Type">long</span> i);
<span class="Type">const</span> T& at(<span class="Type">long</span> i) <span class="Type">const</span>;
<span class="Comment">// indexing with range checking</span>
<span class="Comment">// the remaining member functions are a bit esoteric (skip on first</span>
<span class="Comment">// reading)</span>
Vec(INIT_SIZE_TYPE, <span class="Type">long</span> n);
<span class="Comment">// Vec(INIT_SIZE, n) initializes vector with an intial length of n.</span>
<span class="Comment">// new objects are initialized using the default contructor for T</span>
<span class="Comment">// EXCEPTIONS: may throw</span>
Vec(INIT_SIZE_TYPE, <span class="Type">long</span> n, <span class="Type">const</span> T& a);
<span class="Comment">// Vec(INIT_SIZE, n, a) initializes vector with an intial length of n.</span>
<span class="Comment">// new objects are initialized using the copy contructor for T</span>
<span class="Comment">// EXCEPTIONS: may throw</span>
<span class="Type">void</span> kill();
<span class="Comment">// release space and set to length 0</span>
<span class="Type">void</span> SetMaxLength(<span class="Type">long</span> n);
<span class="Comment">// allocates space and initializes up to n elements. Does not change</span>
<span class="Comment">// current length</span>
<span class="Comment">// EXCEPTIONS: may throw, strong ES</span>
<span class="Type">void</span> FixLength(<span class="Type">long</span> n);
<span class="Comment">// sets length to n and prohibits all future length changes.</span>
<span class="Comment">// FixLength may only be invoked immediately after the default</span>
<span class="Comment">// construction or kill.</span>
<span class="Comment">// The kill operation is also subsequently prohibited, and swap is</span>
<span class="Comment">// allowed on fixed length vectors of the same length.</span>
<span class="Comment">// FixLength is provided mainly to implement Mat<T>, to enforce</span>
<span class="Comment">// the restriction that all rows have the same length.</span>
<span class="Comment">// EXCEPTIONS: may throw, strong ES</span>
<span class="Type">void</span> FixAtCurrentLength();
<span class="Comment">// fixes the length at the cuurent length and prohibits</span>
<span class="Comment">// all future length changes. </span>
<span class="Comment">// It is required that length() == MaxLength() when called.</span>
<span class="Comment">// EXCEPTIONS: if length() != MaxLength() and error is raised;</span>
<span class="Comment">// if length() == 0, a memory allocation error may be raised.</span>
<span class="Comment">// Strong ES.</span>
<span class="Type">long</span> fixed() <span class="Type">const</span>;
<span class="Comment">// test if length has been fixed by FixLength() or FixAtCurrentLength()</span>
<span class="Type">long</span> MaxLength() <span class="Type">const</span>;
<span class="Comment">// maximum length, i.e., number of allocated and initialized elements</span>
<span class="Type">long</span> allocated() <span class="Type">const</span>;
<span class="Comment">// the number of objects for which space has been allocated, but not</span>
<span class="Comment">// necessarily initialized; this may be larger than MaxLength().</span>
T& RawGet(<span class="Type">long</span> i);
<span class="Type">const</span> T& RawGet(<span class="Type">long</span> i) <span class="Type">const</span>;
<span class="Comment">// indexing with no range checking</span>
<span class="Type">long</span> position(<span class="Type">const</span> T& a) <span class="Type">const</span>;
<span class="Comment">// returns position of a in the vector, or -1 if it is not there.</span>
<span class="Comment">// The search is conducted from position 0 to allocated()-1 the vector, </span>
<span class="Comment">// and an error is raised if the object is found at position MaxLength()</span>
<span class="Comment">// or higher (in which case a references an uninitialized object).</span>
<span class="Comment">// Note that if NTL_CLEAN_PTR flag is set, this routine takes</span>
<span class="Comment">// linear time, and otherwise, it takes constant time.</span>
<span class="Comment">// EXCEPTIONS: may throw (as indicated above)</span>
<span class="Type">long</span> position1(<span class="Type">const</span> T& a) <span class="Type">const</span>;
<span class="Comment">// returns position of a in the vector, or -1 if it is not there.</span>
<span class="Comment">// The search is conducted from position 0 to length()-1 of the vector.</span>
<span class="Comment">// Note that if NTL_CLEAN_PTR flag is set, this routine takes</span>
<span class="Comment">// linear time, and otherwise, it takes constant time.</span>
};
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Some utility routines</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">void</span> swap(Vec<T>& x, Vec<T>& y);
<span class="Comment">// swaps x & y; same as x.swap(y)</span>
<span class="Comment">// EXCEPTIONS: same as for swap member function</span>
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">void</span> append(Vec<T>& v, <span class="Type">const</span> T& a);
<span class="Comment">// appends a to the end of v; same as v.append(a)</span>
<span class="Comment">// EXCEPTIONS: same as for append member function</span>
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">void</span> append(Vec<T>& v, <span class="Type">const</span> Vec<T>& w);
<span class="Comment">// appends w to the end of v; same as v.append(w)</span>
<span class="Comment">// EXCEPTIONS: same as for append member function</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Input/Output</span>
<span class="Comment">The I/O format for a vector v with n elements is:</span>
<span class="Comment"> [v[0] v[1] ... v[n-1]]</span>
<span class="Comment">Uses corresponding I/O operators for T</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">template</span><<span class="Type">class</span> T>
istream& <span class="Statement">operator</span>>>(istream&, Vec<T>&);
<span class="Comment">// EXCEPTIONS: may throw, weak ES</span>
<span class="Type">template</span><<span class="Type">class</span> T>
ostream& <span class="Statement">operator</span><<(ostream&, <span class="Type">const</span> Vec<T>&);
<span class="Comment">// EXCEPTIONS: may throw, weak ES</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Equality Testing</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">long</span> <span class="Statement">operator</span>==(<span class="Type">const</span> Vec<T>& a, <span class="Type">const</span> Vec<T>& b);
<span class="Type">template</span><<span class="Type">class</span> T>
<span class="Type">long</span> <span class="Statement">operator</span>!=(<span class="Type">const</span> Vec<T>& a, <span class="Type">const</span> Vec<T>& b);
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Customized Constructors and Destructors</span>
<span class="Comment"> </span>
<span class="Comment">Esoteric: skip on first reading...also these interfaces are subject to change</span>
<span class="Comment">When new elements in a vector need to be constructed, one of the</span>
<span class="Comment">following routines is called:</span>
<span class="Comment"> void BlockConstruct(T* p, long n); </span>
<span class="Comment"> // invokes T() to initialize p[i] for i = 0..n-1</span>
<span class="Comment"> void BlockConstructFromVec(T* p, long n, const T* q);</span>
<span class="Comment"> // invokes T(q[i]) to initialize p[i] for i = 0..n-1;</span>
<span class="Comment"> // q points to elements from a Vec<T></span>
<span class="Comment"> void BlockConstructFromObj(T* p, long n, const T& q);</span>
<span class="Comment"> // invokes T(q) to initialize p[i] for i = 0..n-1</span>
<span class="Comment">When a vector is destroyed, the following routine is called:</span>
<span class="Comment"> void BlockDestroy(T* p, long n);</span>
<span class="Comment"> // invokes ~T() on p[i] for i = 0..n-1</span>
<span class="Comment">The default behavior of these routines may be modified by </span>
<span class="Comment">overloading these functions with a custom implementation.</span>
<span class="Comment">EXCEPTIONS:</span>
<span class="Comment">In order to provide exception safe code, the Construct routines</span>
<span class="Comment">should provide strong ES; in particular, if any constructor</span>
<span class="Comment">throws, all newly constructed objects should be destroyed.</span>
<span class="Comment">Moreover, the BlockDestroy routine should not throw at all.</span>
<span class="Comment">In NTL, these routines are overridden for the ZZ_p and GF2E classes,</span>
<span class="Comment">so that many vector entries will be packed into contiguous storage</span>
<span class="Comment">locations. This reduces the number of invocations of malloc, and</span>
<span class="Comment">increases locality of reference.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
