hash_map + remove_if

프로그래밍 일반에 관한 포럼입니다.

Moderator: 류광

Locked
Reiot
Posts: 133
Joined: 2003-10-16 12:02
Contact:

hash_map + remove_if

Post by Reiot »

find_if 로는 잘 쓰던 함수자를 remove_if 에는 사용할 수 없습니다. 예를 들면

Code: Select all

bool ZeroKey ( const hash_map<int,int>::value_type & v ) 
{
	return v.first==0;
}

hash_map<int,int> h;

find_if( h.begin(), h.end(), ZeroKey );

h.erase( remove_if( h.begin(), h.end(), ZeroKey ), h.end() ); // not compiled

에러 메시지는 다음과 같습니다.

Code: Select all

c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\algorithm(492) : error C2582: 'operator =' 함수는 'std::pair<_Ty1,_Ty2>'에서 사용할 수 없습니다.
        with
        [
            _Ty1=const int,
            _Ty2=int
        ]
        c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\algorithm(522) : 컴파일 중인 함수 템플릿 인스턴스화 '_OutIt std::remove_copy_if<std::_Tree<_Traits>::iterator,_FwdIt,bool(__cdecl *)(const stdext::hash_map<_Kty,_Ty>::value_type &)>(_InIt,_InIt,_OutIt,_Pr)'에 대한 참조를 확인하십시오.
        with
        [
            _OutIt=std::_Tree<std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>>::iterator,
            _Traits=std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>,
            _FwdIt=std::_Tree<std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>>::iterator,
            _Kty=int,
            _Ty=int,
            _InIt=std::_Tree<std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>>::iterator,
            _Pr=bool (__cdecl *)(const stdext::hash_map<int,int>::value_type &)
        ]
        d:\Works\equalto\equalto\equalto.cpp(228) : 컴파일 중인 함수 템플릿 인스턴스화 '_FwdIt std::remove_if<std::_Tree<_Traits>::iterator,bool(__cdecl *)(const stdext::hash_map<_Kty,_Ty>::value_type &)>(_FwdIt,_FwdIt,_Pr)'에 대한 참조를 확인하십시오.
        with
        [
            _FwdIt=std::_Tree<std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>>::iterator,
            _Traits=std::_Tmap_traits<int,int,std::less<int>,std::allocator<std::pair<const int,int>>,false>,
            _Kty=int,
            _Ty=int,
            _Pr=bool (__cdecl *)(const stdext::hash_map<int,int>::value_type &)
        ]
코드를 따라나가다보면 hash_map 의 value_type 이 pair<const int,int> 가 되는데,
const 에다가 대입을 하려고 해서 생기는 에러인 것 같습니다.
그래서 여기 저기 찾아보니까 map 이나 set 류의 associative container 에다가는
remove_if 를 사용할 수 없다는 뉘앙스의 글들이 종종 보이는데,
쓸 수 없다는 명백한 문장은 찾을 수 없었습니다.

정말 쓸 수 없는게 맞을까요?
레이옷(Reiot) at http://reiot.com
Yeol
Posts: 50
Joined: 2005-06-24 15:40
Contact:

Post by Yeol »

remove, remove_if 는 연관 컨테이너(set, map)에 사용할 수 없습니다.
remove는 제거될 원소를 직접 삭제하지않고 그 원소의 자리에
다음 원소를 차례로 덮어쓴후 새로운 끝 위치를 반환합니다.
'ABCDEFG'가 저장된 char형 배열에서 remove로 'D'를 제거한다면,
배열을 'ABCEFGG'로 만들고 새로운 끝(뒤에서 두번째 'G')의 위치를 반환하는 거죠.
map에서 이 알고리즘을 사용하면 같은 키값을 가진 원소가 두개가 되버리겠죠.

그리고 연관 컨테이너에는 find_if 같은 순차 알고리즘보다는 컨테이너의 멤버 함수를 사용하는 것이 좋습니다.
sphawk
Posts: 149
Joined: 2004-05-28 02:11
Location: N모사

Post by sphawk »

윗분이 설명 잘 해 주셨네요. 다음은 참고 자료입니다.

vc 7.1 의 hash_map 의 멤버 함수입니다.
size_type erase(const key_type& _Keyval)
void erase(const key_type *_First, const key_type *_Last)

꼭 연관 컨테이너가 아니더라도, 멤버 함수가 있으면
알고리즘보다는 멤버 함수를 사용하는 것이
대부분의 경우 성능이 좋습니다.
Reiot
Posts: 133
Joined: 2003-10-16 12:02
Contact:

Post by Reiot »

답변 감사드립니다.

그런데 종종 연관 컨테이너에서 키 값이 아닌 무언가로 검색해야만 하는 경우에는 어쩔 수 없이 순차검색을 사용해야만 하지 않나요? ^^
레이옷(Reiot) at http://reiot.com
seeper
Posts: 1483
Joined: 2003-06-06 23:19
Contact:

Post by seeper »

데이터가 적다면 순차검색하겠지만..
(그렇다면 그냥 vector 쓰죠...)
데이터가 많다면 저는 index 같은걸 만들어서..
다시 key를 가르켜 줍니다.

그런데 이렇게 하는게 맞는건가요??
seeper0 (a) gmail.com [email주소 무단수집거부]
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

Reiot wrote:답변 감사드립니다.

그런데 종종 연관 컨테이너에서 키 값이 아닌 무언가로 검색해야만 하는 경우에는 어쩔 수 없이 순차검색을 사용해야만 하지 않나요? ^^
그러고보니... 이런 문제가 있었군요...

아무 생각없이 처음에는 map 으로 구성했다가 나중에 순차 검색을 해야하는 상황이 종종 있었던것 같습니다.
어차피 그런형태로 사용한다면 에초에 set을 사용하는 것도 좋을것 같습니다.

그리고 remove 와 remove_if , find_if 에 관한 내용은 more exceptional c++ 에 (질문 하신것과는 조금 다른 내용입니다만) 간단한 설명이 있네요.
(Item#2, Item#3)

remove 를 통해서 실제 컨테이너 안의 값이 지워지지 않는 이유는,
remove 가 iterator 만 가지고 동작하기 때문에 그 안의 값을 지우는 기능을 갖을 수 없다고 하네요.
I want to live in korea, making programs, but...
http://wrice.egloos.com
Locked