STL의 성능은 1. 어떤 태플릿라이브러리를 쓰느냐. 2. 사용자가 어떻게 쓰느냐에 따라서달라집니다.

1.은 구현의 문제, 즉 알고리즘의 차이입니다. 보통set은  tree구조인데 어떤 트리냐 등등의 차이죠.

2. 사용자가 어떻게 쓰느냐인데, 이는 STL의 컨테이너는 Allocator를 포함하고 다분히 메모리를 낭비하거나 재할당/복사하는 경우가 많기 때문입니다 .이는 1번과도 연계되서 종종 이슈가 됩니다.

우선 std set의 성능은 hash_set에 비해서 이론적으로는 Ln vs 1 정도로 떨어지지만 경험적으로는 그정도 차이가 나지는 않습니다.

따라서, 기본적으로 set을 정확히 어떻게 사용했는지를 알지 못하면 답변을 드리기 어려운 면이 있습니다. :-)

앗, 벌써 해결 보셨군요. 일단 VS계열이 사용하는 std stl보다는 stlport를 써보세요.

그리고 의사코드 상으로는 특별히 느려질만한 부분으로는 제외한 부분집합이라는 부분 뿐인데요.

vs std stl과 stlport가 ptr을 다루는 부분부터 많이 달라서요. vs std stl은 조심해서 쓰지 않으면 많은 패널티가 있습니다.

심지어 find 처럼 단순한 함수더라도 set은 어떤 자료형을 어떻게 쓰냐에 따라서 기복이 심하거든요 =_=

Debug 모드로 컴파일하신거 아닌가요? VC의 STL이 느린편이긴 해도 저 정도는 아닌데 말이죠. 전세계 유수의 계산 프로그램들이 VC의 STL로 컴파일해서 사용중입니다. 나름대로 최적화 노하우가 필요하긴 해도 그렇게까지 느리진 않아요.

특히 VC의  STL을 Debug 모드로 컴파일하면 모든 Debug 옵션이 전부 다 켜지기 때문에 엄청나게 느려집니다.  Release 모드에서는 #define _SECURE_SCL 0 을강제로 해주는게 좋습니다. 

http://sweeper.egloos.com/2819872 참고하세요~ 저 글에서는 성능향상이 미미하다고 나와있는데, 제 경험상으로는 코드마다 많이 달랐습니다. 실제로 효과가 아주 큰 경우도 자주 보입니다.

컴파일러라는게 참 애매한게, Intel 컴파일러가 참 좋기로 많이 알려져있는데 이게 꼭 빠른것만은 아니더라는겁니다. 사실 그거 얼마 하지도 않는데 왜 다들 안사서 쓰겠어요. 요즘은 그냥 설치하고 VS에서 메뉴에서 한번 뚝 눌러주기만 하면 자동으로 다 알아서 해주기까지 하거든요.

그런데 코드에 따라서 어떤 경우엔 빨라지고 어떤 경우엔 그대로고 어떤 경우엔 아예 느려지기까지 합니다. ;;; 게다가 소숫점 대빵 많이 들어간 연산의 경우 SSE를 사용하다가 round robin의 문제로 답이 달라지기까지 합니다.!!! 아주 곤란해지죠. 거기다 MultiThread로 개발을 하다보면 Thread간의 미묘한 조율때문에 단순히 한군데서 빨라진다고 성능이 향상된다고 볼수가 없어집니다. 보통 성능이 빨라진다는건 그 순간에 그 로직이 CPU를 더 많이 사용한다는걸 의미하거든요. 

말씀하신것처럼 최적화 옵션이라고 해서 꼭 빨라지는게 아닌것도 같은 이유입니다. 결국 속도도 속도지만 그 컴파일러에 가장 맞는 코드를 만들었는가가 결국은 더 중요해집니다. 

아.. 참고로 성능때문이시라면 map은 쓰지 마세요~ map은 검색을 위해 만들어진거라 요소가 추가/삭제될때마다 sorting을 해대거든요. 속도에선 쥐약입니다. hash_map을 쓰라고들 많이 이야기되는데, 그것도 별루이고 STL 표준도 아닙니다. :(

midday님이 얘기하신 #define _SECURE_SCL 0 은 vs2005이후 더블체크와 릴리즈모드 체크로 인한 문제로 많이들 쓰긴 하는데요.

사실 전 권하진 않습니다. 경험적으로 이게 퍼포먼스에서 큰 효과를 보는 경우가 드믑니다. 짧은 데이터로는 2~3배차이난다고 하지만 릴리즈모드에서는 평균 10% 안쪽이고 컨테이너와 아이템 종류와 양에 따라서는 0.0x% 정도 차이정도 안 보이기도 합니다. 한마디로 iterator를 어디서 어떻게 쓰는지 코딩습관만 고쳐도 차이가 확 날수도 미미할 수도 있다는 얘깁니다.(앞서 얘기한 set의 find를 조심하라고 한 부분은 자료형에도 문제가 있지만 예상하셨다 시피 iterator로 전체를 검사하기 때문에 SECURE_SCL 이 퍼포먼스를 갉아먹는 것으로도 대표적 예입니다. 하지만 이는 습관적으로 find를 안쓰면 차이가 미미해지죠.)

게다가 결정적으로 _SECURE_SCL 값에 따라서 외부라이브러리를 못 쓸 수도 있고 보안관련 옵션이 다 꺼져버립니다. 실제로 상용라입중 STL을 사용하면 _SECURE_SCL을 거의 켜놓고 제공합니다. exploit에 대한 모든 secure옵션을 다 꺼버리기 때문에 당연히 키고 제공을 하는데요.

이럴 경우 라입쪽에 무조건 맞춰야만 쓸 수 있고, 모듈별로 혼용이 불가능합니다. 게다가 크러쉬덤프에서도 문제가 있기도하고요.

문제는 사용자들은 퍼포먼스 때문에 _SECURE_SCL 을 끄기를 원하고, 실제로 언제부터인가 이게 유행이 되버렸습니다.

뭐 당연하지만 퍼포먼스에 목매는 것은 개발자의 첫번째 덕목이니까요. 문제는 보안이라서 이제는 퍼포먼스 vs 보안의 경중을 가려야 한다는 것인데요. 다 꺼버리면 exploit에 대처하는 방법이 전무하니 그거도 문제고요.

안그래도 STL 세미나에서 secure쪽에 대한 말들이 많아서 VS2010에서는 unchecked type 을 따로 제공합니다.

#ifndef UNCHECKED
    #define ITERATOR std::list<int>::iterator
    #define BEGIN_OF(p) p.begin()
    #define END_OF(p)  p.end()
#else
    #define ITERATOR std::list<int>::iterator::_Unchecked_type
    #define BEGIN_OF(p) p.begin()._Unchecked()
    #define END_OF(p)  p.end()._Unchecked()
#endif

int _tmain(int argc, _TCHAR* argv[])
{
    std::list<int> l;
    l.push_back(10);
    l.push_back(9);
    l.push_back(8);
    l.push_back(7);

    ITERATOR iter = BEGIN_OF(l);

    while( iter != END_OF(l) )
    {
        printf( "%d\n" , *iter ) ;
        iter++;
    }

    return 0;
}

간단한 샘플인데 어떻게 동작하시는지 금방 아실겁니다.

코드는 구리지만 이렇게 해서 퍼포먼스가 정말 중요한 부분만 빼시고, 나머지는 그대로 SECURE_SCL을 on으로 두시는게 좋습니다.