…
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; } };
문자열(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;
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에 나와있었던 걸로 기억하는데, 자꾸 착각이 되어서 기록해둔다.
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());
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 등에도 적용할 수 있다.
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; }