What container/ADT should I use for the following?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: What container/ADT should I use for the following?

  1. #1
    Join Date
    Feb 2010
    Posts
    15

    What container/ADT should I use for the following?

    Hi again...

    I need to use an efficient container that satisfies the following properties:
    1) Has the ability to add elements at the end.
    2) Has the ability to remove elements anywhere.
    3) Has the ability to quickly access elements anywhere within the container (random access).

    I tried using the STL containers, specifically the list and vector templates. Lists don't have the 3rd property, so the workaround was very slow compared to what I had already designed already. Similarly, I found vectors to be also a bit slow in comparison.

    My own design is simple, but lacks the ability to remove elements, short of recreating the whole container. I have a function which needs to choose elements repeatedly and randomly from within this container, but in the meantime, some elements are 'killed'/removed from the container. I am resorting to putting a bool variable in the element class which determines whether the element is 'alive' or 'dead'. This, coupled with the randomness and repeatedness of the choosing function is leading to inefficiency.

    Is there any possible way to fix it, short of removing the randomness?

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: What container/ADT should I use for the following?

    Try a std::deque. It's like a vector, but does not guarantee elements are stored in contiguous memory, which gives it a win when adding and removing elements from the middle.

  3. #3
    Join Date
    Feb 2005
    Posts
    2,160

    Re: What container/ADT should I use for the following?

    At my old job as a QC Chemist, I had a sign hanging over my lab bench:

    You can have it done cheap.
    You can have it done right.
    You can have it done fast.
    Pick any two.

    That would seem to apply similarly to your criteria above. I'm not familiar enough with the STL containers to know if it is possible, but have you consider binary trees?

    http://en.wikipedia.org/wiki/Binary_tree

    Edit: After seeing Lindley's post: is contiguousness a requirement as well? That would certainly eliminate B-Tree.
    Last edited by hoxsiew; February 14th, 2010 at 09:23 AM.

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    Re: What container/ADT should I use for the following?

    Depending on the precise nature of your remove/choose logic, there may be a better approach. If you provide more details I may have additional suggestions.

  5. #5
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,297

    Re: What container/ADT should I use for the following?

    Not so long ago, I needed a container which could push_back, push_front, erase any element anywhere, and be able to access a random element, all in o(1).

    note that I did not need to write myContainer[5], for example, but myContainer.getRandomElement().

    This was done by having a vector, with empty "holes" in it. Basically, it was a vector of pointers, wrapped, where null pointers were allowed, but hidden to the user. The consequence is that accessing "any"element was very easy, but accessing a specific one is harder. It had bi-directional iterators, and these:begin, end, randomIt.

    I needed this because I had to model a queue of objects, and every iteration, I would take a random object from the queue (of about 1M elements), modify it, and put it back at the end, billions of times (it was a chemistry simulation).

    The container structure was degenerative (I had to re-build it every so often), but was very good for my needs.

    Maybe you need something similar? If you need more details, just ask me.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,297

    Re: What container/ADT should I use for the following?

    Quote Originally Posted by Lindley View Post
    Try a std::deque. It's like a vector, but does not guarantee elements are stored in contiguous memory, which gives it a win when adding and removing elements from the middle.
    It doesn't actually. I allows for push_front, and erase has a worst case scenario of N/2, instead of vector's N, but the complexity is still o(N). Erasing an element in a deque still shifts ALL the other elements to the nearest end. Slightly better than vector, but unacceptable for op's needs.

    No while in theory you could erase elements in a deque in constant amortized time (or at least o(log(N)) ), that is not the point of deques, and it would an extra book-keeping penalty for all the other things it was meant to do. For example, I'm pretty sure it would not be possible to keep a random access of o(1). This is because while the elements are not stored in contiguous memory, it is a lot of blocks, that all have the exact same size (implementation defined, but it's usually that way). If each block does not have the same size (to allow erase anywhere), then finding a random element, say 1000, would require a more complex look up. At least o(log(N)) I would say.

    As far as I know anyways...

  7. #7
    Join Date
    Feb 2010
    Posts
    15

    Re: What container/ADT should I use for the following?

    monarch, that does sound similar to what I need! Imagine I have these 10 elements in a container, where 'o' is a live element and 'x' is a dead one.

    starting at: o o o o o o o o o o

    The function picks a random live element, does its magic, maybe killing it in the process, and repeats the random search-kill procedure until all the elements are dead. Say it picks element 3, and kills it, giving

    o o x o o o o o o o

    It now randomly picks another element, which has to be live, and therein lies the problem. I was thinking of creating a separate list of pointers to choosable elements, and this may be similar to your approach, but I haven't tried it yet...

    As it stands at the moment, I am using a bool like I said above. But when the situation gets to something like this,

    x o x x x x x x x x,

    the function is going to take a long time to get to the one good element it needs. On average, 1000 elements would need something like 7.4k repetitions of the search-kill function, which is around n log n I guess.
    Last edited by Metalstrm; February 14th, 2010 at 10:08 AM.

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,297

    Re: What container/ADT should I use for the following?

    Quote Originally Posted by Metalstrm View Post
    monarch, that does sound similar to what I need! Imagine I have these 10 elements in a container, where 'o' is a live element and 'x' is a dead one.

    starting at: o o o o o o o o o o

    The function picks a random live element, does its magic, maybe killing it in the process, and repeats the random search-kill procedure until all the elements are dead. Say it picks element 3, and kills it, giving

    o o x o o o o o o o

    It now randomly picks another element, which has to be live, and therein lies the problem.
    Take a random index, and look if it is alive. If it is, good, return a pointer to it. If it isn't, try again.

    If after 5 (or so) tries you still haven't found a live element, it is time to "rebuild the container". Strip your container of all your dead elements. Look up the vector erase(remove) idiom. The complexity is o(N), every time your container has been emptied of a good amount of it's elements.

    Quote Originally Posted by Metalstrm View Post
    I was thinking of creating a separate list of pointers to chosable elements, and this may be similar to your approach, but I haven't tried it yet...
    Because you would have to update that list every time, it probably isn't a good solution.

  9. #9
    Join Date
    Feb 2010
    Posts
    15

    Re: What container/ADT should I use for the following?

    Thanks monarch, I think I'm going to try that right away!

  10. #10
    Join Date
    Oct 2008
    Posts
    1,137

    Re: What container/ADT should I use for the following?

    Quote Originally Posted by Metalstrm View Post
    monarch, that does sound similar to what I need! Imagine I have these 10 elements in a container, where 'o' is a live element and 'x' is a dead one.

    starting at: o o o o o o o o o o ... giving o o x o o o o o o o
    given that you're picking elements randomly why not simply swapping the just 'killed' element with the last element and making a pop_back() each time ? (using a simple std::vector...)

  11. #11
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,297

    Re: What container/ADT should I use for the following?

    Quote Originally Posted by superbonzo View Post
    given that you're picking elements randomly why not simply swapping the just 'killed' element with the last element and making a pop_back() each time ? (using a simple std::vector...)
    I my case, the order was important, so actually erasing was essential.

    I cannot answer for Metalstrm.

    That is a very good idea though, in general. I'll remember it next time I need to erase an element from a vector.

  12. #12
    Join Date
    Feb 2010
    Posts
    15

    Re: What container/ADT should I use for the following?

    Quote Originally Posted by superbonzo View Post
    given that you're picking elements randomly why not simply swapping the just 'killed' element with the last element and making a pop_back() each time ? (using a simple std::vector...)
    Woah, very nice idea and didn't enter my mind at all. (First day I'm trying my hand at STL containers, so don't flame me too much Still, the concept doesn't need the STL actually...)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center