사용자 도구

사이트 도구

추적: • cppsnippetscontainerandalgorithm
kb:cppsnippetscontainerandalgorithm

목차


C++ / Snippets / Container & Algorithm

…

대소문자 구분하지 않는 string 기반의 set/map을 위한 함수자

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;
    }
};

문자열을 키로 쓰는 set/map 성능 향상시키기

문자열(std::string)을 키로 가지는 맵 같은 경우, 문자열 비교 자체에 걸리는 시간 때문에 검색이 느려질 수 있다. 이 경우, 키로 사용하는 문자열이 별로 중요한 내용이 아니라면 아래와 같은 클래스를 사용함으로서 성능을 약간 증가시킬 수 있다. 

////////////////////////////////////////////////////////////////////////////////
/// \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
    }
};

대소문자 구별없이 비교를 할 수 없다는 점이 좀 아쉽다. 어셈블리도 좀 안다면 비교 연산자를 좀 더 깔끔하게 만들 수 있을 텐데. 어쨌든 테스트해보니, 릴리즈 빌드에서 약 25~33% 정도의 성능이 향상되었다. 

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;

map/multimap -> vector/list 변환

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;
}
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);

더 나은 방법이 있을 것도 같은데, 못 찾겠다. 약간 응용해보면 이런 것도 있을 수 있겠다. 

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);
}

일반 배열도 사용하려면 컨테이너의 begin, end를 인자로 받아야 한다. 지저분해서 싫은데 어떡하지.

컬렉션을 횡단하며 객체 삭제하기

Effective STL에 나와있었던 걸로 기억하는데, 자꾸 착각이 되어서 기록해둔다.

순차형(sequential) 컬렉션

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;
    }
}

순차형의 경우, remove_if 알고리즘을 이용할 수도 있다. 

stx::vector<int> a;
a.erase(std::remove_if(a.begin(), a.end(), [](int v) -> bool { return v % 2 == 0; }), a.end());

연관형(associative) 컬렉션

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;
    }
}

객체의 리스트를 횡단하면서 멤버 함수 호출하기

:!: 람다가 나오면서 다 헛소리가 되어버림.

예를 들어 다음과 같은 클래스들이 있다고 하자. 

class myclass
{
public:
    void heartbeat() { ... }
    void set(int param) { ... }
};
 
std::list<myclass> obj_list;
std::list<myclass*> ptr_list;

오브젝트 자체로 이루어진 리스트들 돌면서 myclass의 heartbeat 함수를 호출하려면 다음과 같이 한다. 

for_each(obj_list.begin(), obj_list.end(), mem_fun(&myclass::heartbeat));

포인터로 이루어진 리스트를 돌면서 myclass의 heartbeat 함수를 호출하려면 다음과 같이 한다. 

for_each(ptr_list.begin(), ptr_list.end(), mem_fun<void, myclass>(&myclass::heartbeat));

포인터로 이루어진 리스트를 돌면서 myclass의 set 함수를 호출하려면 다음과 같이 한다. 

for_each(ptr_list.begin(), ptr_list.end(), bind2nd(mem_fun1<void, myclass, int>(&myclass::heartbeat), 99));

개인적으로는 이 정도까지는 추천하지 않는다. 차라리 for 루프 돌면서 하는 게 관리하기가 편하기 때문이다.

당연하지만, vector 및 deque 등에도 적용할 수 있다.

set_intersection 알고리즘의 대안

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
   );

set_intersection 알고리즘은 정렬된 두 개의 컨테이너에서 교집합을 구하는 알고리즘인데 쓰기가 좀 뭐하다. 호출시 output_iterator를 넘기는데, 이 output_iterator에 해당하는 컨테이너는 호출 전에 최소 교집합의 크기만큼의 공간을 가지고 있어야 하기 때문이다. insert_iterator도 시도해보았으나, VisualCpp 7.1에서는 뭔가 에러가 나는 관계로 알고리즘 헤더를 보고 그냥 땜빵으로 알고리즘을 만들었다. 

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;
    }
}

약간 응용하면 교집합을 가지는가의 여부를 반환하는 함수도 만들 수 있다. 

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;
}
kb/cppsnippetscontainerandalgorithm.txt · 마지막으로 수정됨: 2014/11/15 10:29 (바깥 편집)

문서 도구

별도로 명시하지 않을 경우, 이 위키의 내용은 다음 라이선스에 따라 사용할 수 있습니다: CC Attribution-Share Alike 3.0 Unported
CC Attribution-Share Alike 3.0 Unported Valid HTML5 Valid CSS Driven by DokuWiki