현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

std::Set + std::List의 장점을 가진 자료구조가 있나요?

ignore444의 이미지
글쓴이: ignore444 / 작성시간: 금, 2010/06/18 - 12:53오후

* binary search tree의 장점 : 삽입/삭제/찾기가 빠르다
* liked list의 장점 : 삽입한 순서대로 순회가 가능하다.

위의 특징을 만족시키는 자료구조가 있나요?
list에서 set의 iterator의 포인터를 간직하고 있다... 라는 식의 구현은 별로 라고 생각합니다. set의 공개된 인터페이스를 사용하지 않고 set구현에 의존된 변수를 list에서 건들고 있으니깐요, 또한 어떤 item을 삭제한다고 했을때, set에서는 삭제가 빠르지만, list에서 삭제하려면 전부 훑어 봐야 하니깐요. 이 문제를 해결하기 위해서는 set에서도 list의 iterator의 포인터를 가지고 있고... 점점 소스는 지저분해지고요
그렇기 때문에 이런 자료구조가 있는지 찾고 있습니다.
혹시 아시는 분 있나요? 아마 없을듯 싶지만요..

Forums: 
프로그래밍 QnA
klara의 이미지

글쓴이: klara / 작성시간: 금, 2010/06/18 - 1:22오후

그런 자료구조가 있는진 모르겠지만, linked list의 장점은 삽입한 순서대로 순회가 가능하다가 아닙니다.
linked list의 삽입이 빠르다는 것입니다.
linked list는 삽입한 순서대로가 아니라, 노드가 연결된 순서대로만 순회가 가능합니다.

winner의 이미지

글쓴이: winner / 작성시간: 금, 2010/06/18 - 2:00오후

우선 set은 그렇게 빠르지 않습니다. logN 이 많은 경우 빨라보여도 대용량의 경우
성능을 상당히 저하시킬 수 있습니다.
list와 set은 application의 자료이용방식에 따라 각 연산의 성능이 달라지므로
누가 더 빠르다 느리다고 할 수는 없습니다.

생각하시는 것은 보통 흔히 영속저장방식(예를 들어 파일 혹은 DB)에서 index를 활용하는 방식같은데
set을 기반으로 list를 덧붙이는 방식이 아니라 거꾸로 list 기반에서 set을 활용하는 방식을 씁니다.
공개된 interface와 구현이야기는 정확히 어떤 것을 원하는지 모르겠습니다만
두가지를 모두 활용해야 하는 것이 일반적인 방식인 것 같습니다.

자료구조는 생각보다 다양하니까 깊이 공부해보시면 원하는 것을 찾을 수 있을지도 모르겠네요.

taeyeung의 이미지

글쓴이: taeyeung / 작성시간: 토, 2010/06/19 - 8:21오전

님의 응용 분야가 어떤 분야인지는 모르겠지만 데이터 베이스의 구현이나 파일 시스템의 구현에 B+ Tree를 많이 사용합니다.

(트리 구조와 리스트 구조의 혼합 형태입니다)

http://en.wikipedia.org/wiki/B%2B_tree

인터넷에 공개된 소스도 많으니 참고가 될겁니다.

B+ Tree는 유사 변종도 많습니다. B* Tree, B# Tree등이 있지요.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.