Sign in to follow this  
muse1987

Indexed container for fast insertion/removal?

Recommended Posts

Hi. I have an assignment in my company to find or implement a container. It's a random-access container so provides same functionalities as std::vector. However, it cannot be slow for insertion/removal operations. More formally, element insertion/removal (at random position) must be done in O( log(N) ) time in the worst case. Element access can be slower, again, O( log(N) ). So-- O( log(N) ) complexity for insertion/removal/access. I haven't got a clue on how to implement such a beast and the google didn't help me either. Please give me some information. Thanks for advance. [Edited by - muse1987 on October 24, 2008 10:05:41 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by fpsgamer
std::map ... Its a red-black tree.


Sorry if my previous post wasn't clear enough... I meant indexed access by 'random-access', just like std::vector.

For example, if the container has 5 elements as following:
c[0] = 100
c[1] = 200
c[2] = 300
c[3] = 400
c[4] = 500

and I remove second element, it will look like this:
c[0] = 100
c[1] = 300
c[2] = 400
c[3] = 500

If I use std::map then I have to reindex entries and it will take O(N), won't it

Share this post


Link to post
Share on other sites
Or a skip list. IMHO, this would be easier to implement from scratch than a balanced tree, if that's what you'll need to do eventually.

Share this post


Link to post
Share on other sites
Quote:
Original post by muse1987
Quote:
Original post by fpsgamer
std::map ... Its a red-black tree.


Sorry if my previous post wasn't clear enough... I meant indexed access by 'random-access', just like std::vector.

For example, if the container has 5 elements as following:
c[0] = 100
c[1] = 200
c[2] = 300
c[3] = 400
c[4] = 500

and I remove second element, it will look like this:
c[0] = 100
c[1] = 300
c[2] = 400
c[3] = 500

If I use std::map then I have to reindex entries and it will take O(N), won't it


Are you 100% sure this is what your assignment means by element removal?

Your use of the term random-access might be questionable, too. Using the [] operator itself for indexed access doesn't automatically mean random access. std::map supports the [] operator, if that's what you need. But it's not a random access operation. Random access typically is defined to mean the ability to access an arbitrary element in constant time.

Share this post


Link to post
Share on other sites
Why do you need this? What is the function of this container?

But above all, which problem are you trying to solve? If you have frequent additions and removal, then indexed access isn't needed (almost as a rule).

Index is used when it carries some implicit information. For example, item at 7 is an apple. If you allow removal, index loses this meaning.

The only sensible operations in this case are keyed access or iteration. The rest simply aren't needed.

Define the problem first. I'm having hard time believing any company assigning a programmer to a task which is specified with O() conditions.

Quote:
I haven't got a clue on how to implement such a beast and the google didn't help me either


Try searching for Algorithms and Data Structures 101.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
Are you 100% sure this is what your assignment means by element removal?

Your use of the term random-access might be questionable, too. Using the [] operator itself for indexed access doesn't automatically mean random access. std::map supports the [] operator, if that's what you need. But it's not a random access operation. Random access typically is defined to mean the ability to access an arbitrary element in constant time.


Okok. My fault. It's indexed-access container. It has to behave exactly same as std::vector, except complexity for insertion/removal/access ( all O(log(N)) )

Any idea? Thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by muse1987
Quote:
Original post by fpsgamer
std::map ... Its a red-black tree.


Sorry if my previous post wasn't clear enough... I meant indexed access by 'random-access', just like std::vector.

If I use std::map then I have to reindex entries and it will take O(N), won't it
How about a balanced binary tree where the number of children is stored within each node? That way you can recursively decide which path contains your index easily enough, and as far as I can see maintaining the counts when rearranging the tree should be easy (and efficient.)
Also, if you value your sanity, and you can put up with amortized O(log(N)) operations, then I suggest implementing a splay tree rather than a red-black tree or AVL tree ;)

Quote:
Original post by muse1987
Okok. My fault. It's indexed-access container. It has to behave exactly same as std::vector, except complexity for insertion/removal/access ( all O(log(N)) )
Any idea? Thanks
Any chance you could relax these requirements slightly or give us a detailed explanation of what you'll be doing with the container?
For instance, do you need to insert elements in the middle and maintain order after a removal? If not then a dynamic array with shuffle-the-to-back deletion would suffice.
Do you need to modify the list and access the elements simultaneously or is insertion/removal done in a separate pass? If so then perhaps you could flatten a tree into an array or sort a list in a separate pass.

Share this post


Link to post
Share on other sites
You could make your own binary tree. Each node would store the count of the number of items in the left and right subtrees. I believe that lets you find and insert the Nth entry in O(log(N)). Insertion will actually be somewhat more expensive as it needs to update the counts in the parent nodes.

You'd also need to keep the tree reasonably balanced, or it could end up as O(N) performance. The simplest option is to look for nodes which are unbalanced during insertion, and rebalance the appropriate subtree if you find one that's got a big enough difference between the two. Rebalancing is obviously O(size of subtree) which could get somewhat expensive with the worst case ordering of insertions, however every insertion would be O(N) if you didn't do that.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Why do you need this?

An assignment.

Quote:
What is the function of this container?

Same as std::vector

Quote:
But above all, which problem are you trying to solve?

Me? just vector-like container with fast insertion/removal. I'm not sure where they're going to use this but seems like it will be used for very-large text editor being planned in my company.

Quote:
I'm having hard time believing any company assigning a programmer to a task which is specified with O() conditions.

I can understand that. Probably this is the hardest job I've ever faced. [wink]

And thanks for your information

Share this post


Link to post
Share on other sites
Quote:
Original post by muse1987
Quote:
Original post by the_edd
Are you 100% sure this is what your assignment means by element removal?

Your use of the term random-access might be questionable, too. Using the [] operator itself for indexed access doesn't automatically mean random access. std::map supports the [] operator, if that's what you need. But it's not a random access operation. Random access typically is defined to mean the ability to access an arbitrary element in constant time.


Okok. My fault. It's indexed-access container. It has to behave exactly same as std::vector, except complexity for insertion/removal/access ( all O(log(N)) )

Any idea? Thanks


The suggestions of red-black tree and skip-list are appropriate then. std::map could be implemented in terms of either, though it's usually (always?) an rb-tree.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this