Index: src/natools-constant_indefinite_ordered_maps.adb
==================================================================
--- src/natools-constant_indefinite_ordered_maps.adb
+++ src/natools-constant_indefinite_ordered_maps.adb
@@ -409,10 +409,52 @@
    procedure Clear (Container : in out Constant_Map) is
    begin
       Container.Backend.Reset;
    end Clear;
 
+   function Constant_Reference
+     (Container : aliased in Constant_Map;
+      Position : in Cursor)
+     return Constant_Reference_Type
+   is
+      use type Backend_Refs.Immutable_Reference;
+   begin
+      if Position.Is_Empty then
+         raise Constraint_Error
+           with "Constant_Reference called with empty Position";
+      end if;
+
+      if Container.Backend /= Position.Backend then
+         raise Program_Error with "Constant_Reference called"
+           & " with unrelated Container and Position";
+      end if;
+
+      return
+        (Backend => Container.Backend,
+         Element => Container.Backend.Query.Data.all.Nodes
+                     (Position.Index).Element);
+   end Constant_Reference;
+
+
+   function Constant_Reference
+     (Container : aliased in Constant_Map;
+      Key : in Key_Type)
+     return Constant_Reference_Type
+   is
+      Position : constant Cursor := Container.Find (Key);
+   begin
+      if Position.Is_Empty then
+         raise Constraint_Error
+           with "Constant_Reference called with Key not in map";
+      end if;
+
+      return
+        (Backend => Container.Backend,
+         Element => Container.Backend.Query.Data.Nodes
+                     (Position.Index).Element);
+   end Constant_Reference;
+
 
    function Contains (Container : Constant_Map; Key : Key_Type)
      return Boolean
    is
       Floor, Ceiling : Count_Type;
@@ -514,10 +556,24 @@
          Position.Index := I;
          Process.all (Position);
       end loop;
    end Iterate;
 
+
+   function Iterate (Container : in Constant_Map)
+     return Map_Iterator_Interfaces.Reversible_Iterator'Class is
+   begin
+      return Iterator'(Backend => Container.Backend, Start => No_Element);
+   end Iterate;
+
+
+   function Iterate (Container : in Constant_Map; Start : in Cursor)
+     return Map_Iterator_Interfaces.Reversible_Iterator'Class is
+   begin
+      return Iterator'(Backend => Container.Backend, Start => Start);
+   end Iterate;
+
 
    function Last (Container : Constant_Map) return Cursor is
    begin
       if Container.Is_Empty then
          return No_Element;
@@ -583,10 +639,50 @@
 
 
    ------------------------------
    -- Updatable Map Operations --
    ------------------------------
+
+   function Reference
+     (Container : aliased in out Updatable_Map;
+      Position : in Cursor)
+     return Reference_Type
+   is
+      use type Backend_Refs.Immutable_Reference;
+   begin
+      if Position.Is_Empty then
+         raise Constraint_Error with "Reference called with empty Position";
+      end if;
+
+      if Container.Backend /= Position.Backend then
+         raise Program_Error
+           with "Reference called with unrelated Container and Position";
+      end if;
+
+      return
+        (Backend => Container.Backend,
+         Element => Container.Backend.Query.Data.Nodes
+                     (Position.Index).Element);
+   end Reference;
+
+
+   function Reference
+     (Container : aliased in out Updatable_Map;
+      Key : in Key_Type)
+     return Reference_Type
+   is
+      Position : constant Cursor := Container.Find (Key);
+   begin
+      if Position.Is_Empty then
+         raise Constraint_Error with "Reference called with Key not in map";
+      end if;
+
+      return
+        (Backend => Container.Backend,
+         Element => Container.Backend.Query.Data.Nodes
+                     (Position.Index).Element);
+   end Reference;
 
    procedure Update_Element
      (Container : in out Updatable_Map;
       Position : in Cursor;
       Process : not null access procedure (Key : in Key_Type;
@@ -597,6 +693,39 @@
       Process.all
         (Accessor.Data.Nodes (Position.Index).Key.all,
          Accessor.Data.Nodes (Position.Index).Element.all);
    end Update_Element;
 
+
+
+   -------------------------
+   -- Iterator Operations --
+   -------------------------
+
+   overriding function First (Object : Iterator) return Cursor is
+   begin
+      if Has_Element (Object.Start) then
+         return Object.Start;
+      elsif Object.Backend.Is_Empty then
+         return No_Element;
+      else
+         return (Is_Empty => False,
+            Backend => Object.Backend,
+            Index => 1);
+      end if;
+   end First;
+
+
+   overriding function Last (Object : Iterator) return Cursor is
+   begin
+      if Has_Element (Object.Start) then
+         return Object.Start;
+      elsif Object.Backend.Is_Empty then
+         return No_Element;
+      else
+         return (Is_Empty => False,
+            Backend => Object.Backend,
+            Index => Object.Backend.Query.Data.Size);
+      end if;
+   end Last;
+
 end Natools.Constant_Indefinite_Ordered_Maps;

Index: src/natools-constant_indefinite_ordered_maps.ads
==================================================================
--- src/natools-constant_indefinite_ordered_maps.ads
+++ src/natools-constant_indefinite_ordered_maps.ads
@@ -46,10 +46,11 @@
 -- ordered maps (see ARM A.18.6), except for tampering, which becomes       --
 -- irrelevant.                                                              --
 ------------------------------------------------------------------------------
 
 with Ada.Containers.Indefinite_Ordered_Maps;
+with Ada.Iterator_Interfaces;
 
 private with Ada.Finalization;
 private with Ada.Unchecked_Deallocation;
 private with Natools.References;
 private with Natools.Storage_Pools;
@@ -65,10 +66,11 @@
 
    package Unsafe_Maps is new Ada.Containers.Indefinite_Ordered_Maps
      (Key_Type, Element_Type);
 
    type Cursor is private;  --  with Type_Invariant => Is_Valid (Cursor);
+   pragma Preelaborable_Initialization (Cursor);
 
    No_Element : constant Cursor;
 
    procedure Clear (Position : in out Cursor);
    function Is_Valid (Position : Cursor) return Boolean;
@@ -106,12 +108,21 @@
    function "<" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre => Has_Element (Right) or else raise Constraint_Error;
    function ">" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre => Has_Element (Right) or else raise Constraint_Error;
 
+
+   package Map_Iterator_Interfaces is new Ada.Iterator_Interfaces
+     (Cursor, Has_Element);
+
 
    type Constant_Map is tagged private;
+--   TODO: add aspects when they don't put GNAT in an infinite loop
+--   with Constant_Indexing => Constant_Reference,
+--        Default_Iterator => Iterate,
+--        Iterator_Element => Element_Type;
+   pragma Preelaborable_Initialization (Constant_Map);
 
    procedure Clear (Container : in out Constant_Map);
    function Create (Source : Unsafe_Maps.Map) return Constant_Map;
    procedure Move (Target : in out Constant_Map; Source : in out Constant_Map);
    procedure Replace
@@ -154,21 +165,61 @@
 
    procedure Reverse_Iterate
      (Container : in Constant_Map;
       Process : not null access procedure (Position : in Cursor));
 
+   function Iterate (Container : in Constant_Map)
+     return Map_Iterator_Interfaces.Reversible_Iterator'Class;
+
+   function Iterate (Container : in Constant_Map; Start : in Cursor)
+     return Map_Iterator_Interfaces.Reversible_Iterator'Class;
+
+
+   type Constant_Reference_Type
+     (Element : not null access constant Element_Type) is private
+     with Implicit_Dereference => Element;
+
+   function Constant_Reference
+     (Container : aliased in Constant_Map;
+      Position : in Cursor)
+     return Constant_Reference_Type;
+
+   function Constant_Reference
+     (Container : aliased in Constant_Map;
+      Key : in Key_Type)
+     return Constant_Reference_Type;
+
 
-   type Updatable_Map is new Constant_Map with private;
+   type Updatable_Map is new Constant_Map with private
+     with Constant_Indexing => Constant_Reference,
+          Variable_Indexing => Reference,
+          Default_Iterator => Iterate,
+          Iterator_Element => Element_Type;
+   pragma Preelaborable_Initialization (Updatable_Map);
 
    procedure Update_Element
      (Container : in out Updatable_Map;
       Position : in Cursor;
       Process : not null access procedure (Key : in Key_Type;
                                            Element : in out Element_Type))
      with Pre => (Has_Element (Position) or else raise Constraint_Error)
       and then (Is_Related (Container, Position) or else raise Program_Error);
 
+
+   type Reference_Type (Element : not null access Element_Type) is private
+     with Implicit_Dereference => Element;
+
+   function Reference
+     (Container : aliased in out Updatable_Map;
+      Position : in Cursor)
+     return Reference_Type;
+
+   function Reference
+     (Container : aliased in out Updatable_Map;
+      Key : in Key_Type)
+     return Reference_Type;
+
 
 private
 
    type Key_Access is access Key_Type;
    type Element_Access is access Element_Type;
@@ -256,9 +307,45 @@
      is (not Position.Is_Empty);
 
    function Is_Related (Container : Constant_Map; Position : Cursor)
      return Boolean
      is (Backend_Refs."=" (Container.Backend, Position.Backend));
+
+
+   type Constant_Reference_Type
+     (Element : not null access constant Element_Type)
+   is record
+      Backend : Backend_Refs.Immutable_Reference;
+   end record;
+
+
+   type Reference_Type (Element : not null access Element_Type) is record
+      Backend : Backend_Refs.Immutable_Reference;
+   end record;
+
+
+   type Iterator is new Map_Iterator_Interfaces.Reversible_Iterator with record
+      Backend : Backend_Refs.Immutable_Reference;
+      Start : Cursor := No_Element;
+   end record;
+
+   overriding function First (Object : Iterator) return Cursor;
+   overriding function Last  (Object : Iterator) return Cursor;
+
+   overriding function Next
+     (Object   : Iterator;
+      Position : Cursor) return Cursor
+     is (Next (Position))
+     with Pre => Position.Is_Empty
+        or else Backend_Refs."=" (Position.Backend, Object.Backend);
+
+   overriding function Previous
+     (Object   : Iterator;
+      Position : Cursor) return Cursor
+     is (Previous (Position))
+     with Pre => Position.Is_Empty
+        or else Backend_Refs."=" (Position.Backend, Object.Backend);
+
 
    No_Element : constant Cursor := (Is_Empty => True);
 
 end Natools.Constant_Indefinite_Ordered_Maps;