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?

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.

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.

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.

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.

Quote:

---

Originally Posted by Lindley

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...

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.

Quote:

---

Originally Posted by Metalstrm

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

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.

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

Quote:

---

Originally Posted by Metalstrm

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...)

Quote:

---

Originally Posted by superbonzo

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.

Quote:

---

Originally Posted by superbonzo

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...)