A.18.3 The Generic Package Containers.Doubly_Linked_Lists
The language-defined generic package Containers.Doubly_Linked_Lists
provides private types List and Cursor, and a set of operations for each
type. A list container is optimized for insertion and deletion at any
position.
A doubly-linked list container
object manages a linked list of internal
nodes, each of which
contains an element and pointers to the next (successor) and previous
(predecessor) internal nodes. A cursor designates a particular node within
a list (and by extension the element contained in that node). A cursor
keeps designating the same node (and element) as long as the node is
part of the container, even if the node is moved in the container.
The
length of a list is the number of elements
it contains.
Static Semantics
The generic library
package Containers.Doubly_Linked_Lists has the following declaration:
with Ada.Iterator_Interfaces;
generic
type Element_Type
is private;
with function "=" (Left, Right : Element_Type)
return Boolean
is <>;
package Ada.Containers.Doubly_Linked_Lists
is
pragma Preelaborate(Doubly_Linked_Lists);
pragma Remote_Types(Doubly_Linked_Lists);
type List
is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(List);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_List :
constant List;
No_Element :
constant Cursor;
function Has_Element (Position : Cursor)
return Boolean;
package List_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : List) return Boolean;
function Length (Container : List)
return Count_Type;
function Is_Empty (Container : List)
return Boolean;
procedure Clear (Container :
in out List);
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out List;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type));
procedure Update_Element
(Container :
in out List;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type));
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element;
function Constant_Reference (Container :
aliased in List;
Position :
in Cursor)
return Constant_Reference_Type;
function Reference (Container :
aliased in out List;
Position :
in Cursor)
return Reference_Type;
procedure Assign (Target :
in out List; Source :
in List);
function Copy (Source : List)
return List;
procedure Move (Target :
in out List;
Source :
in out List);
procedure Insert (Container :
in out List;
Before :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out List;
Before :
in Cursor;
New_Item :
in Element_Type;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out List;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Prepend (Container :
in out List;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Append (Container :
in out List;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Delete (Container :
in out List;
Position :
in out Cursor;
Count :
in Count_Type := 1);
procedure Delete_First (Container :
in out List;
Count :
in Count_Type := 1);
procedure Delete_Last (Container :
in out List;
Count :
in Count_Type := 1);
procedure Reverse_Elements (Container :
in out List);
procedure Swap (Container :
in out List;
I, J :
in Cursor);
procedure Swap_Links (Container :
in out List;
I, J :
in Cursor);
procedure Splice (Target :
in out List;
Before :
in Cursor;
Source :
in out List);
procedure Splice (Target :
in out List;
Before :
in Cursor;
Source :
in out List;
Position :
in out Cursor);
procedure Splice (Container:
in out List;
Before :
in Cursor;
Position :
in Cursor);
function First (Container : List)
return Cursor;
function First_Element (Container : List)
return Element_Type;
function Last (Container : List)
return Cursor;
function Last_Element (Container : List)
return Element_Type;
function Next (Position : Cursor)
return Cursor;
function Previous (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
procedure Previous (Position :
in out Cursor);
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Contains (Container : List;
Item : Element_Type)
return Boolean;
This paragraph
was deleted.
procedure Iterate
(Container :
in List;
Process :
not null access procedure (Position :
in Cursor));
procedure Reverse_Iterate
(Container :
in List;
Process :
not null access procedure (Position :
in Cursor));
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
is
function Is_Sorted (Container : List)
return Boolean;
procedure Sort (Container :
in out List);
procedure Merge (Target :
in out List;
Source :
in out List);
end Generic_Sorting;
private
... -- not specified by the language
end Ada.Containers.Doubly_Linked_Lists;
The actual function for the generic formal function
"=" on Element_Type values is expected to define a reflexive
and symmetric relationship and return the same result value each time
it is called with a particular pair of values. If it behaves in some
other manner, the functions Find, Reverse_Find, and "=" on
list values return an unspecified value. The exact arguments and number
of calls of this generic formal function by the functions Find, Reverse_Find,
and "=" on list values are unspecified.
The type List is used to represent lists. The type
List needs finalization
(see
7.6).
Empty_List represents the empty List object. It has
a length of 0. If an object of type List is not otherwise initialized,
it is initialized to the same value as Empty_List.
No_Element represents a cursor that designates no
element. If an object of type Cursor is not otherwise initialized, it
is initialized to the same value as No_Element.
The predefined "=" operator for type Cursor
returns True if both cursors are No_Element, or designate the same element
in the same container.
Execution of the default implementation of the Input,
Output, Read, or Write attribute of type Cursor raises Program_Error.
List'Write for a List object L writes Length(L)
elements of the list to the stream. It also may write additional information
about the list.
List'Read reads the representation of a list from
the stream, and assigns to Item a list with the same length and
elements as was written by List'Write.
Some operations of this generic package have access-to-subprogram
parameters. To ensure such operations are well-defined, they guard against
certain actions by the designated subprogram. In particular, some operations
check for “tampering with cursors” of a container because
they depend on the set of elements of the container remaining constant,
and others check for “tampering with elements” of a container
because they depend on elements of the container not being replaced.
A
subprogram is said to
tamper with cursors of a list object
L
if:
it inserts or deletes elements of L, that
is, it calls the Insert, Clear, Delete, or Delete_Last procedures with
L as a parameter; or
it reorders the elements of L, that is,
it calls the Splice, Swap_Links, or Reverse_Elements procedures or the
Sort or Merge procedures of an instance of Generic_Sorting with L
as a parameter; or
it finalizes L; or
it calls the Assign procedure with L as
the Target parameter; or
it calls the Move procedure with L as a
parameter.
A
subprogram is said to
tamper with elements of a list object
L
if:
it tampers with cursors of L; or
it replaces one or more elements of L, that
is, it calls the Replace_Element or Swap procedures with L as
a parameter.
When tampering
with cursors is
prohibited for a particular list object
L,
Program_Error is propagated by a call of any language-defined subprogram
that is defined to tamper with the cursors of
L, leaving
L
unmodified. Similarly, when tampering with elements is
prohibited
for a particular list object
L, Program_Error is propagated by
a call of any language-defined subprogram that is defined to tamper with
the elements of
L (or tamper with the cursors of
L), leaving
L unmodified. These checks are made before any other defined behavior
of the body of the language-defined subprogram.
function Has_Element (Position : Cursor) return Boolean;
Returns True if
Position designates an element, and returns False otherwise.
function "=" (Left, Right : List) return Boolean;
If Left and Right
denote the same list object, then the function returns True. If Left
and Right have different lengths, then the function returns False. Otherwise,
it compares each element in Left to the corresponding element in Right
using the generic formal equality operator. If any such comparison returns
False, the function returns False; otherwise, it returns True. Any exception
raised during evaluation of element equality is propagated.
function Length (Container : List) return Count_Type;
Returns the number
of elements in Container.
function Is_Empty (Container : List) return Boolean;
Equivalent to Length
(Container) = 0.
procedure Clear (Container : in out List);
Removes all the
elements from Container.
function Element (Position : Cursor) return Element_Type;
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, Element returns
the element designated by Position.
procedure Replace_Element (Container : in out List;
Position : in Cursor;
New_Item : in Element_Type);
If Position equals
No_Element, then Constraint_Error is propagated; if Position does not
designate an element in Container, then Program_Error is propagated.
Otherwise, Replace_Element assigns the value New_Item to the element
designated by Position.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, Query_Element
calls Process.all with the element designated by Position as the
argument. Tampering with the elements of the list that contains the element
designated by Position is prohibited during the execution of the call
on Process.all. Any exception raised by Process.all is
propagated.
procedure Update_Element
(Container : in out List;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Update_Element calls Process.all
with the element designated by Position as the argument. Tampering with
the elements of Container is prohibited during the execution of the call
on Process.all. Any exception raised by Process.all is
propagated.
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
The types Constant_Reference_Type
and Reference_Type need finalization.
The default initialization of an object of type
Constant_Reference_Type or Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in List;
Position : in Cursor)
return Constant_Reference_Type;
This function (combined
with the Constant_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read access to an individual element of a list
given a cursor.
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Constant_Reference returns
an object whose discriminant is an access value that designates the element
designated by Position. Tampering with the elements of Container is prohibited
while the object returned by Constant_Reference exists and has not been
finalized.
function Reference (Container : aliased in out List;
Position : in Cursor)
return Reference_Type;
This function (combined
with the Variable_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read and write access to an individual element
of a list given a cursor.
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Reference returns an object
whose discriminant is an access value that designates the element designated
by Position. Tampering with the elements of Container is prohibited while
the object returned by Reference exists and has not been finalized.
procedure Assign (Target : in out List; Source : in List);
If Target denotes
the same object as Source, the operation has no effect. Otherwise, the
elements of Source are copied to Target as for an
assignment_statement
assigning Source to Target.
function Copy (Source : List) return List;
Returns a list whose
elements match the elements of Source.
procedure Move (Target : in out List;
Source : in out List);
If Target denotes
the same object as Source, then the operation has no effect. Otherwise,
the operation is equivalent to Assign (Target, Source) followed by Clear
(Source).
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
If Before is not
No_Element, and does not designate an element in Container, then Program_Error
is propagated. Otherwise, Insert inserts Count copies of New_Item prior
to the element designated by Before. If Before equals No_Element, the
new elements are inserted after the last node (if any). Any exception
raised during allocation of internal storage is propagated, and Container
is not modified.
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
If Before is not
No_Element, and does not designate an element in Container, then Program_Error
is propagated. Otherwise, Insert allocates Count copies of New_Item,
and inserts them prior to the element designated by Before. If Before
equals No_Element, the new elements are inserted after the last element
(if any). Position designates the first newly-inserted element, or if
Count equals 0, then Position is assigned the value of Before. Any exception
raised during allocation of internal storage is propagated, and Container
is not modified.
procedure Insert (Container : in out List;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
If Before is not
No_Element, and does not designate an element in Container, then Program_Error
is propagated. Otherwise, Insert inserts Count new elements prior to
the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last node (if any). The new elements
are initialized by default (see
3.3.1). Position
designates the first newly-inserted element, or if Count equals 0, then
Position is assigned the value of Before. Any exception raised during
allocation of internal storage is propagated, and Container is not modified.
procedure Prepend (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
Equivalent to Insert
(Container, First (Container), New_Item, Count).
procedure Append (Container : in out List;
New_Item : in Element_Type;
Count : in Count_Type := 1);
Equivalent to Insert
(Container, No_Element, New_Item, Count).
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
If Position equals
No_Element, then Constraint_Error is propagated. If Position does not
designate an element in Container, then Program_Error is propagated.
Otherwise, Delete removes (from Container) Count elements starting at
the element designated by Position (or all of the elements starting at
Position if there are fewer than Count elements starting at Position).
Finally, Position is set to No_Element.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
If Length (Container)
<= Count, then Delete_First is equivalent to Clear (Container). Otherwise,
it removes the first Count nodes from Container.
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
If Length (Container)
<= Count, then Delete_Last is equivalent to Clear (Container). Otherwise,
it removes the last Count nodes from Container.
procedure Reverse_Elements (Container : in out List);
Reorders the elements
of Container in reverse order.
procedure Swap (Container : in out List;
I, J : in Cursor);
If either I or J
is No_Element, then Constraint_Error is propagated. If either I or J
do not designate an element in Container, then Program_Error is propagated.
Otherwise, Swap exchanges the values of the elements designated by I
and J.
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
If either I or J
is No_Element, then Constraint_Error is propagated. If either I or J
do not designate an element in Container, then Program_Error is propagated.
Otherwise, Swap_Links exchanges the nodes designated by I and J.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
If Before is not
No_Element, and does not designate an element in Target, then Program_Error
is propagated. Otherwise, if Source denotes the same object as Target,
the operation has no effect. Otherwise, Splice reorders elements such
that they are removed from Source and moved to Target, immediately prior
to Before. If Before equals No_Element, the nodes of Source are spliced
after the last node of Target. The length of Target is incremented by
the number of nodes in Source, and the length of Source is set to 0.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List;
Position : in out Cursor);
If Position is No_Element,
then Constraint_Error is propagated. If Before does not equal No_Element,
and does not designate an element in Target, then Program_Error is propagated.
If Position does not equal No_Element, and does not designate a node
in Source, then Program_Error is propagated. If Source denotes the same
object as Target, then there is no effect if Position equals Before,
else the element designated by Position is moved immediately prior to
Before, or, if Before equals No_Element, after the last element. In both
cases, Position and the length of Target are unchanged. Otherwise, the
element designated by Position is removed from Source and moved to Target,
immediately prior to Before, or, if Before equals No_Element, after the
last element of Target. The length of Target is incremented, the length
of Source is decremented, and Position is updated to represent an element
in Target.
procedure Splice (Container: in out List;
Before : in Cursor;
Position : in Cursor);
If Position is No_Element,
then Constraint_Error is propagated. If Before does not equal No_Element,
and does not designate an element in Container, then Program_Error is
propagated. If Position does not equal No_Element, and does not designate
a node in Container, then Program_Error is propagated. If Position equals
Before there is no effect. Otherwise, the element designated by Position
is moved immediately prior to Before, or, if Before equals No_Element,
after the last element. The length of Container is unchanged.
function First (Container : List) return Cursor;
If Container is
empty, First returns the value No_Element. Otherwise, it returns a cursor
that designates the first node in Container.
function First_Element (Container : List) return Element_Type;
Equivalent to Element
(First (Container)).
function Last (Container : List) return Cursor;
If Container is
empty, Last returns the value No_Element. Otherwise, it returns a cursor
that designates the last node in Container.
function Last_Element (Container : List) return Element_Type;
Equivalent to Element
(Last (Container)).
function Next (Position : Cursor) return Cursor;
If Position equals
No_Element or designates the last element of the container, then Next
returns the value No_Element. Otherwise, it returns a cursor that designates
the successor of the element designated by Position.
function Previous (Position : Cursor) return Cursor;
If Position equals
No_Element or designates the first element of the container, then Previous
returns the value No_Element. Otherwise, it returns a cursor that designates
the predecessor of the element designated by Position.
procedure Next (Position : in out Cursor);
Equivalent to Position
:= Next (Position).
procedure Previous (Position : in out Cursor);
Equivalent to Position
:= Previous (Position).
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
If Position is not
No_Element, and does not designate an element in Container, then Program_Error
is propagated. Find searches the elements of Container for an element
equal to Item (using the generic formal equality operator). The search
starts at the element designated by Position, or at the first element
if Position equals No_Element. It proceeds towards Last (Container).
If no equal element is found, then Find returns No_Element. Otherwise,
it returns a cursor designating the first equal element encountered.
function Reverse_Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
If Position is not
No_Element, and does not designate an element in Container, then Program_Error
is propagated. Find searches the elements of Container for an element
equal to Item (using the generic formal equality operator). The search
starts at the element designated by Position, or at the last element
if Position equals No_Element. It proceeds towards First (Container).
If no equal element is found, then Reverse_Find returns No_Element. Otherwise,
it returns a cursor designating the first equal element encountered.
function Contains (Container : List;
Item : Element_Type) return Boolean;
Equivalent to Find
(Container, Item) /= No_Element.
Paragraphs 139
and 140 were moved above.
procedure Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
Iterate calls Process.all
with a cursor that designates each node in Container, starting with the
first node and moving the cursor as per the Next function. Tampering
with the cursors of Container is prohibited during the execution of a
call on Process.all. Any exception raised by Process.all
is propagated.
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
Iterates over the
nodes in Container as per procedure Iterate, except that elements are
traversed in reverse order, starting with the last node and moving the
cursor as per the Previous function.
function Iterate (Container : in List)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns
a reversible iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each node in Container, starting with the first node and
moving the cursor as per the Next function when used as a forward iterator,
and starting with the last node and moving the cursor as per the Previous
function when used as a reverse iterator. Tampering with the cursors
of Container is prohibited while the iterator object exists (in particular,
in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
function Iterate (Container : in List; Start : in Cursor)
return List_Iterator_Interfaces.Reversible_Iterator'Class;
If Start is not
No_Element and does not designate an item in Container, then Program_Error
is propagated. If Start is No_Element, then Constraint_Error is propagated.
Otherwise, Iterate returns a reversible iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each node in Container, starting with the node designated
by Start and moving the cursor as per the Next function when used as
a forward iterator, or moving the cursor as per the Previous function
when used as a reverse iterator. Tampering with the cursors of Container
is prohibited while the iterator object exists (in particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
The actual function for the generic formal function
"<" of Generic_Sorting is expected to return the same value
each time it is called with a particular pair of element values. It should
define a strict weak ordering relationship (see
A.18);
it should not modify Container. If the actual for "<" behaves
in some other manner, the behavior of the subprograms of Generic_Sorting
are unspecified. The number of times the subprograms of Generic_Sorting
call "<" is unspecified.
function Is_Sorted (Container : List) return Boolean;
Returns True if
the elements are sorted smallest first as determined by the generic formal
"<" operator; otherwise, Is_Sorted returns False. Any exception
raised during evaluation of "<" is propagated.
procedure Sort (Container : in out List);
Reorders the nodes
of Container such that the elements are sorted smallest first as determined
by the generic formal "<" operator provided. The sort is
stable. Any exception raised during evaluation of "<" is
propagated.
procedure Merge (Target : in out List;
Source : in out List);
If Source is empty,
then Merge does nothing. If Source and Target are the same nonempty container
object, then Program_Error is propagated. Otherwise, Merge removes elements
from Source and inserts them into Target; afterwards, Target contains
the union of the elements that were initially in Source and Target; Source
is left empty. If Target and Source are initially sorted smallest first,
then Target is ordered smallest first as determined by the generic formal
"<" operator; otherwise, the order of elements in Target
is unspecified. Any exception raised during evaluation of "<"
is propagated.
Bounded (Run-Time) Errors
Calling Merge in an instance
of Generic_Sorting with either Source or Target not ordered smallest
first using the provided generic formal "<" operator is
a bounded error. Either Program_Error is raised after Target is updated
as described for Merge, or the operation works as defined.
It is a bounded error for
the actual function associated with a generic formal subprogram, when
called as part of an operation of this package, to tamper with elements
of any List parameter of the operation. Either Program_Error is raised,
or the operation works as defined on the value of the List either prior
to, or subsequent to, some or all of the modifications to the List.
It is a bounded error to call
any subprogram declared in the visible part of Containers.Doubly_Linked_Lists
when the associated container has been finalized. If the operation takes
Container as an
in out parameter, then it raises Constraint_Error
or Program_Error. Otherwise, the operation either proceeds as it would
for an empty container, or it raises Constraint_Error or Program_Error.
Erroneous Execution
A Cursor value is
invalid if any of the following have occurred since it was created:
The list that contains the element it designates
has been finalized;
The list that contains the element it designates
has been used as the Target of a call to Assign, or as the target of
an
assignment_statement;
The list that contains the element it designates
has been used as the Source or Target of a call to Move; or
The element it designates has been removed from
the list that previously contained the element.
The result of "=" or Has_Element is unspecified
if it is called with an invalid cursor parameter. Execution is erroneous
if any other subprogram declared in Containers.Doubly_Linked_Lists is
called with an invalid cursor parameter.
Execution is erroneous if the list associated
with the result of a call to Reference or Constant_Reference is finalized
before the result object returned by the call to Reference or Constant_Reference
is finalized.
Implementation Requirements
No storage associated with a doubly-linked List
object shall be lost upon assignment or scope exit.
The execution of an
assignment_statement
for a list shall have the effect of copying the elements from the source
list object to the target list object and changing the length of the
target object to that of the source object.
Implementation Advice
Containers.Doubly_Linked_Lists should be implemented
similarly to a linked list. In particular, if N is the length
of a list, then the worst-case time complexity of Element, Insert with
Count=1, and Delete with Count=1 should be O(log N).
The worst-case time complexity of a call on procedure
Sort of an instance of Containers.Doubly_Linked_Lists.Generic_Sorting
should be O(N**2), and the average time complexity should
be better than O(N**2).
Move should not copy elements, and should minimize
copying of internal data structures.
If an exception is propagated from a list operation,
no storage should be lost, nor any elements removed from a list unless
specified by the operation.
50 Sorting a list never copies elements,
and is a stable sort (equal elements remain in the original order). This
is different than sorting an array or vector, which may need to copy
elements, and is probably not a stable sort.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
