Maps

The language-defined generic packages Containers.Hashed_Maps and Containers.Ordered_Maps provide private types Map and Cursor, and a set of operations for each type. A map container allows an arbitrary type to be used as a key to find the element associated with that key. A hashed map uses a hash function to organize the keys, while an ordered map orders the keys per a specified relation.

This subclause describes the declarations that are common to both kinds of maps. See A.18.5 for a description of the semantics specific to Containers.Hashed_Maps and A.18.6 for a description of the semantics specific to Containers.Ordered_Maps.

Bounded (Run-Time) Errors

It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of a map package, to tamper with elements of any map parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the map either prior to, or subsequent to, some or all of the modifications to the map.

It is a bounded error to call any subprogram declared in the visible part of a map package 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 map that contains the node it designates has been finalized.
• The map that contains the node it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement.
• The map that contains the node it designates has been used as the Source or Target of a call to Move.
• The node it designates has been removed from the map that previously contained the node.

The result of "=" or Has_Element is unspecified if these functions are called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps is called with an invalid cursor parameter.

Execution is erroneous if the map 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.

Hashed Maps

with Ada.Iterator_Interfaces;

generic
   type Key_Type     is private;
   type Element_Type is private;
   with function Hash(Key: Key_Type) return Hash_Type;
   with function Equivalent_Keys(Left, Right: Key_Type) return Boolean;
   with function "="(Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Maps is
   with Preelaborate, Remote_Types, Nonblocking, Global => in out synchronized is

   type Map    is tagged private;
   type Cursor is        private;

   Empty_Map : constant Map;
   No_Element: constant Cursor;

   function Has_Element(                Position: Cursor) return Boolean;
   function Has_Element(Container: Map; Position: Cursor) return Boolean;

   package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

   function "="(Left, Right: Map) return Boolean;

   function Tampering_With_Cursors_Prohibited (Container: Map) return Boolean;
   function Tampering_With_Elements_Prohibited(Container: Map) return Boolean;

   function Empty(Capacity: Count_Type := <implementation-defined>) return Map;
   function Capacity(Container: Map) return Count_Type;
   function Length  (Container: Map) return Count_Type;
   function Is_Empty(Container: Map) return Boolean;

   procedure Reserve_Capacity(Container: in out Map; Capacity: Count_Type);
   procedure Clear           (Container: in out Map);

   function Key(                Position: Cursor) return Key_Type;
   function Key(Container: Map; Position: Cursor) return Key_Type;
   function Element(                Position: Cursor) return Element_Type;
   function Element(Container: Map; Position: Cursor) return Element_Type;

   procedure Replace_Element(Container: in out Map; Position: Cursor; New_item: Element_Type);
   procedure Query_Element(Position: Cursor;
                           Process : not null access procedure(Key: Key_Type; Element: Element_Type));
   procedure Query_Element(Container: Map;
                           Position : Cursor;
                           Process  : not null access procedure(Key: Key_Type; Element: Element_Type));
   procedure Update_Element(Container: in out Map;
                            Position : Cursor;
                            Process  : not null access procedure(Key: Key_Type; Element: in out Element_Type));

   type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
   type Reference_Type         (Element: not null access          Element_Type) is private;

   function Constant_Reference(Container: aliased        Map; Position: Cursor) return Constant_Reference_Type;
   function Reference         (Container: aliased in out Map; Position: Cursor) return Reference_Type;
   function Constant_Reference(Container: aliased        Map; Key: Key_Type)    return Constant_Reference_Type;
   function Reference         (Container: aliased in out Map; Key: Key_Type)    return Reference_Type;

   procedure Assign(Target: in out Map; Source: Map);

   function Copy(Source: Map; Capacity: Count_Type := 0) return Map;

   procedure Move(Target: in out Map; Source: in out Map);
   procedure Insert(Container: in out Map;
                     Key     : Key_Type;
                     New_Item: Element_Type;
                     Position: out Cursor;
                     Inserted: out Boolean);
   procedure Insert(Container: in out Map;
                    Key      : Key_Type;
                    Position : out Cursor;
                    Inserted : out Boolean);
   procedure Insert (Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Include(Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Replace(Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Exclude(Container: in out Map; Key: Key_Type);
   procedure Delete (Container: in out Map; Key: Key_Type);
   procedure Delete (Container: in out Map; Position: in out Cursor);

   function First(Container: Map)                   return Cursor;
   function Next (Container: Map; Position: Cursor) return Cursor;
   function Next (                Position: Cursor) return Cursor;

   procedure Next(Position: in out Cursor);
   procedure Next(Container: Map; Position: in out Cursor);

   function Find    (Container: Map; Key: Key_Type) return Cursor;
   function Element (Container: Map; Key: Key_Type) return Element_Type;
   function Contains(Container: Map; Key: Key_Type) return Boolean;
   function Equivalent_Keys(Left, Right: Cursor)           return Boolean;
   function Equivalent_Keys(Left: Cursor; Right: Key_Type) return Boolean;
   function Equivalent_Keys(Left: Key_Type; Right: Cursor) return Boolean;

   procedure Iterate(Container: Map; Process: not null access procedure(Position: Cursor));
   function  Iterate(Container: Map) return Map_Iterator_Interfaces.Parallel_Iterator'Class;

   package Stable is
      type Map(Base: not null access Hashed_Maps.Map) is tagged limited private;
      type Cursor is private;

      Empty_Map : constant Map;
      No_Element: constant Cursor;

      function Has_Element(Position: Cursor) return Boolean;

      package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

      procedure Assign(Target: in out Hashed_Maps.Map; Source: Map);

      function Copy(Source: Hashed_Maps.Map) return Map;

      type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
      type Reference_Type         (Element: not null access          Element_Type) is private;
   end Stable;
end Ada.Containers.Hashed_Maps;

Ordered Maps

with Ada.Iterator_Interfaces;

generic
   type Key_Type     is private;
   type Element_Type is private;
   with function "<"(Left, Right: Key_Type)     return Boolean is <>;
   with function "="(Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Maps is
   with Preelaborate, Remote_Types, Nonblocking,
        Global => in out synchronized is

   function Equivalent_Keys(Left, Right: Key_Type) return Boolean is
      (not ((Left < Right) or (Right < Left)));

   type Map    is tagged private;
   type Cursor is        private;

   Empty_Map : constant Map;
   No_Element: constant Cursor;

   function Has_Element(Position: Cursor) return Boolean;
   function Has_Element(Container: Map; Position: Cursor) return Boolean;

   package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

   function "="(Left, Right: Map) return Boolean;

   function Tampering_With_Cursors_Prohibited (Container: Map) return Boolean;
   function Tampering_With_Elements_Prohibited(Container: Map) return Boolean;

   function Empty return Map is
      (Empty_Map);

   procedure Clear(Container: in out Map);

   function Length  (Container: Map) return Count_Type;
   function Is_Empty(Container: Map) return Boolean;
   function Key(                Position: Cursor) return Key_Type;
   function Key(Container: Map; Position: Cursor) return Key_Type;
   function Element(                Position: Cursor) return Element_Type;
   function Element(Container: Map; Position: Cursor) return Element_Type;
   procedure Replace_Element(Container: in out Map; Position: Cursor; New_item: Element_Type);
   procedure Query_Element(Position: Cursor;
                           Process : not null access procedure(Key: Key_Type; Element: Element_Type));
   procedure Query_Element(Container: Map;
                           Position : Cursor;
                           Process  : not null access procedure(Key: Key_Type; Element: Element_Type));
   procedure Update_Element(Container: in out Map;
                            Position : Cursor;
                            Process  : not null access procedure(Key: Key_Type; Element: in out Element_Type));

   type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
   type Reference_Type         (Element: not null access          Element_Type) is private;

   function Constant_Reference(Container: aliased        Map; Position: Cursor) return Constant_Reference_Type;
   function Reference         (Container: aliased in out Map; Position: Cursor) return Reference_Type;
   function Constant_Reference(Container: aliased        Map; Key: Key_Type)    return Constant_Reference_Type;
   function Reference         (Container: aliased in out Map; Key: Key_Type)    return Reference_Type;

   procedure Assign(Target: in out Map; Source:        Map);
   procedure Move  (Target: in out Map; Source: in out Map);
   function  Copy(Source: Map) return Map;

   procedure Insert(Container: in out Map;
                    Key      : Key_Type;
                    New_Item : Element_Type;
                    Position : out Cursor;
                    Inserted : out Boolean);
   procedure Insert      (Container: in out Map; Key: Key_Type; Position: out Cursor; Inserted : out Boolean);
   procedure Insert      (Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Include     (Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Replace     (Container: in out Map; Key: Key_Type; New_Item: Element_Type);
   procedure Exclude     (Container: in out Map; Key: Key_Type);
   procedure Delete      (Container: in out Map; Key: Key_Type);
   procedure Delete      (Container: in out Map; Position: in out Cursor);
   procedure Delete_First(Container: in out Map);
   procedure Delete_Last (Container: in out Map);

   function First        (Container: Map) return Cursor;
   function First_Element(Container: Map) return Element_Type;
   function First_Key    (Container: Map) return Key_Type;
   function Last         (Container: Map) return Cursor;
   function Last_Element (Container: Map) return Element_Type;
   function Last_Key     (Container: Map) return Key_Type;

   function  Next(                Position: Cursor) return Cursor;
   function  Next(Container: Map; Position: Cursor) return Cursor;
   procedure Next(                Position: in out Cursor);
   procedure Next(Container: Map; Position: in out Cursor);
   
   function Previous(Position: Cursor) return Cursor;
   function Previous(Container: Map; Position: Cursor) return Cursor;

   procedure Previous(                Position: in out Cursor);
   procedure Previous(Container: Map; Position: in out Cursor);
   
   function Find    (Container: Map; Key: Key_Type) return Cursor;
   function Element (Container: Map; Key: Key_Type) return Element_Type;
   function Floor   (Container: Map; Key: Key_Type) return Cursor;
   function Ceiling (Container: Map; Key: Key_Type) return Cursor;
   function Contains(Container: Map; Key: Key_Type) return Boolean;

   function "<"(Left, Right: Cursor)           return Boolean;
   function ">"(Left, Right: Cursor)           return Boolean;
   function "<"(Left: Cursor; Right: Key_Type) return Boolean;
   function ">"(Left: Cursor; Right: Key_Type) return Boolean;
   function "<"(Left: Key_Type; Right: Cursor) return Boolean;
   function ">"(Left: Key_Type; Right: Cursor) return Boolean;

   procedure Iterate        (Container: Map; Process: not null access procedure(Position: Cursor));
   procedure Reverse_Iterate(Container: Map; Process: not null access procedure(Position: Cursor));
   function  Iterate(Container: Map) return Map_Iterator_Interfaces.Parallel_Reversible_Iterator'Class;
   function  Iterate(Container: Map; Start: Cursor) return Map_Iterator_Interfaces.Reversible_Iterator'Class;

   package Stable is
      type Map(Base: not null access Ordered_Maps.Map) is tagged limited private;
      type Cursor is private;

      Empty_Map : constant Map;
      No_Element: constant Cursor;

      function Has_Element(Position: Cursor) return Boolean;

      package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);

      procedure Assign(Target: in out Ordered_Maps.Map; Source: Map);

      function Copy(Source: Ordered_Maps.Map) return Map;

      type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
      type Reference_Type         (Element: not null access          Element_Type) is private;
   end Stable;
end Ada.Containers.Ordered_Maps;

Bounded Ordered Map

The language-defined generic package Containers.Bounded_Ordered_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Ordered_Maps (see A.18.6), with the difference that the maximum storage is bounded.

Containers.Bounded_Ordered_Maps

type Map(Capacity: Count_Type) is tagged private;

Bounded (Run-Time) Errors

It is a bounded error to assign from a bounded map object while tampering with elements [or cursors] of that object is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object prohibiting tampering with elements [or cursors], or execution proceeds normally.

Erroneous Execution

When a bounded map object M is finalized, if tampering with cursors is prohibited for M other than due to an assignment from another map, then execution is erroneous.

Indefinite Hashed Maps

The language-defined generic package Containers.Indefinite_Hashed_Maps provides a map with the same operations as the package Containers.Hashed_Maps (see A.18.5), with the difference that the generic formal types Key_Type and Element_Type are indefinite.

Omitted Subprograms

procedure Insert(Container: in out Map;
                 Key      : Key_Type;
                 Position : out Cursor;
                 Inserted : out Boolean);

Indefinite Ordered Maps

The language-defined generic package Containers.Indefinite_Ordered_Maps provides a map with the same operations as the package Containers.Ordered_Maps (see A.18.6), with the difference that the generic formal types Key_Type and Element_Type are indefinite.

Omitted Subprograms

procedure Insert(Container: in out Map;
                 Key      : Key_Type;
                 Position : out Cursor;
                 Inserted : out Boolean);

Bounded Hash Maps

The language-defined generic package Containers.Bounded_Hashed_Maps provides a private type Map and a set of operations. It provides the same operations as the package Containers.Hashed_Maps (see A.18.5), with the difference that the maximum storage is bounded.

Containers.Bounded_Hashed_Maps

type Map(Capacity: Count_Type; Modulus: Hash_Type) is tagged private;
-- ...

Bounded (Run-Time) Errors

It is a bounded error to assign from a bounded map object while tampering with elements [or cursors] of that object is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object prohibiting tampering with elements [or cursors], or execution proceeds normally.

Erroneous Execution

When a bounded map object M is finalized, if tampering with cursors is prohibited for M other than due to an assignment from another map, then execution is erroneous.