Array moving left

[niklaus]

Hi,

I have an array in which elements are present .
The number of elements n <= 10^6 .
Now if i delete an element in the array, i want to update the
array by moving all the elements to the left. It is very slow
considering the size of element and i want to access the array
with new updated indexes (it needn't be o(1) it can be atmost O(logn))

ex: 4 3 2 100
arr[2]=2;
once i access the index i delete the element,
So the new array should be 4 3 100, arr[2] should be now 100 etc.

Can someone suggest me a good way to solve this problem . Well i
thought
of STL maps but the problem with them is like if i delete an element in
an array
or map, how do i update the values of other elements to the right of
array (ie. decrease
the indexes by 1). This seems to be a tough task when using STL funcs.
The updation part of indices seems to be difficult

Reg
Nik

 

[Alf P. Steinbach]

* (e-mail address removed):

I have an array in which elements are present .
The number of elements n <= 10^6 .
Now if i delete an element in the array, i want to update the
array by moving all the elements to the left. It is very slow
considering the size of element and i want to access the array
with new updated indexes (it needn't be o(1) it can be atmost O(logn))

ex: 4 3 2 100
arr[2]=2;
once i access the index i delete the element,
So the new array should be 4 3 100, arr[2] should be now 100 etc.

Can someone suggest me a good way to solve this problem .

Depends on the requirements, but chances are that what you need is to
manage the array as a cursor gap array, <url:
http://en.wikipedia.org/wiki/Gap_buffer>, yielding O(1) random
read/write access and O(1) sequential insert/delete access; can't get
very much more efficient than that.

 

[Daniel T.]

I have an array in which elements are present .
The number of elements n <= 10^6 .
Now if i delete an element in the array, i want to update the
array by moving all the elements to the left. It is very slow
considering the size of element and i want to access the array
with new updated indexes (it needn't be o(1) it can be atmost O(logn))

There are two options that I can think of off hand.

Switch to using a std::deque. Erasure of a single element will be much
faster than in an array or std::vector, maybe fast enough to suit your
needs. If not:

Switch to using a std::list. Accelerate access by maintaining references
at various points in the array. Wrap the whole thing in a class that
gives a vector like interface. With this, you can adjust the trade off
between removal time and access time by modifying only the class you
wrap the functionality in.

 

[niklaus]

There are two options that I can think of off hand.

Switch to using a std::deque. Erasure of a single element will be much
faster than in an array or std::vector, maybe fast enough to suit your
needs. If not:

Isn't erasion linear in deque . O(n).
I was thinking of maps or sets but then they don't update the indexes
like i can't
access the elements as arr or arr.at(i) or using some std function

Switch to using a std::list. Accelerate access by maintaining references
at various points in the array. Wrap the whole thing in a class that
gives a vector like interface. With this, you can adjust the trade off
between removal time and access time by modifying only the class you
wrap the functionality in.

The numbers rarely repeat.

 

[Daniel T.]

There are two options that I can think of off hand.

Switch to using a std::deque. Erasure of a single element will be much
faster than in an array or std::vector, maybe fast enough to suit your
needs. If not:

Isn't erasion linear in deque . O(n).
I was thinking of maps or sets but then they don't update the indexes
like i can't
access the elements as arr or arr.at(i) or using some std function

In a deque worst case erasure time is O(n/2). If, for example, most of
your erasures are at the front 10% of the container, then erasure from a
deque will be 9 times faster than from an array or vector. That might,
or might not, suit your needs.

The numbers rarely repeat.

That doesn't much matter. If you were to maintain, say, 10 separate
lists (of 10^5 elements each) then worst case accessing time would be
O(n/10), removal would still be O(1) but the time would be somewhat
greater.

 

[Mark P]

Hi,

I have an array in which elements are present .
The number of elements n <= 10^6 .
Now if i delete an element in the array, i want to update the
array by moving all the elements to the left. It is very slow
considering the size of element and i want to access the array
with new updated indexes (it needn't be o(1) it can be atmost O(logn))

ex: 4 3 2 100
arr[2]=2;
once i access the index i delete the element,
So the new array should be 4 3 100, arr[2] should be now 100 etc.

Can someone suggest me a good way to solve this problem . Well i
thought
of STL maps but the problem with them is like if i delete an element in
an array
or map, how do i update the values of other elements to the right of
array (ie. decrease
the indexes by 1). This seems to be a tough task when using STL funcs.
The updation part of indices seems to be difficult

Reg
Nik

You need to provide more information about how you intend or expect this
data structure to be used. Are the deletions localized? Are they only
at the ends? Do reads and deletions occur in random order?

In the most general case, you ought to be able to modify your favorite
balanced tree so that non-leaf nodes keep track of how many descendant
leaves they have. This would allow O(log n) insertions, deletions, and
indexed lookups. I don't think there's any easy way to extract this
behavior from standard library classes though.