C++vector 의 사 칙 연산 실현

6598 단어 vector사 칙 연산
여기 서 vector 의 연산 을 조작 수 vector 의 같은 위치 에 있 는 요 소 를 연산 하 는 것 으로 정의 하고 마지막 으로 새로운 vector 를 얻 을 수 있 습 니 다.구체 적 으로 말 하면,만약 vectord1{1,2,3},d2{4,5,6};v1+v2 는{5,7,9}과 같다.이러한 연산 을 실현 하 는 것 은 결코 어렵 지 않 아 보인다.매우 직관 적 인 방법 은 다음 과 같다.

vector<int> operator+(const vector<int>& v1, const vector<int>& v2) {
  //    v1.size() == v2.size()
  vector<int> r;

  r.reserve(v1.size());
  for (auto i = 0; i < v1.size(); ++i) {
    r.push_back(v1[i] + v2[i]);
  }
  return r;
}

//같은 이치 로 다른 연산 자 를 다시 불 러 와 야 합 니 다.
우 리 는 vector 에 대해 모든 연산 자 를 다시 불 러 왔 습 니 다.그러면 vector 의 연산 은 일반적인 간단 한 유형 과 다 르 지 않 고 실현 도 직 설 적 입 니 다.그러나 이 직 설 적 인 방법 은 심각 한 문제 가 있 습 니 다.효율 이 높 지 않 습 니 다.효율 이 높 지 않 은 이 유 는 전체 연산 과정 에서 모든 단계 의 연산 이 중간 결 과 를 얻 었 기 때 문 입 니 다.중간 결 과 는 vector 이기 때문에 매번 메모 리 를 분배 해 야 합 니 다.연산 에 참여 하 는 vector 가 비교적 크 고 연산 이 길 면 효율 이 비교적 낮 습 니 다.더 좋 은 방법 이 있 습 니까?
매번 연산 할 때마다 중간 결과 가 발생 하면 효율 문 제 를 초래 할 수 있 으 니 중간 결 과 를 최적화 할 수 있 습 니까?돌 이 켜 보면 이러한 vector 의 가감 곱 하기 곱 하기 는 일반 네 가지 연산 과 큰 차이 가 없습니다.컴 파일 원리 에서 이러한 표현 식 에 대해 값 을 구 하 는 것 은 보통 표현 식 을 나무 로 바 꾼 다음 에 이 나 무 를 옮 겨 다 니 며 마지막 결 과 를 얻 을 수 있 습 니 다.결과 의 계산 은 한꺼번에 이 루어 집 니 다.중간 상 태 를 저장 할 필요 가 없습니다.예 를 들 어 표현 식:v1+v2*v3 에 대해 우 리 는 보통 다음 과 같은 트 리 로 전환 할 수 있 습 니 다.

따라서 값 을 구 하 는 것 은 간단 한 중간 순서 로 옮 겨 다 니 는 것 입 니 다.그러면 우리 의 vector 연산 도 이렇게 할 수 있 습 니까?
표현 식 템 플 릿
중간 결 과 를 없 애 려 면 표현 식 에 대한 값 을 늦 추 는 것 이 관건 입 니 다.그러나 c++는 lazy evaluation 을 지원 하지 않 습 니 다.따라서 표현 식 의 중간 절차 와 상 태 를 가 벼 운 대상 으로 저장 하 는 방법 을 생각해 야 합 니 다.구체 적 으로 표현 식 의 중간 단계 의 조작 수 와 조작 유형 을 패키지 해 야 합 니 다.필요 할 때 이 연산 을 동적 으로 실행 하여 결 과 를 얻 을 수 있 도록 다음 과 같은 클래스 를 정의 해 야 합 니 다.

enum OpType {
  OT_ADD,
  OT_SUB,
  OT_MUL,
  OT_DIV,
};

class VecTmp {
  int type_;
  const vector<int>& op1_;
  const vector<int>& op2_;

public:
  VecTmp(int type, const vector<int>& op1, const vector<int>& op2)
    : type_(type), op1_(op1), op2_(op2) {}

  int operator[](const int i) const {
    switch(type_) {
      case OT_ADD: return op1_[i] + op2_[i];
      case OT_SUB: return op1_[i] - op2_[i];
      case OT_MUL: return op1_[i] * op2_[i];
      case OT_DIV: return op1_[i] / op2_[i];
      default: throw "bad type";
    }
  }
};

이런 종류 가 있 으 면 우 리 는 간단 한 연산 표현 식 의 결 과 를 한 대상 에 봉 할 수 있다.물론,우 리 는 먼저 덧셈 연산 자(및 기타 조작 자)를 다시 불 러 와 야 한다.

VecTmp operator+(const vector<int>& op1, const vector<int>& op2) {
  return VecTmp(OT_ADD, op1, op2);
}
이렇게 되면 v1+v2 에 대해 우 리 는 매우 가 벼 운 Vectmp 대상 을 얻 었 고 이 대상 은 v1+v2 의 결 과 를 쉽게 전환 할 수 있다.그러나 위의 방법 은 v1+v2*v3 와 같은 복잡 한 표현 식 을 처리 할 수 없습니다.v2*v3 는 Vectmp 를 얻 었 습 니 다.그러면 v1+Vectmp 는 어떻게 합 니까?
마찬가지 로 우 리 는 v1+Vectmp 를 가 벼 운 대상 에 넣 어야 하기 때문에 우리 의 Vectmp 에 저 장 된 조작 수도 Vectmp 유형 일 수 있 고 약간 재 귀적 인 맛 이 난다.템 플 릿 을 사용 하면 됩 니 다.그래서 다음 코드 를 얻 을 수 있 습 니 다.

#include <vector>
#include <iostream>

using namespace std;

enum OpType {
  OT_ADD,
  OT_SUB,
  OT_MUL,
  OT_DIV,
};

template<class T1, class T2>
class VecSum {
    OpType type_;
  const T1& op1_;
  const T2& op2_;
 public:
  VecSum(int type, const T1& op1, const T2& op2): type_(type), op1_(op1), op2_(op2) {}
 
    int operator[](const int i) const {
      switch(type_) {
        case OT_ADD: return op1_[i] + op2_[i];
        case OT_SUB: return op1_[i] - op2_[i];
        case OT_MUL: return op1_[i] * op2_[i];
        case OT_DIV: return op1_[i] / op2_[i];
        default: throw "bad type";
      }
    }
};

template<class T1, class T2>
VecSum<T1, T2> operator+(const T1& t1, const T2& t2) {
  return VecSum<T1, T2>(OT_ADD, t1, t2);
}

template<class T1, class T2>
VecSum<T1, T2> operator*(const T1& t1, const T2& t2) {
  return VecSum<T1, T2>(OT_MUL, t1, t2);
}

int main() {
  std::vector<int> v1{1, 2, 3}, v2{4, 5, 6}, v3{7, 8, 9};
  auto r = v1 + v2 * v3;
  for (auto i = 0; i < r.size(); ++i) {
    std::cout << r[i] << " ";
  }
}

위의 코드 는 앞에서 언급 한 효율 문 제 를 예 쁘 게 해결 하고 확장 성도 좋 으 며 vector 에 있어 비 침입 적 입 니 다.비록 실현 에 있어 서 는 언뜻 보기 에는 직관 적 이지 않 을 수도 있 지만 이것 외 에 도 작은 문제 들 이 더욱 완선 할 수 있 습 니 다.
연산 자 리 셋 은 다른 유형 에 영향 을 미 칠 수 있 으 므 로 제한 하 는 것 이 좋 습 니 다.vector 와 Vectmp 만 리 셋 할 수 있 습 니 다.여 기 는 SFINAE 로 처리 할 수 있 습 니 다.VecTmp operator[]함수 중의 switch 는 최적화 할 수 있 습 니 다.Vectmp 템 플 릿 은 하나의 매개 변 수 를 추가 한 다음 에 각종 연산 유형 을 특 화하 면 됩 니 다.VecTmp저 장 된 작업 수 에 대한 요구 가 있 습 니 다.vector 나 Vectmp<>만 있 을 수 있 습 니 다.여기 서도 SFINAE 로 제한 을 강화 하여 잘못 사용 할 때 오류 가 발생 하 는 정 보 를 보기 좋게 해 야 합 니 다.
이제 우 리 는 이 작은 이상 한 코드 를 다시 살 펴 보 겠 습 니 다.분명 관건 은 Vectmp 와 같은 것 입 니 다.우 리 는 그의 인 터 페 이 스 는 간단 하고 직 설 적 이지 만 그 유형 은 그렇게 복잡 할 수 있 습 니 다.예 를 들 어 v1+v2*v3 라 는 표현 식 에 대해 그 결과 의 유형 은 다음 과 같 습 니 다.Vectmp,Vectmp,vector>,표현 식 이 좀 더 복잡 하면 그 유형 도 더욱 복잡 해 집 니 다.자세히 보면 이 물건 이 어디 와 비슷 한 지 알 수 있 습 니까?나무 한 그루,나무 한 그루.

이 나 무 는 아직 낯 이 익 은 것 같 지 않 습 니까?모든 잎 결점 은 vector 이 고 모든 내부 결점 은 Vectmp 에서 예화 되 었 습 니 다.이것 은 유형의 나무 입 니 다.컴 파일 할 때 확 정 됩 니 다.표현 식 을 통 해 컴 파일 할 때 얻 을 수 있 는 복잡 한 유형 은 Expression template 라 는 학 명 이 있 습 니 다.c++에서 모든 표현 식 은 하나의 결 과 를 만들어 야 합 니 다.결 과 는 반드시 유형 이 있 습 니 다.유형 은 컴 파일 할 때의 것 이 고 결 과 는 실 행 될 때 입 니 다.이러한 연산 식 과 같이 그의 최종 유형 은 그 중의 모든 연산 에서 발생 하 는 결과 에 대응 하 는 유형 을 조합 하여 결정 되 며,유형 이 확 정 된 과정 은 표현 식 의 식별 과 일치 합 니 다.
Vectmp 대상 은 논리 적 으로 도 나무 입 니 다.그 구성원 변 수 는 op1 입 니 다.op2_ 각각 좌우 아들 의 결점 이 고 나무의 내부 결점 은 하나의 연산 을 대표 하 며,잎 결점 은 조작 수 이 며,한 번 의 중간 순 서 를 옮 겨 다 니 며 얻 은 것 은 전체 표현 식 의 값 이다.
신기 한 boost::proto
expression template 는 좋 은 것 입 니 다.(expression SFINAE 처럼)컴 파일 할 때 매우 복잡 하고 재 미 있 는 유형 시스템 을 구축 하 는 데 도움 을 줄 수 있 습 니 다.그러나 분명히 모든 것 이 자신 이 처음부터 써 야 한다 면 이 기술 은 사용 하기에 매우 번 거 롭 고 고 통 스 러 울 것 입 니 다.다행히 템 플 릿 원 프로 그래 밍 은 정말 재 미 있 는 것 입 니 다.이미 많은 사람들 이 선구 적 인 일 을 했 습 니 다.boost proto 를 보 세 요.c++의 세계 에서 이상 한 세계 로 가 는 문 을 다시 열 었 습 니 다.

좋은 웹페이지 즐겨찾기