사용자 도구

사이트 도구


kb:cppsnippetscontainerandalgorithm

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:cppsnippetscontainerandalgorithm [2014/11/15 10:29] (현재)
줄 1: 줄 1:
 +{{INLINETOC}}
 +\\
 +
 +====== C++ / Snippets / Container & Algorithm ======
 +...
 +
 +====== 대소문자 구분하지 않는 string 기반의 set/map을 위한 함수자 ======
 +<code cpp>
 +struct LexLess
 +{
 +    bool operator(const char* lhs, const char* rhs) const
 +    {
 +        return CompareStringA(LOCALE_USER_DEFAULT,​ NORM_IGNORECASE,​ lhs, -1, rhs, -1) == CSTR_LESS_THAN;​
 +    }
 +    ​
 +    bool operator(const wchar_t* lhs, const wchar_t* rhs) const
 +    {
 +        return CompareStringW(LOCALE_USER_DEFAULT,​ NORM_IGNORECASE,​ lhs, -1, rhs, -1) == CSTR_LESS_THAN;​
 +    }
 +
 +    bool operator(const std::​string&​ lhs, const std::​string&​ rhs) const
 +    {
 +        return CompareStringA(LOCALE_USER_DEFAULT,​ NORM_IGNORECASE,​ lhs, -1, rhs, -1) == CSTR_LESS_THAN;​
 +    }
 +    ​
 +    bool operator(const std::​wstring&​ lhs, const std::​wstring&​ rhs) const
 +    {
 +        return CompareStringW(LOCALE_USER_DEFAULT,​ NORM_IGNORECASE,​ lhs, -1, rhs, -1) == CSTR_LESS_THAN;​
 +    }
 +};
 +</​code>​
 +
 +====== 문자열을 키로 쓰는 set/map 성능 향상시키기 ======
 +문자열(std::​string)을 키로 가지는 맵 같은 경우, 문자열 비교 자체에 걸리는 시간 때문에 검색이 느려질 수 있다. 이 경우, 키로 사용하는 문자열이 별로 중요한 내용이 아니라면 아래와 같은 클래스를 사용함으로서 성능을 약간 증가시킬 수 있다.
 +<code cpp>
 +////////////////////////////////////////////////////////////////////////////////​
 +/// \class cStringKey
 +/// \brief STL 컨테이너를 위한 문자열 키
 +////////////////////////////////////////////////////////////////////////////////​
 +
 +class cStringKey
 +{
 +private:
 +    enum
 +    {
 +        BYTE_SIZE = 32,
 +    };
 +
 +    char m_Text[BYTE_SIZE];​ ///< 문자열
 +
 +
 +public:
 +    /// \brief 생성자
 +    cStringKey()
 +    {
 +        memset(m_Text,​ 0, sizeof(m_Text));​
 +    }
 +
 +    /// \brief 생성자
 +    cStringKey(const char* text)
 +    {
 +        memset(m_Text,​ 0, sizeof(m_Text));​
 +        memcpy_s(m_Text,​ sizeof(m_Text),​ text, std::​min(sizeof(m_Text),​ strlen(text)));​
 +    }
 +
 +    /// \brief 생성자
 +    cStringKey(const std::​string&​ text)
 +    {
 +        memset(m_Text,​ 0, sizeof(m_Text));​
 +        memcpy_s(m_Text,​ sizeof(m_Text),​ text.c_str(),​ std::​min(sizeof(m_Text),​ text.size()));​
 +    }
 +
 +    /// \brief 복사 생성자
 +    cStringKey(const cStringKey&​ rhs)
 +    {
 +        memcpy_s(m_Text,​ sizeof(m_Text),​ rhs.m_Text, sizeof(m_Text));​
 +    }
 +
 +
 +public:
 +    /// \brief 대입 연산자
 +    inline const cStringKey&​ operator = (const cStringKey&​ rhs)
 +    {
 +        if (this != &rhs)
 +            memcpy_s(m_Text,​ sizeof(m_Text),​ rhs.m_Text, sizeof(m_Text));​
 +
 +        return *this;
 +    }
 +
 +    /// \brief 비교 연산자
 +    ///
 +    /// 이 함수는 약간 유의해야 하는데, 속도를 위해 루프를 풀어버렸기 때문이다.
 +    /// 클래스의 크기가 변경되면,​ 이 함수도 같이 변경해줘야 한다.
 +    inline bool operator < (const cStringKey&​ rhs) const
 +    {
 +        const int* buf1 = reinterpret_cast<​const int*>​(this);​
 +        const int* buf2 = reinterpret_cast<​const int*>​(&​rhs);​
 +
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 0-3
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 4-7
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 8-11
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 12-15
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 16-19
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 20-23
 +
 +        ++buf1; ++buf2;
 +        if (*buf1 != *buf2) return *buf1 < *buf2; // 24-27
 +
 +        ++buf1; ++buf2;
 +        return *buf1 < *buf2; // 28-31
 +    }
 +};
 +</​code>​
 +
 +대소문자 구별없이 비교를 할 수 없다는 점이 좀 아쉽다. 어셈블리도 좀 안다면 비교 연산자를 좀 더 깔끔하게 만들 수 있을 텐데. 어쨌든 테스트해보니,​ 릴리즈 빌드에서 약 25~33% 정도의 성능이 향상되었다.
 +
 +<code cpp>
 +typedef std::​map<​std::​string,​ std::​string>​ OLD_MAP;
 +typedef std::​map<​cStringKey,​ std::​string>​ NEW_MAP;
 +
 +OLD_MAP oldMap;
 +NEW_MAP newMap;
 +
 +for (int i=0; i<1000; ++i)
 +{
 +    std::string key = generic::​to_string(rand() % 1000, 4);
 +    std::string value = generic::​to_string(rand() % 1000, 4);
 +    oldMap.insert(OLD_MAP::​value_type(key,​ value));
 +    newMap.insert(NEW_MAP::​value_type(key,​ value));
 +}
 +
 +DWORD begin = 0, oldTime = 0, newTime = 0;
 +int repetition = 200000;
 +
 +begin = timeGetTime();​
 +for (int i=0; i<​repetition;​ ++i)
 +{
 +    oldMap.find(generic::​to_string(rand() % 1000, 4));
 +}
 +oldTime = timeGetTime() - begin;
 +
 +begin = timeGetTime();​
 +for (int i=0; i<​repetition;​ ++i)
 +{
 +    newMap.find(generic::​to_string(rand() % 1000, 4));
 +}
 +newTime = timeGetTime() - begin;
 +
 +std::cout << "OLD: " << oldTime << std::endl;
 +std::cout << "NEW: " << newTime << std::endl;
 +</​code>​
 +
 +====== map/​multimap -> vector/list 변환 ======
 +<code cpp>
 +template <​typename I, typename C>
 +inline void make_sequence(const I& first, const I& last, C& container)
 +{
 +    std::​back_insert_iterator<​C>​ inserter(container);​
 +    for (I itr(first); itr != last; ++itr, ++inserter)
 +        *inserter = itr->​second;​
 +}
 +</​code>​
 +
 +<code cpp>
 +std::​map<​int,​ int> myMap;
 +myMap[0] = 0;
 +myMap[1] = 1;
 +myMap[2] = 2
 +myMap[3] = 3
 +
 +std::​vector<​int>​ myVector;
 +make_sequence(myMap.begin(),​ myMap.end(),​ myVector);
 +</​code>​
 +
 +더 나은 방법이 있을 것도 같은데, 못 찾겠다. 약간 응용해보면 이런 것도 있을 수 있겠다.
 +
 +<code cpp>
 +template <​typename I, typename C>
 +inline void make_sorted_sequence(const I& first, const I& last, C& container)
 +{
 +    std::​back_insert_iterator<​C>​ inserter(container);​
 +    for (I itr(first); itr != last; ++itr, ++inserter)
 +        *inserter = itr->​second;​
 +
 +    std::​sort(container.begin(),​ container.end());​
 +}
 +
 +template <​typename I, typename C, typename P>
 +inline void make_sorted_sequence(const I& first, const I& last, C& container, P comp)
 +{
 +    std::​back_insert_iterator<​C>​ inserter(container);​
 +    for (I itr(first); itr != last; ++itr, ++inserter)
 +        *inserter = itr->​second;​
 +
 +    std::​sort(container.begin(),​ container.end(),​ comp);
 +}
 +</​code>​
 +일반 배열도 사용하려면 컨테이너의 begin, end를 인자로 받아야 한다. 지저분해서 싫은데 어떡하지.
 +
 +
 +====== 컬렉션을 횡단하며 객체 삭제하기 ======
 +Effective STL에 나와있었던 걸로 기억하는데,​ 자꾸 착각이 되어서 기록해둔다. ​
 +
 +===== 순차형(sequential) 컬렉션 =====
 +<code cpp>
 +typedef std::​list<​OBJECT>​ OBJECTS;
 +OBJECTS objects;
 +...
 +for (OBJECTS::​iterator itr(objects.begin());​ itr != object.end();​ )
 +{
 +    const OBJECT& object = *itr;
 +
 +    if (should_delete(object))
 +    {
 +        itr = objects.erase(itr);​
 +    }
 +    else
 +    {
 +        ++itr;
 +    }
 +}
 +</​code>​
 +
 +순차형의 경우, remove_if 알고리즘을 이용할 수도 있다.
 +<code cpp>
 +stx::​vector<​int>​ a;
 +a.erase(std::​remove_if(a.begin(),​ a.end(), [](int v) -> bool { return v % 2 == 0; }), a.end());
 +</​code>​
 +
 +
 +===== 연관형(associative) 컬렉션 =====
 +<code cpp>
 +typedef std::​map<​int,​ OBJECT> OBJECTS;
 +OBJECTS objects;
 +...
 +for (OBJECTS::​iterator itr(objects.begin());​ itr != object.end();​ )
 +{
 +    const OBJECT& object = itr->​second;​
 +
 +    if (should_delete(object))
 +    {
 +        objects.erase(itr++);​
 +    }
 +    else 
 +    {
 +        ++itr;
 +    }
 +}
 +</​code>​
 +  ​
 +====== 객체의 리스트를 횡단하면서 멤버 함수 호출하기 ======
 +:!: 람다가 나오면서 다 헛소리가 되어버림.
 +
 +예를 들어 다음과 같은 클래스들이 있다고 하자.
 +<code cpp>
 +class myclass
 +{
 +public:
 +    void heartbeat() { ... }
 +    void set(int param) { ... }
 +};
 +
 +std::​list<​myclass>​ obj_list;
 +std::​list<​myclass*>​ ptr_list;
 +</​code> ​
 +
 +오브젝트 자체로 이루어진 리스트들 돌면서 myclass의 heartbeat 함수를 호출하려면 다음과 같이 한다. ​
 +
 +<code cpp>
 +for_each(obj_list.begin(),​ obj_list.end(),​ mem_fun(&​myclass::​heartbeat));​
 +</​code>​
 +
 +포인터로 이루어진 리스트를 돌면서 myclass의 heartbeat 함수를 호출하려면 다음과 같이 한다.
 +
 +<code cpp>
 +for_each(ptr_list.begin(),​ ptr_list.end(),​ mem_fun<​void,​ myclass>​(&​myclass::​heartbeat));​
 +</​code>​
 +
 +포인터로 이루어진 리스트를 돌면서 myclass의 set 함수를 호출하려면 다음과 같이 한다.
 +
 +<code cpp>
 +for_each(ptr_list.begin(),​ ptr_list.end(),​ bind2nd(mem_fun1<​void,​ myclass, int>​(&​myclass::​heartbeat),​ 99));
 +</​code>​
 +
 +개인적으로는 이 정도까지는 추천하지 않는다. 차라리 for 루프 돌면서 하는 게 관리하기가 편하기 때문이다.
 +
 +당연하지만,​ vector 및 deque 등에도 적용할 수 있다.
 +
 +====== set_intersection 알고리즘의 대안 ======
 +<code cpp>
 +template<​class InputIterator1,​ class InputIterator2,​ class OutputIterator>​
 +   ​OutputIterator set_intersection(
 +      InputIterator1 _First1, ​
 +      InputIterator1 _Last1,
 +      InputIterator2 _First2, ​
 +      InputIterator2 _Last2, ​
 +      OutputIterator _Result
 +   );
 +template<​class InputIterator1,​ class InputIterator2,​ class OutputIterator,​ class BinaryPredicate>​
 +   ​OutputIterator set_intersection(
 +      InputIterator1 _First1, ​
 +      InputIterator1 _Last1,
 +      InputIterator2 _First2, ​
 +      InputIterator2 _Last2, ​
 +      OutputIterator _Result,
 +      BinaryPredicate _Comp
 +   );
 +</​code>​
 +
 +set_intersection 알고리즘은 **정렬된 두 개의 컨테이너에서 교집합을 구하는 알고리즘**인데 쓰기가 좀 뭐하다. 호출시 output_iterator를 넘기는데,​ 이 output_iterator에 해당하는 컨테이너는 호출 전에 최소 교집합의 크기만큼의 공간을 가지고 있어야 하기 때문이다. insert_iterator도 시도해보았으나,​ VisualCpp 7.1에서는 뭔가 에러가 나는 관계로 알고리즘 헤더를 보고 그냥 땜빵으로 알고리즘을 만들었다.
 +
 +<code cpp>
 +template <​typename T>
 +void intersection(const T& c1, const T& c2, T& u)
 +{
 +    T::​const_iterator first1(c1.begin());​
 +    T::​const_iterator last1(c1.end());​
 +    T::​const_iterator first2(c2.begin());​
 +    T::​const_iterator last2(c2.end());​
 +
 +    for (; first1 != last1 && first2 != last2; )
 +    {
 +        if (*first1 < *first2)
 +            ++first1;
 +        else if (*first2 < *first1)
 +            ++first2;
 +        else
 +            u.insert(*first1++),​ ++first2;
 +    }
 +}
 +</​code>​
 +
 +약간 응용하면 교집합을 가지는가의 여부를 반환하는 함수도 만들 수 있다.
 +
 +<code cpp>
 +template <​typename T>
 +bool has_intersection(const T& c1, const T& c2)
 +{
 +    T::​const_iterator first1(c1.begin());​
 +    T::​const_iterator last1(c1.end());​
 +    T::​const_iterator first2(c2.begin());​
 +    T::​const_iterator last2(c2.end());​
 +
 +    for (; first1 != last1 && first2 != last2; )
 +    {
 +        if (*first1 < *first2)
 +            ++first1;
 +        else if (*first2 < *first1)
 +            ++first2;
 +        else
 +            return true;
 +    }
 +
 +    return false;
 +}
 +</​code>​
 +----
 +  * see also [[CppSnippets|C++ Snippets]]
  
kb/cppsnippetscontainerandalgorithm.txt · 마지막으로 수정됨: 2014/11/15 10:29 (바깥 편집)