std :: map이 왜 내 코드를 너무 부 풀리게 만드나요?

Question

최근의 레크리에이션 프로젝트는 brainfuck 인터프리터를 C++로 작성하는 것입니다. 그것은 충분히 직설적 이었지만, 오늘 나는 편집 단계로 그것을 추가하기로 결정했습니다. 궁극적 인 목표는 실행 파일을 만들 수 있지만 지금은 기본적인 최적화입니다. 예를 들어, +++++는 5 개에 대해 1 개의 명령을 하나의 add에 추가하는 식으로 진행됩니다.

잘 작동하는 동안 스트립 된 후 실행 파일의 크기가 9k에서 12k로 감소했습니다. 몇 가지 연구를 한 후 아래 함수가 비난 할 것이라고 결정했습니다. 구체적으로지도입니다. 나는 왜 그런지 이해하지 못한다.

void Brainfuck::compile(const string& input) { 
    map<char, pair<Opcode, int>> instructions { 
     { '<', make_pair(Opcode::MOVL, 1) }, 
     { '>', make_pair(Opcode::MOVR, 1) }, 
     { '+', make_pair(Opcode::INCR, 1) }, 
     { '-', make_pair(Opcode::DECR, 1) }, 
     { '[', make_pair(Opcode::WHILE, 0) }, 
     { ']', make_pair(Opcode::WEND, 0) }, 
     { ',', make_pair(Opcode::INP, 0) }, 
     { '.', make_pair(Opcode::OUTP, 0) }, 
    }; 

    string::const_iterator c = begin(input); 
    while (c != end(input)) { 
     if (instructions.find(*c) != end(instructions)) { 
      auto instruction = instructions[*c]; 
      makeOp(c, instruction.first, instruction.second); 
     } else { 
      c++; 
     } 
    } 
} 

지도의 키는 8 가지 유효한 Brainfuck 작업 중 하나입니다. 함수는 입력 문자열을 통해이 유효한 문자를 찾습니다. 유효하지 않은 문자는 Brainfuck 사양대로 건너 뜁니다. 하나를 찾으면 그 키에 대한 맵 값을 최적화를 수행하는 makeop라는 함수에 전달하고이를 op 구조체로 변환하고이를 인터프리터가 실제로 실행할 명령어 벡터에 추가합니다.

op 구조체에는 두 개의 멤버가 있습니다. Opcode - 8 개의 연산 중 하나를 나타내는 uint8_t와 피연산자를 포함하는 하나의 int를 기반으로하는 범위가 지정된 enum입니다. (더 복잡한 버전은 여러 피연산자가있는 명령어를 가질 수 있습니다.) 위의 +++++ 예제에서 구조체는 Opcode :: INCR과 5를 포함합니다.

따라서 각 맵의 값 엔트리는 Opcode와 피연산자의 수로 구성된 std :: pair이다. 나는 약간의 오버 헤드가 일반적인 데이터 구조에서는 피할 수 없다는 것을 알고 있지만 위의 설명의 단순성을 고려할 때 3k가 약간 과도하다고 생각하지 않습니까?

아니면 내 목표를 효율적으로 달성하기위한 올바른 방법이 아닙니까? 하지만 std :: map이 아니라면 어떤 데이터 구조를 사용해야합니까?

업데이트 : 응답하는 모든 사람에게

감사합니다. 첫째, 내 동기에 대한 몇 마디. 나는 C++을 자주 사용하지 않는다. 그래서 나는 내 지식을 날카롭게 유지할 수있는 레크리에이션 프로젝트를하고 있습니다. 절대적으로 가장 작은 코드 크기를 갖는 것은 예를 들어, 선명도 그러나 그것은 부 풀리는 일이 어떻게 일어나는지를 배우는 것은 나에게 흥미 롭다. 주어진 조언에 따라

는

, 내 기능은 이제 다음과 같습니다

static const int MAXOPS = 8; 

void Brainfuck::compile(const string& input) { 
    array<tuple<char, Opcode, int>, MAXOPS> instructions { 
     make_tuple('<', Opcode::MOVL, 1), 
     make_tuple('>', Opcode::MOVR, 1), 
     make_tuple('+', Opcode::INCR, 1), 
     make_tuple('-', Opcode::DECR, 1), 
     make_tuple('[', Opcode::WHILE, 0), 
     make_tuple(']', Opcode::WEND, 0), 
     make_tuple(',', Opcode::INP, 0), 
     make_tuple('.', Opcode::OUTP, 0), 
    }; 

    string::const_iterator c = begin(input); 
    while (c != end(input)) { 
     auto instruction = find_if(begin(instructions), end(instructions), 
     [&instructions, &c](auto i) { 
      return *c == get<0>(i); 
     }); 

     if (instruction != end(instructions)) { 
      makeOp(c, get<1>(*instruction), get<2>(*instruction)); 
     } else { 
      c++; 
     } 
    } 
} 

나는 다시 컴파일하고 ... 아무 일도하지 않습니다. 맵을 포함하고있는 또 다른 메소드가 있다는 것을 기억했다. (이제 삭제 된?) 응답은 단지 맵의 인스턴스화만으로 코드를 추가 할 수 있다고 제안했다. 그래서 그 맵을 배열로 변경하고 다시 컴파일했다. 이번에는 내 실행 파일 의 삭제 된 크기가 12280에서 91552로 변경되었습니다.

Answer 1

map은 요소를 저장하기 위해 내부적으로 균형 트리를 사용합니다. 균형 잡힌 트리는 빠르지 만 삽입 또는 삭제시 트리의 균형을 다시 잡기 위해 약간의 코드 오버 헤드가 필요합니다. 따라서이 코드의 솔기가 3k이면 합리적입니다.