G
Guest
Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Best regards
Is it possible to delete an element from a sorted array with O(1)
time?
Best regards
Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
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.
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.
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.
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).
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?
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
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).
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]
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.