¿Qué estructura de datos usar para ordenar estos datos en PL/SQL?

Es muy fácil si usa PL/SQL como SQL y no como otros lenguajes. Es bastante específico y, a veces, es muy agradable precisamente por eso.

A veces realmente odio PL/SQL, pero este caso se trata absolutamente de amor.

Mira lo fácil que es:

create type it as object (
  iter          number,
  stringval     varchar2(100),
  intval        integer
);

create type t_it as table of it;

declare
  t       t_it := new t_it();
  tmp1    varchar2(32767);
  tmp2    varchar2(32767);
begin
  t.extend(4);
  t(1) := new it(1,'Oslo',40);
  t(2) := new it(2,'Berlin',74);
  t(3) := new it(3,'Rome',25);
  t(4) := new it(4,'Paris',10);

  select listagg(stringval,', ') within group (order by stringval),
         listagg(stringval,', ') within group (order by intval)
  into tmp1, tmp2
  from table(t);

  dbms_output.put_line(tmp1);
  dbms_output.put_line(tmp2);
end;
/

drop type t_it;
drop type it;

Aquí puedes ver el problema de que debes crear tipos globales, y esto es por lo que lo odio. Pero dicen que en Oracle 12 se puede hacer con tipos definidos localmente, así que lo estoy esperando :)

La salida es:

Berlin, Oslo, Paris, Rome
Paris, Rome, Oslo, Berlin

EDITAR

En la medida en que no sepa la cantidad de iteraciones desde el principio, la única forma es extender en cada iteración (este es solo un ejemplo de extensión):

declare
  iterator       pls_integer := 1;
begin
  /* some type of loop*/ loop
    t.extend();

    -- one way to assign
    t(t.last) := new it(1,'Oslo',40);

    -- another way is to use some integer iterator
    t(iterator) := new it(1,'Oslo',40);

    iterator := iterator + 1;
  end loop;
end;

Prefiero la segunda forma porque es más rápida (no calcula .last en cada iteración).