C++ 컨테이너 선택에 대해 여쭙고자 합니다.

greathero의 이미지

제가 어떠한 클래스에서 쓰고 싶은 컨테이너는 특정 객체를 10개만 저장하는 컨테이너입니다.
그런데, 인덱스가 1~10까지 고정되어 있었으면 좋겠습니다.

그래서 <인덱스, 객체> 방식으로 map을 생각했는데요.
map을 쓰려니 좀 난감한 점이 있더라구요.

이 컨테이너에서 null인 객체가 몇 개인지를 찾는지에 대한 로직을 구현한다고 보면
그냥 단순히 생각했을 땐 (m->find(i) == m->end)인지 아닌지를 봐야되는데 이걸
i를 1부터 10까지 돌릴려고 보니 좀 짜증나더라구요.
선형적 비용 + 로그 비용(find 함수)가 드니까 비효율적으로 보이기도 하고...

반대로 map이 아니라 벡터라면 아래와 같이 하면 되서 편하구요.
****단, 벡터에 erase나 remove를 쓰는게 아닌 해당 인덱스값에 널값을 넣는 방식으로 삭제를 했습니다.****
(이 방법이 문제를 일으킬까요?)

for(Obj obj: *objVector) {
  if(obj == 0)
    ++numOfEmpty;
}

컨테이너 안에 객체를 삽입/삭제 하고싶을때도 일단 해당 인덱스 안에 객체가 있는지 판별을 해야 하는데
map의 find 함수보단 직관적으로 objVector->at()을 이용하는게 편하구요(물론 벡터에서의 element 삭제 함수를 쓰는게 아닌 널 값으로 삽입한다는 가정하에)

사실 인덱스 범위가 고정되어야 하고 요소 삽입이나 삭제시에 요소들이 안밀려나게 할려면 벡터는 부적합하고 맵이 훨씬 적합하긴 한데...
이런 현실적인 문제때문에 일단은 벡터를 쓰고 있습니다. 잘 돌아는 가구요.

그런데, 제가 원하는 바를 map으로 효과적으로 구현을 할 수 있을까요?
조금 더 질문을 함축하면 map에서 null인 객체를 "map->find(index) == map->end()" 방식 말고 다르게 찾을 수 있을까요?
그러면 벡터 대신 map을 쓸 수 있을거 같습니다.
아시는 분 있으시면 도와주세요 ㅎㅎ~~

klyx의 이미지

왜 map이 더 적합한가요?

greathero의 이미지

벡터를 썼을 때 삭제 연산을 일반적인 erase를 써서 지우고 싶은데 이렇게 되면 인덱스가 제가 생각하는 대로 유지가 안됩니다.
즉, 5번째의 객체가 삭제되었으면 여긴 삭제된채로 남아있어야 하는데(5번 인덱스는 null로) erase를 하면 그 뒤의 원소들이 한칸씩 당겨지니깐요...

그래서 궁여지책으로 삭제 연산을 erase를 쓰지 않고 null값을 넣은거였구요.
뭐 이런 방법이 문제 될게 없다면 저도 벡터가 적합하다고 생각해요 ㅎㅎ

empty2fill의 이미지

"이 컨테이너에서 null인 객체가 몇 개인지를 찾는지에 대한 로직을 구현한다고 보면 그냥 단순히 생각했을 땐 (m->find(i) == m->end)인지 아닌지를 봐야되는데 이걸 i를 1부터 10까지 돌릴려고 보니 좀 짜증나더라구요. 선형적 비용 + 로그 비용(find 함수)가 드니까 비효율적으로 보이기도 하고..."

컨테이너에서 null인 객체의 개수 = 10 - map.size() 하면 되지 않을까요?

——
———
Life is a tragedy when seen in close-up, but a comedy in long-shot. - Chaplin, Charlie -

greathero의 이미지

갯수만 구하는게 아니라 하나하나 NULL인지 따져볼려면 어차피 FIND를 해야되는건 마찬가지라서요ㅠ

klyx의 이미지

혹시 iterator는 알고 계신가요? 모든 요소를 탐색하는데 왜 find를 쓰시는지 모르겠습니다.

greathero의 이미지

map에서 erase를 해버리면 이터레이터를 써서 접근을 하면 해당 객체가 null인지 아닌지 제대로 판별을 못하는거 같아요...

greathero의 이미지

제가 NULL 값 판별하는 코드를 잘못 짰는지...
한번 봐주세요~

	map<int, Human> *m = new map<int, Human>();
 
	m->operator[](1) = human1;
	m->operator[](2) = human2;
	m->operator[](3) = human3;
	m->operator[](4) = human4;
	m->operator[](5) = human5;
 
	m->erase(2);
	// 2번째 인덱스에 있는 인간이 NULL인지 판별할 수 있는지 살펴보자.
	auto it = m->begin();
	++it;
	if(it->second == 0)
		cout << "NULL" << endl;
	else
		cout << "NOT NULL" << endl;
	// OUTPUT: NOT NULL
greathero의 이미지

1번 3번 4번 5번 이렇게 밖에 접근을 못하고 2번에 접근을 못하게 되네요...
인덱스 정보를 유지하려면 vector이던 map이던 erase를 쓰지말고 null값으로 덮어씌워야 되는듯...

kukyakya의 이미지

왜 굳이 index 정보를 유지하려고 하시는건가요?

10개를 유지하는것이 중요하다면 그냥 *Object[10] 을 사용하시는게 나아보이는데요.

greathero의 이미지

인덱스를 1~10까지 고정적으로만 받을거라서요~

greathero의 이미지

코드에 반복자가 들어가는 곳이 너무 많아서 GG네요 ㅋㅋ

klyx의 이미지

자주 불리는 부분을 함수로 만들면되지요.

greathero의 이미지

코드로 설명을 해주실 수 있을까요?

klyx의 이미지

왜 굳이 연산자를 operator[]로 호출하나요? 그냥 m[1] = human1; 처럼 하면 되는데...
그리고 당연히 지워버리면 NULL도 뭐도 아닙니다. 지우면 그냥 map 안에 없는겁니다. erase가 호출되고 나면 map의 크기 자체가 하나 줄어듭니다.

jick의 이미지

map은 대량의 데이터를 넣었을 때 효율적으로 검색을 할 수 있어야 하기 때문에 보통 balanced tree 구조를 하고 있습니다.

이 balanced tree가 말은 좋은데 사실 오버헤드가 큽니다. 데이터를 하나 집어넣을 때마다 루트에서부터 탐색을 하며 맞는 자리를 찾고 필요에 따라 트리를 회전시키는 삽질을 해야 합니다.

데이터 열 개짜리 map을 사용하면 뭐 동작이야 하겠지만 뭘 해도 vector보다 느릴 거라는 데 한표 던집니다.

philnet의 이미지

(1) 객체 대신 객체 포인터를 넣은 선언,
(2) 객체를 지워야할 때에는 erase 대신 지울 객체의 포인터를 delete 하고, 해당 map 의 위치를 NULL로 설정

...
void DeleteHuman(map<int, Human*>& humans, int idToDelete)
{
  delete humans[idToDelete];
  humans[idToDelete] = NULL;
}
 
int CountNullHuman(const map<int, Human*>& humans)
{
  int count = 0;
  for ( map<int, Human*>::const_iterator iter = humans.begin(); iter != humans.end(); ++iter )
  {
    if ( iter->second == NULL ) ++count;
  }
  return count;
}
...

Human* 대신 tr1::shared_ptr 을 사용하신 다면 삭제하는게 좀더 간단해지고, 메모리 누수에 대한 염려도 줄겠죠.

philnet의 이미지

STL에 어느 정도 익숙해 지고, 어떤 컨테이너를 어떤 알고리듬을 써야 하는가가 슬슬 궁금해진다면,
Effective STL을 읽어야 할 때가 된 듯 싶습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.