STL 메모리에 관해 질문이 있습니다.

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

Moderator: 류광

Locked
비회원

STL 메모리에 관해 질문이 있습니다.

Post by 비회원 »

STL 을 사용하던중 궁금한게 생겼습니다.

typedef list<string> VALUE;
typedef map<int> ITEM;



이렇게 선언을 하고

VALUE value;
value.push_back("문자열");
...
...


여러개를 push 하고 나서
ITEM item;

item.insert(make_pair(10, value));
...
...

이렇게 다시 맵에 값을 넣었습니다.

이 상태에서 item.clear(); 를 하면..

안에 있던 리스트까지 전부 삭제가 되는건가요..?
mika
Posts: 537
Joined: 2005-01-17 22:42

Post by mika »

네.

그런데 list에 값을 넣고 맵에 추가하는 방식은 insert할 때 list간의 복사가 발생하게 되므로 매우 비효율적일 것 같네요.

빈 리스트를 맵에 담고 해당 리스트에 값을 추가하거나, 리스트의 포인터를 담는 편이 더 나을 듯. ^^
비회원

빈 리스트를 넣으라는것이..

Post by 비회원 »

소중한 답변 감사합니다 ^^

답변 내용을 보니 리스트 복사가 일어나면 느려지겠네요..ㅠㅠ

그렇다면.

VALUE value;
item.insert(make_pair(1, value));

ITEM::iterator itMap;

itMap = item.find(1);

itMap->second.push_back("문자열");


이런식으로 작성을 하면 되는건가요..?
비회원

.

Post by 비회원 »

안녕하세요.

insert 반환값이 해당 맵에 추가된 요소의 반복자일 것입니다.
find 를 굳이 하지 않으셔도 될것 같습니다.
비회원

흠..

Post by 비회원 »

insert 를 보면 pair 형태의 iterator 인지 뭔가를 반환을 하는데요.

pair 는 iterator 가 없나봐요...? ㅠㅠ

어떤식으로 받아야 할까요..
비회원

찾았습니다..;;

Post by 비회원 »

pair<iterator> 형태로 만들어서 받아야 하는군요...ㅎㅎ
mika
Posts: 537
Joined: 2005-01-17 22:42

Post by mika »

굳이 insert하실 필요 없이,

map[key] = value;

위와 같이 첨자 연산자를 사용하는 방법도 괜찮겠네요.
만약 id에 해당하는 키가 없을 경우 자동으로 생성하고 이후 연산을 처리하므로 더 깔끔할 듯.
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

map 의 operator[] 는 사용하시면 성능이 대략 느려집니다.
effective STL 에 설명되어있습니다.
insert 와 find 를 사용하시기를 권합니다.
I want to live in korea, making programs, but...
http://wrice.egloos.com
mika
Posts: 537
Joined: 2005-01-17 22:42

Post by mika »

쌀밥 wrote:map 의 operator[] 는 사용하시면 성능이 대략 느려집니다.
effective STL 에 설명되어있습니다.
insert 와 find 를 사용하시기를 권합니다.
항상 느린 게 아닙니다. 그럼 operator[]의 존재 가치가 없겠죠.
estl을 보셔도 "추가" 상황에서만 비효율적일 수 있다고 명시하고 있습니다.

추가가 빈번하다면 안 좋을 수도 있겠지만, 질문 본문에 언급한 상황은 그런 상황으로 보이진 않네요.

게다가 estl에 추가와 갱신 모두 괜찮은 insert 함수의 예시를 보이고 있는데(172p),
vc 2008의 std::map::insert의 구현을 살펴보면 그대로 입니다.
(확인은 하지 않았지만 하위 버전에서도 마찬가지일거라 봅니다.)

비회원님께서는 사용하시는 컴파일러의 구현을 살펴보시고 만약 비효율적으로 구현이 되어 있다면
insert와 find를 사용하시는 것이 좋을 수도 있겠지만(이때 insert는 단축정보를 사용하는 버전을 써야 합니다)
제 생각에는 그런 가능성은 희박하니 그냥 operator[]를 쓰는 것이 여러 모로 나을 것 같네요.
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

개인적인 코딩 취향일지도 모르겠습니다만, 저라면 map::operator[] 를 쓰지 않겠습니다.

코딩을 하다가 보면 오타가 날수도 있고 실수를 할수도 있는데, operator[] 를 사용하면 예를 들어
variable["key"] = "value";
라고 하는것이 내가 추가를 하려고 하는것인지 update 를 하려고 하는 것인지 명확하지 않습니다. "key" 에 해당하는 부분에 오타가 나서 "Key" 라고 입력했다고 하면 나중에 디버깅하는 것도 고녁입니다.

테클은 아니니 참고되시길...
I want to live in korea, making programs, but...
http://wrice.egloos.com
비회원

Post by 비회원 »

쌀밥 wrote:개인적인 코딩 취향일지도 모르겠습니다만, 저라면 map::operator[] 를 쓰지 않겠습니다.

코딩을 하다가 보면 오타가 날수도 있고 실수를 할수도 있는데, operator[] 를 사용하면 예를 들어
variable["key"] = "value";
라고 하는것이 내가 추가를 하려고 하는것인지 update 를 하려고 하는 것인지 명확하지 않습니다. "key" 에 해당하는 부분에 오타가 나서 "Key" 라고 입력했다고 하면 나중에 디버깅하는 것도 고녁입니다.

테클은 아니니 참고되시길...

추가 하려고 하는건지 업데이트하는건지 구별을 할수없다는건
구조자체가 잘못된거아닌가요...
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

코드는 누가 언제 읽어도 의미가 명확한것이 더 좋은것 아니겠습니까?

물론 내가 짠것도 내일이나 한달뒤에 보면 "내가 여기서 업데이트 하는 거였나? 추가 하는건가?" 하고 갸우뚱할수 있는 것이지요.

좋은 "구조"의 함수는 "한번에 한가지만" 그것도 "잘" 하는 것이 좋은 함수입니다.
그런점에서 한번에 업데이트도 하고 추가도 하는 어정쩡한 함수를 선호하는 것은 가독성이나 유지 보수나 구조나 설계나 뭐로 봐도 좋은 점이 없는 것이지요.

거기에 성능도 더 나아지는게 아니라면 굳이 왜....??

*다시 말하지만 이것은 어디까지나 개인적인 코딩 스타일의 차이인것 같습니다...
I want to live in korea, making programs, but...
http://wrice.egloos.com
namenu
Posts: 34
Joined: 2006-11-29 02:11

Post by namenu »

예를들어 cache를 map으로 관리하는데 없다면 추가하고, 있다면 갱신하고자 한다면 []가 괜찮은 선택이 아닐까요?

비슷한 시각으로 fopen에서 "w"옵션도 모호한 의미를 가진다고 볼 수 있는데, 상황에 따라서 자주 사용되지요..


에 그리고 find->insert가 []보다 빠르다고 보기는 힘든데요.. (vc2008)

find로 검증을 한 번 하고 insert를 할 때

iterator it = m.find(v);
m.insert(v); // 1
m.insert(it, v); // 2

1번을 이용하면 내부적으로 find를 한번 더 하고
2번을 호출한다고 해도 it는 힌트일 뿐 내부적으로 검증을 거치게 됩니다.

vc2008에서 []는 내부적으로 find->2번을 호출하는 구조로 되어있지만, 내부적으로 검증과정이 생략될 여지가 있습니다.

암튼 []를 너무 미워하지 맙시다..
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

잘 이해가 안가는 부분이 있어서...
namenu wrote:예를들어 cache를 map으로 관리하는데 없다면 추가하고, 있다면 갱신하고자 한다면 []가 괜찮은 선택이 아닐까요?
이부분은 이렇게 되는것 인가요?

Code: Select all

iterator iter = cache.find(key);
if( iter == cache.end() ) {
    // 없다면 추가
    const VALUE value = retrieveValue( key ); // costly
    cache.insert( part < KEY, VALUE > ( key, value) );
    return value;
}
// 있으면 바로 리턴
return iter->second;
"있다면 갱신"이라는 부분이 이해가 안가네요.

cache 안에 값이 없으면 (retreieveValue 호출한 다음에) 값을 넣고,
cache 안에 값이 있어도 (retreieveValue 호출한 다음에) 값을 갱신(!)하면,
cache 안에 값이 있거나 없거나 retreiveValue 를 한다는 이야기가 되는데,
그럼 이경우 cache 가 어떻게 성능을 향상시키는거죠?
namenu wrote:비슷한 시각으로 fopen에서 "w"옵션도 모호한 의미를 가진다고 볼 수 있는데, 상황에 따라서 자주 사용되지요..
이부분은 저는 모르는건가 본데, 좀 더 설명을 부탁드립니다. :-)

namenu wrote:에 그리고 find->insert가 []보다 빠르다고 보기는 힘든데요.. (vc2008)

find로 검증을 한 번 하고 insert를 할 때
항상 find 로 검증한뒤에 insert를 해야하는 것이 아니기 때문에 빨라질수 있는 것이죠.

추가 할때는 (find 없이) insert 만 하고
갱신 할때는 find 만 하면 되지요.


*PS: 물론 추가와 갱신을 구분할 필요가 전혀 없는 곳에서는 operator[]를 쓰는게 적절할때도 있겠습니다. 그걸 부정하는 것은 아니니...
*PS 다시 말씀드리지만 이건 개인적인 코딩스타일의 문제인것 같습니다.
I want to live in korea, making programs, but...
http://wrice.egloos.com
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

namenu wrote:iterator it = m.find(v);
m.insert(it, v); // 2
생각해보니 위의 코드는 의도하신것 처럼 동작하지 않을듯 합니다.
it 에 관계없이 v 에 있는 key 값을 사용하는 것이고, it 는 그냥 힌트일뿐이군요..
(저런식으로 사용해본적이 없어서....:-) )

갱신하실때는 cache.find( key )->second = newValue; 식으로 하시면 됩니다.
I want to live in korea, making programs, but...
http://wrice.egloos.com
namenu
Posts: 34
Joined: 2006-11-29 02:11

Post by namenu »

"있다면 갱신"이라는 부분이 이해가 안가네요.

cache 안에 값이 없으면 (retreieveValue 호출한 다음에) 값을 넣고,
cache 안에 값이 있어도 (retreieveValue 호출한 다음에) 값을 갱신(!)하면,
cache 안에 값이 있거나 없거나 retreiveValue 를 한다는 이야기가 되는데,
그럼 이경우 cache 가 어떻게 성능을 향상시키는거죠?
갱신이란게 second를 덮으씌우는 작업을 말하는 겁니다. :)

Code: Select all

iterator iter = cache.find(key);
if( iter == cache.end() ) {
    // 없다면 추가
    const VALUE value = retrieveValue( key ); // costly
    cache.insert( part <KEY> ( key, value) );
    return value;
}
// 있으면 갱신후(!) 리턴
ter->second = retrieveValue(key);  // <return>second;
말씀하신 모호성 문제라면 "w"옵션은 이게 파일을 덮어씌우는건지 새로 만드는건지가 애매하니까 이 역시 지양해야할까? 하는 의문에 예를 들어본 거구요.

그리고 위 코드에서 cache.insert는 key값을 삽입할 곳을 찾기 위해 tree의 탐색이 일어납니다.

find의 내부에서 사용된 lower_bound가 그 정확한 위치를 가리키고 있으므로 이는 낭비죠.

Code: Select all

cache.insert(iter, pair(key, value));
적어도 이렇게 iter를 명시해 주어야 하지만 대부분 무의식적으로 쌀밥님처럼 insert를 사용합니다.

탐색을 위해 상수시간을 소비하느냐 logN만큼을 소비하느냐는 상황에 따라 작은 문제가 될 수 있습니다.

이 함수는 iter가 어떤 위치를 가리키던 전후를 살펴보고 유효한 경우에는 해당 위치에, 그렇지 않는 경우에는 iter를 무조건 신뢰하는 private insert를 사용하고 있습니다.

그에 비해 []는 find->private insert로 이어질 수 있다! 하는것이 앞서 댓글에서 말하고자 했던 내용인데.. 제가 설명을 넘 대충 했네요..
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

궁금해서 직접 테스트 해봤습니다.

Code: Select all

	const int maxCount = 1000 * 1000 * 10;

	for( int k = 0; k < 3; ++k ) {
		cout << "=== Round " << k + 1 << " =====" << endl;

		{
			map<int> cache;
			const time_t startTime1 = time(NULL);
			for( int i = 0; i < maxCount; ++i )
				cache[i] = i;
			const time_t endTime1 = time(NULL);
			cout << "insertion with operator[]: " << endTime1 - startTime1 << "sec" << endl;

			const time_t startTime2 = time(NULL);
			for( int j = 0; j < maxCount; ++j )
				cache[j] = j;
			const time_t endTime2 = time(NULL);
			cout << "update with operator[]: " << endTime2 - startTime2 << "sec" << endl;
		}

		{
			map<int> cache;
			const time_t startTime1 = time(NULL);
			for( int i = 0; i < maxCount; ++i )
				cache.insert( pair<int>( i, i ) );
			const time_t endTime1 = time(NULL);
			cout << "insertion with insert: " << endTime1 - startTime1 << "sec" << endl;

			const time_t startTime2 = time(NULL);
			for( int j = 0; j < maxCount; ++j )
				cache.find(j)->second = j;
			const time_t endTime2 = time(NULL);
			cout << "update with find: " << endTime2 - startTime2 << "sec" << endl;
		}
	}
궁금하신분들은 직접 해보시길...

제 컴퓨터는 mac 이라서 gcc 4.3.3 에 Darwin 8.11.1 에서 돌렸습니다. 결과는 다음과 같습니다.
=== Round 1 =====
insertion with operator[]: 34sec
update with operator[]: 15sec
insertion with insert: 31sec
update with find: 16sec
=== Round 2 =====
insertion with operator[]: 31sec
update with operator[]: 17sec
insertion with insert: 33sec
update with find: 17sec
=== Round 3 =====
insertion with operator[]: 30sec
update with operator[]: 16sec
insertion with insert: 33sec
update with find: 17sec
결론적으로 별 차이가 없는것 같군요.
10,000,000 번을 반복한다는 점을 고려해볼때 1초나 2초 정도 차이는 큰 차이가 아니라고 생각되네요...
I want to live in korea, making programs, but...
http://wrice.egloos.com
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

Post by 쌀밥 »

namenu wrote:

Code: Select all

iterator iter = cache.find(key);
if( iter == cache.end() ) {
    // 없다면 추가
    const VALUE value = retrieveValue( key ); // costly
    cache.insert( part <KEY> ( key, value) );
    return value;
}
// 있으면 갱신후(!) 리턴
return ter->second = retrieveValue(key);  // <return>second;
위와 같이 한다면 map을 사용할것 없이 그냥 왜

Code: Select all

return retrieveValue(key)
를 하지 않는지 의아해지는군요. 뭔가 다른 형태의 cache 를 염두에 두신것 같은데, 뭐 꼭 저런식으로 해야한다면 operator[] 를 사용하는게 좋은 경우라고 생각됩니다..
namenu wrote:말씀하신 모호성 문제라면 "w"옵션은 이게 파일을 덮어씌우는건지 새로 만드는건지가 애매하니까 이 역시 지양해야할까? 하는 의문에 예를 들어본 거구요.
fopen 과 map 에 값을 넣는 것은 가지고 시작하는 전재가 다릅니다.
파일에 쓰기를 할때 프로그래머는 보통 해당 파일이 없는걸 시작점으로 전재(precondition)하고 시작하는 반면에
map 을 다룰때는 그 안에 값이 있는 경우와 없는 경우가 둘다 존재한다는 전재를 가지고 있기 때문에
이 두가지의 비교는 적절하지 않아보입니다.
namenu wrote:그리고 위 코드에서 cache.insert는 key값을 삽입할 곳을 찾기 위해 tree의 탐색이 일어납니다.

find의 내부에서 사용된 lower_bound가 그 정확한 위치를 가리키고 있으므로 이는 낭비죠.

Code: Select all

cache.insert(iter, pair(key, value));
적어도 이렇게 iter를 명시해 주어야 하지만 대부분 무의식적으로 쌀밥님처럼 insert를 사용합니다.

탐색을 위해 상수시간을 소비하느냐 logN만큼을 소비하느냐는 상황에 따라 작은 문제가 될 수 있습니다.

이 함수는 iter가 어떤 위치를 가리키던 전후를 살펴보고 유효한 경우에는 해당 위치에, 그렇지 않는 경우에는 iter를 무조건 신뢰하는 private insert를 사용하고 있습니다.

그에 비해 []는 find->private insert로 이어질 수 있다! 하는것이 앞서 댓글에서 말하고자 했던 내용인데.. 제가 설명을 넘 대충 했네요..
이부분은 몰랐던 내용인데 하나 배웠습니다. 감사감사 :-)
I want to live in korea, making programs, but...
http://wrice.egloos.com
namenu
Posts: 34
Joined: 2006-11-29 02:11

Post by namenu »

쌀밥 wrote:
namenu wrote:

Code: Select all

iterator iter = cache.find(key);
if( iter == cache.end() ) {
    // 없다면 추가
    const VALUE value = retrieveValue( key ); // costly
    cache.insert( part <KEY> ( key, value) );
    return value;
}
// 있으면 갱신후(!) 리턴
return ter->second = retrieveValue(key);  // <return>second;
위와 같이 한다면 map을 사용할것 없이 그냥 왜

Code: Select all

return retrieveValue(key)
를 하지 않는지 의아해지는군요. 뭔가 다른 형태의 cache 를 염두에 두신것 같은데, 뭐 꼭 저런식으로 해야한다면 operator[] 를 사용하는게 좋은 경우라고 생각됩니다..

Code: Select all

bool load(Key k, Value& v)
{
  iterator it = cache.find(k);
  if (it == cache.end()) return false;
  v = it->second;
  return true;
}

void save(Key k, const Value& v)
{
  cache[k] = v;
}

void save2(Key k, const Value& v)
{
  iterator it = cache.find(k);
  if (it == cache.end())
    cache.insert(v);
  else
    it->second = v;
}

void load_with_save(Key k, Value& v)
{
  if (!load(k, v)) {
    v = compute(k);
    save(k, v);
  }
}

위와 같을 때 두 save를 비교하려고 했던건데요, 위 코드는 무시해주세요 :oops:
zupet
Posts: 2764
Joined: 2003-05-13 03:34
Location: NCSOFT LE팀

Post by zupet »

namenu wrote:말씀하신 모호성 문제라면 "w"옵션은 이게 파일을 덮어씌우는건지 새로 만드는건지가 애매하니까 이 역시 지양해야할까? 하는 의문에 예를 들어본 거구요.

그리고 위 코드에서 cache.insert는 key값을 삽입할 곳을 찾기 위해 tree의 탐색이 일어납니다.

find의 내부에서 사용된 lower_bound가 그 정확한 위치를 가리키고 있으므로 이는 낭비죠.
STL map 객체 아닌가요? find 가 실패하면 무조건 end() 를 가르키게 됩니다. find 가 성공한 다음 그 다음에 무엇인가 삽입할때는 도움이 되지만 위와 같이 존재 여부만 위와 같이 find 가 실패한 경우에는 iter 를 써도 비용 절감이 없다고 알고 있습니다.

참고로 저는 map을 쓸때 항상 아래와 같이 사용합니다. 사실상 operator[] 와 같은 형태지만 새로운 값을 삽입하고 default constructor 를 호출하는 것이 자동적으로 진행되는데 경우에 따라 외부 초기화가 필요하기 떄문에 STL에 그냥 맡기는 것보다는 직접 사용하는게 낫다고 생각했습니다. 디버깅할 때도 어느 시점에 새로운 삽입이 일어나는지를 확인할 수 있기 때문에 여러모로 편합니다. ^_^

Code: Select all

map_iter iter = myMap.find(key);
if(iter == myMap.end())
{
  iter = myMap.insert(iter, value_type(key, OBJECT()));

  iter->second.InitObject(~~~);
}

// 여기서부터는 무조건 iter 가 유효하다.
iter->second.~~ = ?@$;
iter->second.~~ = !#@;
iter->second.~~ = ?%$;

사실 operator[] 로 접근하는 코드를 써놓으면 STL에 익숙하지 않은 분들이 아래 같은 코드를 마구 적어놔서 근본적으로 STL map 에서 [] 사용하는 것 자체를 막고 있습니다. . (먼저 iterator 만으로 코드를 먼저 자버리면 []를 굳이 꺼내다 쓰지 않더군요. 그리고 시간날때 딴사람들 짜놓은 부분 몰래 고쳐놓다보면 코드에서 [] 쓰는걸 거의 찾아보기 힘들어지죠. ^_^)

Code: Select all

// 코드량은 적어보이지만 매우 안좋은 예다. 쓰지 말것.
myMap[key].~~ = ?@$;
myMap[key].~~ = !#@;
myMap[key].~~ = ?%$;
Locked