Search

CPP Module 02

Created
2021/10/08
tag
42서울
42Seoul
CPP Module
All of C++98
Class
Orthodox Canonical Form

Subjects

1. Orthodox Canonical Form Fixed Point Class

Floating Point? Fixed Point? Fixed Point!

ex00 - ex02까지 요구하는 바는 생각보다 간단하다. Fixed 클래스의 생성자와 소멸자를 Orthodox Canonical Form으로 정의하고, 계산을 위한 여러 연산자를 Overloading 하는 것이다. 여기서 문제가 될 수 있는 부분은 현재 float, double과 같은 부동 소수점고정 소수점으로 변환하는 것이다.
고정 소수점은 해당 타입의 정수부와 소수부를 정확히 구분 짓기 때문에 구현이 굉장히 간단하다는 장점이 있지만, 그 표현 범위가 매우 한정적이라는 단점이 있다. 반면에 부동 소수점은 구현은 조금 까다로울 수 있지만, 정수부와 소수부로 나누는 것이 아니라 지수부와 가수부로 나눈 과학적 표기법으로 나타내므로 표현 범위가 넓다는 장점이 있다.
고정 소수점부동 소수점의 표현 방식은 아래 링크를 통해 간단히 파악할 수 있다.
현재 컴퓨터는 부동 소수점을 이용하는데 위 링크 혹은 검색을 통해 찾아본 부동 소수점의 표현법을 어떻게 조작해야 고정 소수점으로 나타낼 지 애매모호 할 수 있다. 부동 소수점으로 나타난 float 혹은 double 값에 대해선 비트 연산이 작동하지 않기 때문에 (물론 타입 캐스팅을 이용하여 강제로 접근을 할 수는 있지만) 부동 소수점으로 나타낸 값 자체가 필요하기 때문에 특별히 무언가를 할 필요는 없다.
float 혹은 double 값이 2 진수로 나타나 있다고 생각해보면, 문제에서 제시한 것처럼 8 비트만 소수점으로 나타내고 싶을 때는 부동 소수점으로 나타난 값에 8 비트만큼 왼쪽으로 쉬프팅 해둔 값을 _fixed_point로 저장해두면 된다. 그리고 필요할 때마다 다시 8 비트만큼 오른쪽으로 쉬프팅 해서 값을 해석하면 된다.
여기에 대해서 2가지 의문이 생길 수 있다. 첫 째는 8 비트만큼 왼쪽으로 쉬프팅하여 값을 늘려서 저장하면 기존 값이 사라질 수 있다는 점이고, 둘 째는 floatdouble같은 부동 소수점 형식은 비트 연산이 동작하지 않는다는 점이다. 첫 째의 경우에는 고정 소수점부동 소수점보다 표현 범위가 작다는 점을 고려해보면 지극히 정상적인 동작이므로 크게 신경쓸 필요 없다. 표현이 안 되는 범위는 고정 소수점으로는 표현이 안 된다고 생각하면 된다. 둘 째의 경우에는 타입 캐스팅을 통해 강제로 비트 연산을 하면 되지 않겠나 싶지만, 부동 소수점고정 소수점처럼 메모리에서 정확히 그 값이 나타난 것이 아니라 지수부가수부로 나뉘므로 타입 캐스팅은 그리 좋은 방식은 아니다. 물론 타입 캐스팅으로 메모리 상에 나타난 값을 직접 해석하여 int 값으로 돌린 뒤에 비트 연산을 해도 되겠지만, 이보다 더 간단한 방식이 있다. 단순히 float 혹은 double 값에 int18 비트만큼 왼쪽으로 쉬프팅 한 값을 곱하면 된다. 이 때 해당 값을 찾아낼 때 정확히 8 비트에 대해서만 남겨두어야 하므로, 곱한 뒤 남은 소수점에 대해서는 roundf로 처리한다.
쉬프팅이 곧 곱셈 혹은 나눗셈과 동일하다는 개념을 이해하면, 위 float 혹은 double 값에 쉬프팅한 값을 곱하는 것이 이해가 될 것이다.
곱한 결과로 _fixed_point를 저장해둔 뒤, toFloat이라는 멤버 함수로 찾을 때는 18 비트만큼 왼쪽으로 쉬프팅한 값을 나누면 roundf를 통해 원래 값에서 정확히 8비트만 남은 값으로 찾아낼 수 있다.
int를 저장하려는 경우에는 직접적인 비트연산을 지원하고 소수점이 없기 때문에 훨씬 더 간단하다. 값 자체를 8 비트만큼 왼쪽으로 쉬프팅하면 되고, 소수점이 없으므로 roundf의 처리는 불필요하다. 값을 찾을 때는 _fixed_point를 오른쪽으로 8 비트만큼 쉬프팅하면 끝이다.

2. Binary Space Partitioning

Reference? Value?

operator+, operator-, operator*, operator/ 와 같은 연산자들은 Fixed 클래스를 반환 하는 것으로 나타나는데, 이를 참조자가 붙은 형태로 반환해도 되지 않을까 하는 의문이 들 수 있다. 결론부터 말하자면, 이는 그리 권장되지 않는다. 예를 들어 Fixed 클래스a, b가 있다고 해보자. a + b를 처리한 결과를 임시로 생성한 Fixed 클래스에 할당하고, 이를 참조자로 반환하면 Dangling Reference 문제에 직면하게 된다. 즉, 반환된 참조자는 이미 해제된 객체가 된다. 따라서 결과적으로 a + b를 수행할 때는 ab 값을 더하여 a를 반환하거나 ba를 더하여 b를 반환해야 Dangling Reference를 피할 수 있다. 다만, 이렇게 되면 a + b + a 혹은 b + a + b 에서 중복된 객체가 이미 바뀐 값으로 적용되어 예기치 못한 결과가 나올 수 있다. 이 때문에 operator+, operator-, operator*, operator/와 같은 연산자들은 값의 복사가 있더라도, 참조자가 아닌 값을 반환하는 것으로 정의하는 것이 낫다.

Operator Overloading

기존에 평가를 위해서 작성해두었던 연산자의 Overloading은 그리 좋은 함수들이 아니다. 여기서 해당되는 연산자들은 참조자 형태로 자기 자신을 반환하지 않는 operator+, operator-, operator*, operator/, operator>, operator<, operator>=, operator<=, operator==, operator!= 와 같은 이항 연산자들에 해당한다. 제시된 함수들은 멤버 함수로써 구현이 되어 있지만, BSP에서는 특별한 언급이 없기 때문에 모두 외부 함수로 빼놓았다. 이유는 교환 법칙 때문이다.
덧셈을 예로 들어보겠다. Fixed 클래스Fixed 클래스 + Fixed 클래스의 경우에는 operator+에 해당하여 잘 동작한다. 그리고 Fixed 클래스 + 리터럴 값의 경우에는 operator+가 잘 동작할 것 같지 않지만, 컴파일러가 최선을 다하여 리터럴 값Fixed 클래스로 바꾸려 하기 때문에 Fixed 클래스생성자를 이용하여 암묵적인 형 변환이 일어나면서 (리터럴 값생성자의 인자로 이용이 될 수 있는 경우) 정상적으로 동작한다. 하지만 리터럴 값 + Fixed 클래스에 대해서는 정상적으로 동작하지 않는 것을 확인할 수 있다. 수치를 대변하는 클래스인 만큼 교환 법칙도 지원을 해야하는데, 그렇지 않다.
리터럴 값 + Fixed 클래스가 정상 동작하지 않는 이유는 간단하다. 리터럴 값은 클래스가 아니기 때문에 클래스에 대한 멤버 함수로 Overloading한 함수 자체가 컴파일러의 후보지에 없다. 따라서 리터럴 값Fixed 클래스 + 리터럴 값의 경우처럼 Fixed 클래스생성자암묵적인 형 변환이 가능하도록 만들려면, Fixed 클래스의 멤버 함수보다는 외부 함수로 정의하는 것이 더 나은 방법이다.
여기서 제시된 이항 연산자들은 Fixed 클래스에 대해서만 이용이 된다고 생각하면 굳이 문제가 되지는 않으므로 외부 함수로 뺄 필요는 없지만, 통상적으로는 멤버 함수로 꼭 정의해야 하는 단항 연산자들과 자기 자신을 반환하는 할당 연산자 등을 제외하면 외부 함수로 빼서 정의하는 것이 낫다는 것을 명심할 필요가 있다.

Const Value Casting

Point 클래스의 두 좌표 xx, yyFixed 클래스로 정의되어 있다. 해당 좌표는 서브젝트에 명시된 대로 const로 정의되는데, Point 클래스 간의 대입이 필요한 경우에는 const로 정의된 xx, yy를 바꿀 수 있어야 한다. 물론 대입을 위한 operator=Overloading 하지 않으면 그만이지만, Orthodox Canonical Form을 위해선 이를 정의하는 것이 맞다. const로 된 값을 바꾸지 못한다고 생각하여 대입 수행을 하지 않고 그대로 this의 참조를 반환하는 경우를 두루 보았는데, C++에서는 const로 된 값을 바꾸는 것이 가능하다.
const로 된 값을 바꾸는 경우가 도대체 어디 있냐고 의문을 가질 수도 있고, 이에 대해서 설계 오류가 아닌가라고 생각할 수도 있다. const로 정의된 값은 가급적 바꾸지 않는 것이 당연하겠지만, 구현체의 맥락 상 const를 갖는 것이 바람직하면서도 반드시 이 값을 바꿔야 하는 경우가 종종 있다. 특히 클래스의 상속 관계에서 해당 경우를 종종 겪을 수 있다.
이와 관련해서 멤버 함수 내에서 멤버 변수를 Write에 이용하지 않는다는 것을 명시적으로 표기하는 const에도 비슷한 사례가 있는데, const로 선언된 멤버 함수 내에서 mutable 키워드를 이용하여 멤버 변수를 Write하는 것이 가능하다. 직접 구현한 Cache에서 멤버 변수를 클래스 보다 먼저 찾는 예를 들 수 있다. 해당 경우에 만일 Cache에서 멤버 변수 값을 찾을 수 없다면, 찾으려는 멤버 변수를 Cache에 기록하여 갱신해야 한다. 이 때는 멤버 변수를 Read만 하는 작업임에도 불구하고 Cache를 갱신해야 되므로 Write가 필요하게 된다. 이와 같은 상황에서 mutable 키워드가 이용되고, 요점은 분명 const여도 const 속성을 무시해야 할 때가 종종 있다는 것이다.
const로 정의된 값을 바꾸기 위해선 const_cast<T>를 이용할 수 있다. const_cast<T>는 변수의 주소를 인자로 받는데, 이는 const로 정의된 변수의 공간 자체를 const가 일시적으로 제거된 형태로 만들기 위해서이다. 물론 반대의 경우처럼 const가 아닌 공간을 const로 만드는 것도 가능하다. 이 때 static_cast<T>와는 달리 타입 변환은 불가능하다는 점에 주의해야 한다. 예를 들어 const int *로 된 공간에서 const를 제거하고 싶다면 const_cast<int *>로만 이용될 수 있다.
int main(void) { const int a = 1; int b; b = static_cast<int>(a); return(0); }
C++
복사
위의 예시가 조금 극단적이긴 하지만 static_cast<T>를 이용하다보면, 일반 변수에 const로 된 값을 변환하면서 이용한 사례를 경험해본적 있을 것이다. 위의 경우도 const가 제거된 것이 아닌가 할 수 있지만, a라는 공간 자체는 static_cast<T>의 호출에도 const 속성은 변하지 않는다. 해당 구문은 b에 할당을 위해 일시적으로 타입만 맞춰준 것에 불과하다. 따라서 a의 값을 바꾸려고 시도하면 컴파일 에러가 발생하는 것을 확인할 수 있고, 이를 포인터로 조작해봐도 결과는 동일하다.
#include <string> #include <iostream> int main(void) { const std::string a = "hi good"; (*(const_cast<std::string *>(&a)))[1] = 'o'; std::cout << a << std::endl; return (0); }
C++
복사
반면에 위와 같은 const_cast<T>를 보면 const_cast<T> 호출과 함께 a의 공간이 일시적으로 const 속성이 제거되어 값이 변경된 것을 확인할 수 있다.
#include <string> #include <iostream> int main(void) { const std::string a = "hi good"; (*(const_cast<std::string *>(&a)))[1] = 'o'; std::cout << a << std::endl; std::string *p = const_cast<std::string *>(&a); // ... Something to do (*p)[0] = 's'; std::cout << *p << std::endl; return (0); }
C++
복사
const_cast<T>const 속성을 제거한 결과는 일시적이라고 했는데, 이를 위 코드처럼 변수에 할당하면서 수명을 연장하는 것도 가능하다.
#include <iostream> int main(void) { // const char *s1 = "hi"; // (const_cast<char *>(s1))[1] = 'o'; // std::cout << s1 << std::endl; const char s2[] = "hi"; (const_cast<char *>(s2))[1] = 'o'; std::cout << s2 << std::endl; return(0); }
C++
복사
const_cast<T>를 사용할 때 주소 값만 이용이 가능하다고 했는데, 이로 인해서 발생할 수 있는 문제가 하나 더 있다. const char *를 이용할 일이 드물긴 하겠지만, 위와 같은 코드처럼 리터럴 영역에 있는 값을 바꾸는 것은 const_cast<T>로도 불가능하다. 제시된 코드의 주석을 풀어도 컴파일이 가능하지만, 실행하게 되면 Bus Error가 발생한다. 따라서 const_cast<T>를 이용하여 그 값을 조작하려는 경우에는 어떤 메모리 레이아웃에 위치하는 값인지 확인하는 습관이 필요하다. 위의 경우에는 const char *가 아닌 const char []와 같은 배열로 이용하면, 스택에 위치한 공간에 대해서 const 속성을 제거하여 이용하게 되므로 값을 수정할 수 있다.
Point& Point::operator=(const Point& p) { if (this != &p) { const_cast<Fixed&>(_x) = p.getX(); const_cast<Fixed&>(_y) = p.getY(); } return (*this); }
C++
복사
const_cast<T>를 잘 응용하면 위와 같이 Point 클래스xx, yy에 대해서도 적절한 operator=Overloading할 수 있다.

CW, CCW by Cross Product

문제에서 요구하는 삼각형 내부에 점이 위치하는지 판별하는 방법은 CW, CCW를 이용하면 된다. CWClockwise로 시계 방향, CCWCounter-Clockwise로 반 시계 방향을 의미한다. 제시된 방향은 2차원 상의 두 벡터에 대해서 Cross Product를 이용하여 각 벡터가 오른쪽에 위치하는지 왼쪽에 위치하는지에 따라 CW인지 CCW인지 판별할 수 있다. 두 벡터의 Cross Product가 양수라면 CCW, 음수라면 CW, 0이라면 평행을 의미한다.
자세한 내용은 아래 링크를 참고하자. 설명이 잘 되어 있다.
두 벡터의 상대적 방향을 결정 짓는 Cross Product를 이용하여 삼각형 내부에 점이 있는지 판별하는 법은 간단하다. Cross Product의 부호를 이용한 상대적 방향 판별은 180°180\degree를 기준으로 CWCCW를 결정되기 때문에, 삼각형 내부의 점은 삼각형의 모든 선분과 비교했을 때 180°180\degree 안에 있으므로 모두 동일한 방향을 이룬다. 이를 이용해볼 수 있도록 삼각형을 이루는 점 AA, BB, CC와 특정 점 PP가 있다고 해보자. AB\overline{AB}BP\overline{BP}, BC\overline{BC}CP\overline{CP}, CA\overline{CA}AP\overline{AP} 간의 상대적 방향을 파악해보면 모두 CW이거나 CCW이어야 점 P가 삼각형의 내부에 있게 된다.
점에 대한 선분을 일관성 있게 두어야 한다. 예를 들어 AB\overline{AB}BP\overline{BP}를 두었다면, BC\overline{BC}에 대해선 BP\overline{BP}가 아닌 CP\overline{CP}를 이용해야 상대적 방향 판별에 일관성이 있다. 위에서 제시된 것과 반대로 AB\overline{AB}AP\overline{AP}, BC\overline{BC}BP\overline{BP}, CA\overline{CA}CP\overline{CP}를 이용할 수도 있다.
Vec operator-(const Point& p1, const Point& p2) { return (Vec(((p1.getX()) - (p2.getX())).toFloat(), (p1.getY() - p2.getY()).toFloat())); } Fixed operator*(const Vec& v1, const Vec& v2) { return (Fixed((v1.getX() * v2.getY()) - v1.getY() * v2.getX())); } bool operator~(const Fixed& f) { return (f > Fixed(0)); }
C++
복사
이 과정에서의 Point 클래스를 이용하게 되는데, Point 클래스간의 Cross Product 및 부호 판별을 특정 연산자로 Overloading하여 사용하면 편하다. 내 경우에는 PointVec과 동일하게 이용할 수 있도록 정의해두었고, Vec을 구하기 쉽게 operator-, Cross Product를 위한 operator*, 부호 판별을 위한 operator~Overloading 하였다.