Dynamic storage class?

This is a discussion on Dynamic storage class? within the C++ Programming forums, part of the General Programming Boards category; Stacks are highly dynamic. You can insert and remove nodes at will, but stacks are horrible for random access. Dynamic ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    4

    Dynamic storage class?

    Stacks are highly dynamic. You can insert and remove nodes at will, but stacks are horrible for random access.
    Dynamic arrays are great for random access, but inserting or removing a node requires moving a whole lot of data.
    Hash tables are also good for random access, but it's not quite like a normal array. If you delete a node, it doesn't automatically 'collapse' the index.

    So I'm wondering if there's any sort of class / library available which has a nice balance between dynamicness and random access.

  2. #2
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,803
    vector?
    Woop?

  3. #3
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    The STL Vector?
    http://www.cprogramming.com/tutorial/stl/vector.html

    There's going to be some overhead when doing deletions that aren't at the end, but as far I know it's not that bad and is certainly easy to use.

    [edit]
    3 mins

  4. #4
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,803
    Check out this as well it list all the stl types you can choose which one is best for you
    http://www.cppreference.com/cppstl.html
    Woop?

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    4
    I'm not exactly sure what Vectors are, but what I can find and understand about them:
    Are vectors simply like dynamic arrays, except they allocate in certain size blocks of memory? ex. It allocates in 4k blocks of memory so it's not constantly reallocating? Or is there more to it than that?

    It's hard to say what my specific use is, as I won't really use it, I have a different reason for asking:
    Currently, I have a concept for data storage. It's dynamic like a stack, but also has a fast random access rate. Inserting and deleting nodes would be no slower than inserting a node into a dynamic array with 10 elements. And if you have 100,000 nodes, it would take, on average, about 40 steps to access any node.
    So why do I ask? I just want to be sure nothing like it exists already before I start on it. It will be pretty complicated and a lot of work...

  6. #6
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,803
    Yes vector is basically a wrapper for dynamic memory. I think the standard is to double the allocation amount so say you have 4 element current it will allocate for 8 next time you add something to it.
    I don't have any experiance with it but maybe boost would have something like that.
    http://www.boost.org/
    Woop?

  7. #7
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    AFAIK only vectors, deques and maps (in the STL) allow for random access. A map would probably be pretty useless in this case, and deques and vectors will both be slow for inserting elements in the middle (a deque might be faster for this than a vector, but I'm not sure).
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,506
    > It will be pretty complicated and a lot of work...
    Which is probably why such a beast doesn't exist in wild. Sure you could do it, but it would always have poorer performance compared to the specific data structures which are more tuned to the specific task at hand.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    In any case, it sounds either like a deque or perhaps a B-tree.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    4
    B-Trees are VERY close to the concept I have in mind. One problem though: When you delete an element in a B-Tree, it doesn't seem to collapse the index. In another words, if you delete element '11', it's just an empty slot. It's not like a dynamic array where it will move all the data backwards when you delete an element.
    The concept I had in mind is very close to the B-Tree algorithm, except mine will actually collapse the index when you delete an element.

    ... Please correct me if I'm wrong though.

    I read about B-Trees at this link: http://www.semaphorecorp.com/btp/algo.html

    Take that concept, but make one major change:
    Each node in the tree holds the base of the index. ex: [ 72 84 . .]
    My concept doesn't do that though. Mine holds the number of elements in that node instead.
    To search for an element, you add the number of elements in each node. Once the number of elements is greater than the index, you know which node your element is in.
    When you insert a node, simply insert it at the proper location. Then you go back to each node in the tree, and add +1 to the number of elements.
    When you remove a node, you basically do the same, except subtract -1 to the number of elements in each node.

    In the end, you get something dynamic like a stack, but with a much faster random access rate.

  11. #11
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    1)...except mine will actually collapse the index when you delete an element.

    2)When you insert a node, simply insert it at the proper location. Then you go back to each node in the tree, and add +1 to the number of elements.

    3) When you remove a node, you basically do the same, except subtract -1 to the number of elements in each node.

    In the end, you get something dynamic like a stack, but with a much faster random access rate.
    You may get faster random access, but with the adjusting you want to do to the other nodes, how is the overall process going to be faster?

  12. #12
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    I think you could implement an indexed list that could be faster and simpler

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Indeed - insertion will still basically be O(n), if I understood you correctly. That's the same complexity as that of a dynamic array like vector<>, only with a smaller O. At the cost of considerably more costly lookup. (O(log n) instead of O(1), I think)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. my error is storage class specified for parameter
    By meli in forum C Programming
    Replies: 5
    Last Post: 03-27-2009, 12:06 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Need help to build network class
    By weeb0 in forum C++ Programming
    Replies: 0
    Last Post: 02-01-2006, 10:33 AM
  4. operator overloading and dynamic memory program
    By jlmac2001 in forum C++ Programming
    Replies: 3
    Last Post: 04-06-2003, 11:51 PM
  5. Abstract class problem
    By VanJay011379 in forum C++ Programming
    Replies: 9
    Last Post: 07-31-2002, 01:30 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21