473,320 Members | 1,719 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Array moving left

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

Nov 18 '06 #1
5 2492
* ni*****@gmail.com:
>
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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Nov 18 '06 #2
ni*****@gmail.com wrote:
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.

--
To send me email, put "sheltie" in the subject.
Nov 18 '06 #3

Daniel T. wrote:
ni*****@gmail.com wrote:
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:
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[i] 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.
--
To send me email, put "sheltie" in the subject.
Nov 19 '06 #4
ni*****@gmail.com wrote:
Daniel T. wrote:
ni*****@gmail.com wrote:
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:
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[i] 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.
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.
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.

--
To send me email, put "sheltie" in the subject.
Nov 19 '06 #5
ni*****@gmail.com wrote:
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.
Nov 20 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: David Gray | last post by:
Greetings all, I need to sort an array containing text only values and remove duplicates at the same time. I was thinking of... 1. Loading all values into one array (Array1) 2. Read...
1
by: Sue Adams | last post by:
I have a form on an asp page and am trying to write the code to place the values of all checkboxes that have been selected, into an array. The checkbox values will be used in a dynamic sql statement...
2
by: KalleD | last post by:
Why can I not move the windows taskbar with the SHAppBarMessage function? I am able to use the function for hiding it and other things, but not moving it (I have unchecked the lock). The code is...
1
by: cricketunes | last post by:
Hey folks I am implementing the Huffman encoding algorithm. I have created the tree and its perfect. Now while searching for a node value, I need to write a 0 to the encoded file if I am moving...
11
by: rayreeves | last post by:
How do I declare an array of references to the elements of an array of values? Ray
10
by: cjparis | last post by:
Hello everyone. If anyone can give me a hand I would be gratefull Am doing a site which requires a moving element and have used DHTML to do it. Have a simple Browser detect script to sort IE...
15
by: mcjason | last post by:
I saw something interesting about a grid pair puzzle problem that it looks like a machine when you find each that work out the way it does and say with all the others that work out the way they...
1
anfetienne
by: anfetienne | last post by:
i have this code below that i made....it loads vars from txt file splits it then puts it into an array....once in an array it the brings the pics in from the array to create thumbnails and a larger...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.