Ordered by insertion Map in bash

Question

Is there an ordered (by insertion) map in bash?

I know there's an associative array data structure in bash, but when iterating over it, the order of the elements is not by insertion. Example below.

I'd like to keep the map ordered by insertion.

Associative array not preserving insertion order:

declare -A REPLACE_MAP
REPLACE_MAP['b']='2'
REPLACE_MAP['a']='1'
for key in "${!REPLACE_MAP[@]}"; do
    echo "$key - ${REPLACE_MAP["$key"]}"
    value=${REPLACE_MAP["$key"]}
done

Result:

a - 1
b - 2

I'd like a data structure that will yield the following result:

b - 2
a - 1

Answer 1

As Michael Vehrs said, bash's associative arrays do not preserve insertion ordering. This is a "feature" of associative arrays in general. The "magic" for this in bash happens in hashlib.c.

Bash does have indexed arrays, which you could use as an indicator for the insertion order:

declare -A REPLACE_MAP
declare -a REPLACE_MAP_INDEX
REPLACE_MAP['b']='2'
REPLACE_MAP_INDEX+=('b')
REPLACE_MAP['a']='1'
REPLACE_MAP_INDEX+=('a')
for key in "${REPLACE_MAP_INDEX[@]}"; do
    printf "%s - %s\n" "$key" "${REPLACE_MAP["$key"]}"
    value=${REPLACE_MAP["$key"]}
done

Another option, depending on your data, is a single indexed array whose values are the original key and value combined in some way (here, using a space):

unset arr
declare -a arr
arr+=("b 2")
arr+=("a 1")
for ckey in "${arr[@]}"; do
  key=${ckey% *}
  value=${ckey#* }
  printf "%s - %s\n" "$key" "$value"
done

... but if space is a valid part of a key or a value, then pick something else that's unused, such as a pipe symbol for example:

unset arr
declare -a arr
arr+=("b|2")
arr+=("a|1")
for ckey in "${arr[@]}"; do
  key=${ckey%|*}
  value=${ckey#*|}
  printf "%s - %s\n" "$key" "$value"
done