Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Best regards
7  5918 
>Hi, folks,
> Is it possible to delete an element from a sorted array with O(1)
time?
Yes.
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
--
Got two Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress--so
please use good, old E-MAIL!
>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 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).
>And first, you will have to find it
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
Alf P. Steinbach wrote:
* Daniel Kraft:
>>>Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Yes.
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.
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
On Aug 19, 1:43 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:
Alf P. Steinbach wrote:
* Daniel Kraft:
>>Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
>Yes.
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.
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 Kraft wrote:
>>Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Yes.
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]
red floyd wrote:
Daniel Kraft wrote:
>>>Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?
Yes.
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
this is the most clueless topic I've seen here
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Maximus |
last post by:
Hi,
I was wondering if it is bad to overuse the new & delete operator. In my
application, e.g. I created my own list class and I will have to resize my
variable maybe like 100 times during runtime (if not more). By resize I mean
somthing like:
int* a = new int;
delete a;
a = new int;
delete a;
|
by: Brian Underhill via DotNetMonster.com |
last post by:
I am trying to delete an element from an array. I have an array of 52
elements and I want to search for an element and delete it. Therefore,
making it an array of 51 elements.
is it just
delete MyArray;
any help would be great....thanks
|
by: ssg31415926 |
last post by:
I need to compare two string arrays defined as string such that the
two arrays are equal if the contents of the two are the same, where
order doesn't matter and every element must be unique.
E.g. these two arrays would test as equal:
servers = "Admin"
servers = "Finance"
servers = "Payroll"
servers = "Sales"
|
by: Whybother |
last post by:
I have this
typedef map<__int64, int> Results_Map;
__int64 is defined as 8 bytes ranging from -9,223,372,036.854,775,808 to
9,223,372,036.854,775,807
I have loaded it with approx 34 million hash keys and when the program is
shutting down it takes forever (10+ mins) while its deleting the objects.
The memory it uses according to task manager is varies from 500,000 k then
|
by: Alison Givens |
last post by:
....... that nobody knows the answer.
I can't imagine that I am the only one that uses parameters in CR.
So, my question again:
I have the following problem.
(VB.NET 2003 with CR)
I have a report with a multiple-value discrete value and a rangevalue.
The report shows fine in the viewer, but when I hit the export to pdf
| | |
by: flash |
last post by:
write a program that manipulates arrays of integers. The main program should call three functions: Insert, Delete, and Search. The Insert function should call a function Sort that sorts the array.
Here is a description of the three functions:
Insert: Accepts as input the array and the element you want to insert into the array. The function should insert the element at the end of the array and should call the function Sort to sort the...
|
by: JH Programmer |
last post by:
Hi,
is there any ways that allow us to delete an element in between?
say
int_val: 1
int_val: 2
int_val: 3
|
by: =?Utf-8?B?R2Vvcmdl?= |
last post by:
Hello everyone,
I remembered delete is implemented through operator overloading, but I am
not quite clear.
Could anyone recommend some links about how delete is implemented so that
I can learn and refresh my memory? :-)
|
by: Gestorm |
last post by:
Suppose we have an array a, the idea is: build another array, int
next, for each 0<i<N, next = next position of a in the sorted
array, if a is the max, then next is undefined. For example, let
the unsorted array is
a = {5, 4, 2, 1, 3};
then
next
would be
{undefined, 0, 4, 2, 1}
after sorted.
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
| | |
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
