Dear All,
I have some code that first populates a std::set, and subsequently does
a mixture of tests-for-presence and deletions. As I understand it,
populating the set will be O(N log N), since each of the N inserts will
be O(log N), and the test and deletes will each be O(log N).
In this case, however, I am populating it with values in ascending order
- it's actually a for loop. I feel that because of this it should be
possible to populate the set in O(N) time. This would be possible if
std::set had an O(1) 'append'-like operation.
Can anyone suggest how I could go about getting this reduced complexity,
if indeed it is possible? I could use a sorted std::vector, which has
O(1) append and could have an O(log N) find using a binary chop (is
there a std::algorithm that will do that for me?), but it doesn't have
an O(log N) delete operation; a sorted std::list does have good delete
performance but lacks O(log N) find. Any ideas?
Cheers,
--Phil. 5 2407
Phil Endecott wrote: Dear All,
I have some code that first populates a std::set, and subsequently does a mixture of tests-for-presence and deletions. As I understand it, populating the set will be O(N log N), since each of the N inserts will be O(log N), and the test and deletes will each be O(log N).
In this case, however, I am populating it with values in ascending order - it's actually a for loop. I feel that because of this it should be possible to populate the set in O(N) time. This would be possible if std::set had an O(1) 'append'-like operation.
Can anyone suggest how I could go about getting this reduced complexity, if indeed it is possible? I could use a sorted std::vector, which has O(1) append and could have an O(log N) find using a binary chop (is there a std::algorithm that will do that for me?), but it doesn't have an O(log N) delete operation; a sorted std::list does have good delete performance but lacks O(log N) find. Any ideas?
Cheers,
--Phil.
Not sure if this is standard, but the SGI STL implementation guarantees
linear time for ranged insertions if the range is already sorted. (I
actually find this a bit suspicious since it's stated so generally. I
suspect they mean this for the case where the set is initially empty.)
Another option is to use insert with hint and use end() as the hint for
each sequential insertion.
Phil Endecott wrote: Dear All,
I have some code that first populates a std::set, and subsequently does a mixture of tests-for-presence and deletions. As I understand it, populating the set will be O(N log N), since each of the N inserts will be O(log N), and the test and deletes will each be O(log N).
In this case, however, I am populating it with values in ascending order - it's actually a for loop. I feel that because of this it should be possible to populate the set in O(N) time. This would be possible if std::set had an O(1) 'append'-like operation.
Can anyone suggest how I could go about getting this reduced complexity, if indeed it is possible? I could use a sorted std::vector, which has O(1) append and could have an O(log N) find using a binary chop (is there a std::algorithm that will do that for me?), but it doesn't have an O(log N) delete operation; a sorted std::list does have good delete performance but lacks O(log N) find. Any ideas?
Cheers,
--Phil.
Set does have an O(1) append operation, but only if you use the two
iterator version of the constructor and the values are in order.
So build the values you want to populate with into a vector then
construct the set
std::vector<int> sorted_values;
for (...)
{
...
sorted_values.push_back(...);
}
std:set<int> s(sorted_values.begin(), sorted_values.end());
john So build the values you want to populate with into a vector then construct the set
std::vector<int> sorted_values; for (...) { ... sorted_values.push_back(...); } std:set<int> s(sorted_values.begin(), sorted_values.end());
john
Or use the hint option that Mark P talks about, I forgot about that.
john
John Harrison wrote: Phil Endecott wrote: populating the set will be O(N log N) I am populating it with values in ascending order - it's actually a for loop. I feel that because of this it should be possible to populate the set in O(N) time.
Set does have an O(1) append operation, but only if you use the two iterator version of the constructor and the values are in order.
Thanks Mark & John for the very quick replies - this is exactly what I
needed.
--Phil.
"Phil Endecott" <ph*******@chezphil.org> wrote in message
news:Li*******************@newsfe6-win.ntli.net... I could use a sorted std::vector, which has O(1) append and could have an O(log N) find using a binary chop (is there a std::algorithm that will do that for me?),
Yes, there is a binary search algorithm but it is called lower_bound. Note
that it is log N only for random access iterators, which vector provides.
The algorithm that one would assume to be doing binary search is called
binary_search, but it returns merely whether the object exists or not :)
Ali This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: cody |
last post by:
Why isn't there an StringBuilder.Append() overload with a StringBuilder as
argument?
Is there a reason that I missed?
|
by: Yves Glodt |
last post by:
Hello,
if I do this:
for row in sqlsth:
________pkcolumns.append(row.strip())
________etc
without a prior:
|
by: Jonathan Buckland |
last post by:
Can someone give me an example how to append data without having to
load the complete XML file.
Is this possible?
Jonathan
|
by: JMCN |
last post by:
hi-
i have inherited an access 97 database that keeps track of the loans.
i have been running into referential intergrity problems when i try to
append new loans to table.
first of all is a...
|
by: David Barger |
last post by:
Greetings,
It appears that an Append Query I run in Access XP is randomly failing
to append a field.
I have payroll data being entered into a payroll database. This data
is exported daily to...
|
by: Michael C via AccessMonster.com |
last post by:
Hello,
I have a table that I am appending 3 seperate tables into. My main problem
is that each time I append the data, it simply adds to the data already there.
That might sound ok, except that...
|
by: audleman |
last post by:
I have an ASP form on my website where a visitor enters information. On
submit, the form calls a stored procedure stores in a MS SQL 2000
database. The stored procedure works most of the time, but...
|
by: John Salerno |
last post by:
If I want to create a list of the form
(where each item is repeated twice after the first one), how might I do
that most efficiently?
Right now I have this:
series =
for x in range(10): ...
|
by: jeremito |
last post by:
I have created a class that inherits from the list object. I want to
override the append function to allow my class to append several
copies at the same time with one function call. I want to do...
|
by: HYRY |
last post by:
I have the following questions, I am using Python 2.4.2
19167152 #1
11306608 #1
1. the address of a.append and list.append is different, can I get the
address of...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |