[질문] multimap에서 효율적인 update ?
글쓴이: sulsj / 작성시간: 화, 2006/06/13 - 1:16오후
안녕하세요
또 여쭙네요..^^
multimap에서 find로 찾은 iterator로 erase(iterator)가 작동하지 않는군요?
우찌하면 효율적으로 update가 가능할까요?
find --> erase --> insert로 쉽게 생각했다가 안되서 헤매고 있습니다. 쩝
typedef struct {
unsigned long _hv2;
string _bs;
int _cnt;
} _KEYMAP_TYPE;
typedef std::multimap<unsigned long, _KEYMAP_TYPE, greater<unsigned long> > KEYMAP_T;사용하는 자료구조는 위와 같구요.
update는 multimap에서 찾아낸 record에서 struct의 _cnt 값을 변경해줘야 하는데...
답변 부탁드립니다.
그럼
Forums:
update 목적으로
update 목적으로 기존의 원소를 지우고 새로 추가하는 방법은 매우 비효율적입니다.
multimap::find()의 반환형은 multimap::iterator인데, 이는 (first, second) pair로
이루어집니다. first는 키를, second는 value를 접근하는 데 사용되지요.
그런데 multimap은 같은 키를 갖는 값이 여러 개 존재할 수 있기 때문에 검색할 때
find()보다 equal_range()를 많이 씁니다.
typedef KEYMAP_T::iterator Iterator; KEYMAP_T m; pair<Iterator, Iterator> range = m.equal_range(1); for (Iterator it = range.first; it != range.second; ++it) it->second._cnt = 3;감사 ^^
잠깐 문제가 있었는데
해결했습니다.
감사드립니다.
그리고 제 경우엔 equal_range에 의해 검색되는 모든 놈들을 다 업뎃하려는 의도가 아니고
struct member의 필드가 일치하는 놈 하나만 업뎃해야 합니다.
따라서 find를 써서 iterator를 증가시키고 있구요...
다른 질문은 있다면...
위에 이야기와 비슷한 맥락인데
equal_range보다 find가 효율적이라 들어서
find --> iterator --> iterator 증가하면서 struct member 비교 --> 업뎃
정책을 생각했는데
equal_range --> upper and lower iterator --> 범위안 데이터만 struct member 비교 --> 업뎃..
이 정책이 더 빠를까요? ^^
음냐...
암튼 감사.
어느 쪽이 빠른지는
어느 쪽이 빠른지는 저도 모르겠습니다.
구현체와 환경에 좌우되는 부분이 많기 때문입니다.
가장 확실하게 알려면 sulsj님의 환경에서 직접 측정해보시면 되겠습니다.
속도가 아니라 코드 측면에서 볼 때 find()를 쓰면 좀 지저분해질 수는 있습니다.
find()를 쓰면서 iterator를 증가한다면 upper bound를 모르므로 iterator가 가리키는 원소가
찾고자 하는 것인지 검사하는 과정이 필요해지죠. 그렇지 않으면 엉뚱한 원소를 변경할 수 있으니까요.
unsigned long key; for (Iterator it = m.find(key); it != m.end() && !(it->first < key) && !(key < it->first); ++it) { // update elements } pair<Iterator, Iterator> range = m.equal_range(key); for (Iterator it = range.first; it != range.second; ++it) { // update elements }저에게는 equal_range() 쪽이 훨씬 읽기 편하네요.
ps. 왜 find()를 쓸 때 비교 구문이 it->first == key 가 아니라 이렇게 복잡하게 쓰는지 의문을 느끼신다면
Effective STL item 19를 읽어보십시오. equality와 equivalence의 차이가 잘 나와 있습니다.
답변 감사드립니다.
^^