Restructuring nested maps I am in the process of making an assembler and one of the needed steps is actually getting the opcode from a table. However, the instruction set I'm working on has a handful of different addressing modes which give different opcodes. On top of that, even if you have the same mode the parameter size changes the opcode as well. This means to get an opcode I need to provide an instruction, an addressing mode, and a size. I also need to be able to get the average size for an addressing mode for setting an estimated size for another portion of my code.

My first solution was to make a large map to hold all the values. This has turned into a 200+ line triple-nested map. Something like this:

// &lt;Instruction, &lt;Addressing Mode, &lt;Size, Opcode&gt;&gt;&gt;
std::map&lt;std::string, std::map&lt;AddressMode, std::map&lt;int, int&gt;&gt;&gt; OpcodeTable = {
  {"ADC", {{Indirect_X, {{2, 0x61}}},
          {Stack, {{2, 0x63}}},
          {Direct, {{2, 0x65}, {3, 0x6D}, {4, 0x6F}}},
          {Indirect_Long, {{2, 0x67}}},
          {Immediate, {{2, 0x69}}},
          {Indirect_Y, {{2, 0x71}}},
          {Indirect, {{2, 0x72}}},
          {Stack_Y, {{2, 0x73}}},
          {Indexed_X, {{2, 0x75}, {3, 0x7D}, {4, 0x7F}}},
          {Indirect_Long_Y, {{2, 0x77}}},
          {Indexed_Y, {{3, 0x79}}}}},
   // and so on for every instruction
};


Currently I access this table through a function called get_opcode which hides the ugliness of navigating this map.

// Checks whether a given value exists in the table or not
bool has_opcode(std::string&amp; instr, AddressMode&amp; mode, int size)
{
  return (detail::OpcodeTable[instr].count(mode) == 1) &amp;&amp;
         (detail::OpcodeTable[instr][mode].count(size) == 1);
}

uint8_t get_opcode(std::string&amp; instr, AddressMode&amp; mode, int size)
{
  if (has_opcode(instr, mode, size))
  {
    return detail::OpcodeTable[instr][mode][size];
  }

  // If an invalid instruction is found, throw an exception with details on what it found.
  throw InvalidInstructionException(
          "Invalid instruction: " + instr +
          " with size " + util::to_string(size) +
          " and mode " + AddressModeString[mode] +
          " does not exist.");
}


I have seen ideas for using a pair as a key, and that helps slightly. It effectively turns into this, but I am not sure if this is a notable improvement.

std::map&lt;std::pair&lt;std::string, AddressMode&gt;, std::map&lt;int, int&gt;&gt; OpcodeTable = {
  {{"ADC", Indirect_X}, {{2, 0x61}}},
  {{"ADC", Stack}, {{2, 0x63}}},
  {{"ADC", Direct}, {{2, 0x65}, {3, 0x6D}, {4, 0x6F}}},
  {{"ADC", Indirect_Long}, {{2, 0x67}}},
  {{"ADC", Immediate}, {{2, 0x69}}},
  {{"ADC", Indirect_Y}, {{2, 0x71}}},
  {{"ADC", Indirect}, {{2, 0x72}}},
  {{"ADC", Stack_Y}, {{2, 0x73}}},
  {{"ADC", Indexed_X}, {{2, 0x75}, {3, 0x7D}, {4, 0x7F}}},
  {{"ADC", Indirect_Long_Y}, {{2, 0x77}}},
  {{"ADC", Indexed_Y}, {{3, 0x79}}},
  // and so on for every instruction
};


Is there any cleaner way to structure this data? I don't need to avoid maps entirely, but I feel like I might have gone overboard with this setup.
Take your "pair" version to its logical conclusion:

using Mnemonic = std::string;
enum AddressMode { /* ... */ };
using Size = int;
using InstructionDescription = std::tuple&lt;Mnemonic, AddressMode, Size&gt;;
using Opcode = uint8_t;
std::map&lt;InstructionDescription, Opcode&gt; OpcodeTable = {
    {{"ADC", Indirect_X, 2},    0x61 },
    {{"ADC", Stack, 2},         0x63 },
    {{"ADC", Direct, 2},        0x65 },
    {{"ADC", Indirect_Long, 2}, 0x67 },
    {{"ADC", Immediate, 2},     0x69 },
    {{"ADC", Direct, 3},        0x6D },
    {{"ADC", Direct, 4},        0x6F },
    {{"ADC", Indirect_Y, 2},    0x71 },
    {{"ADC", Indirect, 2},      0x72 },
    {{"ADC", Stack_Y, 2},       0x73 },
    // ...
};


There will only be 256 rows in this table, so it's totally manageable.

Or, do what real assembler-writers do: read the instruction set specification to learn how the bits of the opcode correspond to the meaning of the instruction, and then turn that into a short mathematical formula instead of a huge lookup table.

For example:

enum AddressMode : uint8_t {
    Indirect_X = 0x01,
    Stack = 0x03,
    Direct = 0x05,
    Indirect_Long = 0x07,
    Immediate = 0x09,
    Indirect_Y = 0x11,
    Indirect = 0x12,
    Stack_Y = 0x13,
    // ...
};

Opcode get_opcode(Mnemonic instr, AddressMode mode, Size size)
{
    if (instr == "ADC") {
        unsigned size_mask = (size == 2) ? 0 : (size == 3) ? 8 : 10;
        return 0x60 + int(mode) + size_mask;
    } else if // ...
}



  I'd think having to search all the instructions every time (up to 3 times per instruction based on optimizations) instead of an O(1) lookup seems like it may increase the time taken to assemble the code which may be over 100k lines in some tests, but I don't have any data to back that up.


Lookups in a std::map are not \$O(1)\$; they're \$O(\log n)\$ and involve a ton of pointer traversals. Doing the same \$O(\log n)\$ operations on a sorted array (which is going to be contiguous in memory, therefore cache-friendly) will be faster — probably even faster than using some actually "\$O(1)\$" (cough handwave cough) yet still cache-unfriendly container such as std::unordered_map.

Anyway, my second code example above is what you'll want to do if you really need the speed (which I'm sure you don't). Simple arithmetic operations will always be lightning-fast compared to any kind of container lookup. But at some point, probably long before any of this starts mattering, the real performance bottleneck will be in how fast you can read that 100K of assembly code off the filesystem and how fast you can write the machine code back out. The code that turns mnemonics into opcodes isn't the bottleneck; I guarantee it.