Is it possible to delete an element from a sorted array with O(1) time?

G

Guest

Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?

Best regards
 
A

Alf P. Steinbach

* Daniel Kraft:
How that?

Any way you like, as long as it's O(1): the only correct answer to the
OP's question -- not amended as you see fit -- is "yes".

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning.

Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

(I assume you actually mean an "array"
and not some special sort of container like linked list).

And first, you will have to find it

Why, and what? That is an extra requirement, not mentioned before now.
If you want help with that new problem, please describe it accurately
and point out why you consider the question to be on-topic in [clc++].
And I don't understand why I should have to find your array for you, or
perhaps it is the OP's array I "have to" find. That's just silly.

(if I understood your question
correctly),

Sorry, that's incorrect: I haven't asked anything.

which takes O(log n) for a sorted array.

I'll take your word for it that your "find it", whatever that means,
takes O(log n) time for whatever you mean by "sorted array". But that's
all we know about what you mean. It could by taken as requirements for
what you mean by "find it", i.e. a partial specification of your
problem, whatever that problem is, but more details would be nice (also,
don't forget to relate it to C++).

Cheers, and hope this helps,

- Alf
 
D

Daniel Kraft

Hi, folks,

How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

And first, you will have to find it (if I understood your question
correctly), which takes O(log n) for a sorted array.

Cheers,
Daniel
 
D

Daniel Kraft

Deleting from any array (sorted or not) takes O(n) except when
Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

I suppose the OP meant "removing" or "erasing" or whatever a single
element from inside the array, which has nothing to do with C++'s delete
(but of course I could have misunderstood the original question).

And as I understood it, he actually means "an array in C++", which is
something like
int foo[256];

which *has* characteristics similar to a std::vector, and which
*requires* O(n) for insertion and removing of elements in the middle.
If the OP was interested in special, optimized data-structures other
than arrays, he would have stated (I believe).
Why, and what? That is an extra requirement, not mentioned before now.

The element, or so to say: I thought the OP wants to delete a element
in the array which equals some value he has stored. Therefore, he first
needs to "find" that element in the array, that is, and iterator
pointing to it.
If you want help with that new problem, please describe it accurately
and point out why you consider the question to be on-topic in [clc++].
And I don't understand why I should have to find your array for you, or
perhaps it is the OP's array I "have to" find. That's just silly.

Yes, that's true. However, it was not me to post this question here.

Rgds,
Daniel
 
A

Alf P. Steinbach

* Daniel Kraft:
I suppose the OP meant "removing" or "erasing" or whatever a single
element from inside the array, which has nothing to do with C++'s delete
(but of course I could have misunderstood the original question).

In that case it's off-topic here.

One must assume topicality unless the question is clearly off-topic.

And as I understood it, he actually means "an array in C++", which is
something like
int foo[256];

Yes, it's like that.

which *has* characteristics similar to a std::vector,

Well, yes, good point: at a sufficient level of abstraction anything's
similar to anything else. But it would be more proper to say that a
std::vector has charactistics similar to a raw array. That's because
std::vector was designed as a higher level array-like structure, using a
raw array as (accessible) internal buffer.

and which
*requires* O(n) for insertion and removing of elements in the middle.

Sorry, that's incorrect. Can't you read? Try reading the text you
quoted above, then, if after Googling etc. this is still unclear, /ask/
(and then preferably cross-posting to [comp.programming] with follow-ups
redirected there -- it's off-topic in [comp.lang.c++]).

If
the OP was interested in special, optimized data-structures other than
arrays, he would have stated (I believe).

Possibly, but it's also possible that the OP is as unclear & confused
as, well, you. I mention this because although the issue you seem to be
hooked on is off-topic here, it's ungood to let such urban myths
propagate. Now try reading the articles I've posted in this thread. :)

Cheers, and hth.,

- Alf
 
K

Kai-Uwe Bux

Alf said:
* Daniel Kraft:

Any way you like, as long as it's O(1): the only correct answer to the
OP's question -- not amended as you see fit -- is "yes".



Sorry, that's incorrect. That depends on the definitions of "delete",
"array", "end", "beginning". In particular, no C++ implementation where
"delete" takes linear time, would be widely used. Also, in the more
general context of computer programming, I think you suffer from the
misconception that general array insertion and deletion is necessarily
O(n), as compared to linked list operations. That is simply incorrect;
you might want to look up cursor gap structures somewhere.

Interesting idea. I read about cursor gap structures when I researched how
to implement text buffers for, but I do not see how they apply to the
problem. As far as I can see, cursor gap structures are well suited if
insertions and deletions have a certain degree of locality (i.e., they
occur in nearby places). But I do not see how one can use this technique to
implement a data structure with constant time random access by index and
constant time entry removal (note that if the structure already has a gap
and the removal happens at a far away place, one would need to move the gap
first).

Could you be a little more specific or provide a reference about how to do
O(1) deletion using a cursor gap?


Best

Kai-Uwe Bux
 
A

Alf P. Steinbach

* Kai-Uwe Bux:
Interesting idea. I read about cursor gap structures when I researched how
to implement text buffers for, but I do not see how they apply to the
problem. As far as I can see, cursor gap structures are well suited if
insertions and deletions have a certain degree of locality (i.e., they
occur in nearby places). But I do not see how one can use this technique to
implement a data structure with constant time random access by index and
constant time entry removal (note that if the structure already has a gap
and the removal happens at a far away place, one would need to move the gap
first).

Could you be a little more specific or provide a reference about how to do
O(1) deletion using a cursor gap?

It seems you already know. ;-) If not then I'm sure e.g. Wikipedia
explains it. I think the Wikipedia article called this "buffer gap".

Of course, the most natural way (what cursor gap is all about) doesn't
support random access, but then, that wasn't asked for even with the
off-topic general programming interpretation of the OP's question.

For random access deletions you can implement "delete an element" in
constant time simply by setting a flag in the element.

When laboring under a preconceived idea of what "delete" has to mean,
the flag technique may sound like a joke. But it's not. For if you
first discard the preconceived idea (e.g., like, later element values
have to be moved, which is the basis of the urban myth), and try to
define what "delete an element" could possibly mean, then first of all
you note that it can't mean to remove the storage, that's impossible.

So at the highest level the meaning has to be that in some way, that
element's /value/ is no longer /logically part/ of the array contents,
and that all other values are still logically part of the array
contents, and that no other value is added to the contents, where
"logically" refers to "via the accessing methods we define". And here
note that even copying array elements to fill the gap, requires some
higher level protocol, higher level access methods, to avoid then
treating indeterminate or duplicated values as part of the array. I.e.
it is a fallacy to think that any element can be deleted without a
higher level access method than the raw array's direct functionality;
the urban myth is in part based on that fallacy.


Cheers, and hth.,

- Alf


Follow-ups set to [comp.programming].
 
T

tom

Interesting idea. I read about cursor gap structures when I researched how
to implement text buffers for, but I do not see how they apply to the
problem. As far as I can see, cursor gap structures are well suited if
insertions and deletions have a certain degree of locality (i.e., they
occur in nearby places). But I do not see how one can use this technique to
implement a data structure with constant time random access by index and
constant time entry removal (note that if the structure already has a gap
and the removal happens at a far away place, one would need to move the gap
first).

Could you be a little more specific or provide a reference about how to do
O(1) deletion using a cursor gap?

Best

Kai-Uwe Bux- Hide quoted text -

- Show quoted text -


To delete an array, you got to:
1. locate it and get a handle(iterate, referece, pointer etc) to it.
(time: log n)
2. delete it by moving the elements after it one position ahead.
(time: n)

To achiveve your goal, you may want to use the associate containers
like: multiset
 
A

Alf P. Steinbach

* tom:
To delete an array, you got to:

I think you mean, "to delete an element of an array".

1. locate it and get a handle(iterate, referece, pointer etc) to it.
(time: log n)

Sorry, that's incorrect.

Generally there's no need to locate an element in order to delete it:
arrays are indexed data structures, where all you need is an index.

And even when there is a need to locate an element with a given value,
it may be possible to compute the relevant index in constant time.

2. delete it by moving the elements after it one position ahead.
(time: n)

Sorry, that's incorrect.

Some ways to delete an array element in constant time have already been
discussed else-thread.

To achiveve your goal, you may want to use the associate containers
like: multiset

What to use depends on the requirements, and no requirements have been
stated.
 
R

red floyd

Daniel said:
How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

[NITPICKY-SMARTALECKY]
OP didn't specify *any* element, he specified *an* element. So yes, in
any array, there exists an element which can be deleted from a sorted
array in O(1) time (namely the last one).
[/NITPICKY-SMARTALECKY]
 
K

Kai-Uwe Bux

red said:
Daniel said:
How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).

[NITPICKY-SMARTALECKY]
OP didn't specify *any* element, he specified *an* element. So yes, in
any array, there exists an element which can be deleted from a sorted
array in O(1) time (namely the last one).
[/NITPICKY-SMARTALECKY]

Similarly: since the OP asked about "a sorted array" as opposed to "any
sorted array", one might as well observe that there are sorted arrays
(e.g., those that consist of identical values) from which _each_ element
can be removed in constant time. <g>

However, it seems a far-fetched assumption that the OP wanted to know
whether there exists some sorted arrays from which at least one element
could be removed in constant time.


Best

Kai-Uwe Bux
 
G

Guest

Hi, folks,
For an array without any order, we can achieve deleting an element
with O(1) time complexity, say we have an unsorted array A, we want to
delete ith element in that array, and i could be any number in [0, n-1]
(here we assume the array is 0-based), here is psuedocode:
A = A[n-1];
A.length -= 1;
We can overwrite the element in the ith position, because the array is
unsorted, we have nothing to worry about, but it doesn't work for a
sorted array, because that will corrupt the order of the array.

Best regards
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,835
Latest member
KetoRushACVBuy

Latest Threads

Top