Is there a well tested implementation of a sorted vector container
library to replace set containers?
I need only something very basic:
Use lower_bound and insert to add a new element if it's not there yet.
Use binary_search and erase to remove an element.
I am hoping that binary search performs faster than set::count.
Nandor 10 3651
"na***********@gmail.com дµÀ£º
"
Is there a well tested implementation of a sorted vector container
library to replace set containers?
I need only something very basic:
Use lower_bound and insert to add a new element if it's not there yet.
Use binary_search and erase to remove an element.
I am hoping that binary search performs faster than set::count.
Nandor
I think you can use the standard vector and algorithms. If you
carefully maintain the order of the elements in the vector, you can use
std::binary_search and std::lower_bound with it.
This is what I am doing now but the implementation is a little tricky.
Especially the use of lower_bound and insert. I had a lot of unexpected
bugs and I still don't fully trust my implementation. There are
unexpected issues when I try to insert elements which are extreme
values or when I insert the very first element. I'd like to use
something that's well written and fully tested.
I think you can use the standard vector and algorithms. If you
carefully maintain the order of the elements in the vector, you can use
std::binary_search and std::lower_bound with it.
On Dec 11, 4:46 am, nandor.sie...@gmail.com wrote:
Is there a well tested implementation of a sorted vector container
library to replace set containers?
I need only something very basic:
Use lower_bound and insert to add a new element if it's not there yet.
Use binary_search and erase to remove an element.
I am hoping that binary search performs faster than set::count.
Perhaps you want a std::priority_queue, it's an adaptor wich probably
uses a deque as container. Inserts can probably be slower than in a
set, but I'm not sure that binary_search will be faster than
set::count, they ought to be logaritmic both of them, but only
benchmarking can tell for sure, and it might be
implementation-dependent.
--
Erik Wikström na***********@gmail.com skrev:
Is there a well tested implementation of a sorted vector container
library to replace set containers?
I need only something very basic:
Use lower_bound and insert to add a new element if it's not there yet.
Use binary_search and erase to remove an element.
All the building blocks are there, but why do you avoid std::set in the
first place? When there is a "frequent" use of insertion/deletion
nothing beats std::set if you want predictable performance or access to
a sorted set.
>
I am hoping that binary search performs faster than set::count.
What? That statement makes no sense. Binary search is O(log n), of
course. But what is set::count and how is that related to binary
search?
/Peter er****@student.chalmers.se wrote:
On Dec 11, 4:46 am, nandor.sie...@gmail.com wrote:
Is there a well tested implementation of a sorted vector container
library to replace set containers?
I need only something very basic:
Use lower_bound and insert to add a new element if it's not there yet.
Use binary_search and erase to remove an element.
I am hoping that binary search performs faster than set::count.
Perhaps you want a std::priority_queue, it's an adaptor wich probably
uses a deque as container. Inserts can probably be slower than in a
set, but I'm not sure that binary_search will be faster than
set::count, they ought to be logaritmic both of them, but only
benchmarking can tell for sure, and it might be
implementation-dependent.
set::count should be logarithmic since the average
complexity for count is at most O(log(size()) + count(k)) for
an Associative Container and there is no point in having
non-logarithmic
implementation for Unique Associative Container.
Regards,
--
Anil
I am hoping that binary search performs faster than set::count.
>
What? That statement makes no sense. Binary search is O(log n), of
course. But what is set::count and how is that related to binary
search?
I can test if an element elem is in a set Set using
Set.count(elem).
In a sorted vector I could use binary_serach for the same purpose.
I tested this and count is much slower than binary_serach on Fedora g++.
On Dec 13, 9:44 am, nandor.sie...@gmail.com wrote:
I am hoping that binary search performs faster than set::count.
What? That statement makes no sense. Binary search is O(log n), of
course. But what is set::count and how is that related to binary
search?I can test if an element elem is in a set Set using
Set.count(elem).
In a sorted vector I could use binary_serach for the same purpose.
I tested this and count is much slower than binary_serach on Fedora g++.
Might be because count returns the number of instances of elem that are
in the set (which ought to be only one, but I don't know how it's
implemented, perhaps by using the std::count, algorithm which is O(n).
You might have more success using set::find() and test if the result
equals set::end() or not, if it equals set::end() then elem is not in
the set. Find should be O(log n), same as binary search.
--
Erik Wikström na***********@gmail.com skrev:
I am hoping that binary search performs faster than set::count.
What? That statement makes no sense. Binary search is O(log n), of
course. But what is set::count and how is that related to binary
search?
I can test if an element elem is in a set Set using
Set.count(elem).
In a sorted vector I could use binary_serach for the same purpose.
I tested this and count is much slower than binary_serach on Fedora g++.
Right. I was not aware of the existence of that function before now!
It should not surprise anyone that count is slower than binary search,
as travelling a tree is slower than travelling a vector. Locality is
probably also faster for vector. Still, set is better as soon as you
begin to remove and insert elements, and if that is done frequently,
I'd prefer std::set (or one of the hash-based containers in C++0x).
/Peter na***********@gmail.com wrote:
>
I can test if an element elem is in a set Set using
Set.count(elem).
In a sorted vector I could use binary_serach for the same purpose.
In a set you should use binary search to determine whether an element is
present. That's built in. An element is present if my_set.find(elem) !=
my_set.end().
--
-- Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." ( www.petebecker.com/tr1book)
Pete Becker skrev:
na***********@gmail.com wrote:
I can test if an element elem is in a set Set using
Set.count(elem).
In a sorted vector I could use binary_serach for the same purpose.
In a set you should use binary search to determine whether an element is
present. That's built in. An element is present if my_set.find(elem) !=
my_set.end().
This is what I have always done. Looking at the documentation of count,
it just seems that it would be more convenient to use. Actually, I'd
guees count to be implemented as
this->find(elem) != this->end(), that is exactly as you wrote above,
/Peter This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Kushal |
last post by:
Hello,
I am trying to build a dynamic set/list of data which should be sorted
as each element is inserted. The main criteria in this list is the
speed, the time it takes to insert a element,...
|
by: Der Andere |
last post by:
I need to implement a sorted (ordered) list. STL has no sorted list type as
far as I know. Is there a (straight) way to implement a sorted list using
STL?
BTW: The type of items in the list will...
|
by: Aaron Walker |
last post by:
I want a std::map<std::string, std::string> but I don't want it sorted by keys.
I've been able to simulate this with a vector of pairs and operator.
class umap : public...
|
by: Generic Usenet Account |
last post by:
I have a need for a set operation (actually multi-set operation) on
sorted structures that is not in the STL library. I call it the
set_retain operation. It's kinda similar to the...
|
by: boheman |
last post by:
Hi, I am wondering if there is a simple and quick way to return the
indices of sorted vector.
for example, I have a vector<intx containing {5, 2, 3, 0, 2}.
I can use
sort(x.begin(), x.end(),...
| |
by: Hunk |
last post by:
Would like some advice on the fillowing
I have a sorted list of items on which i require to search and
retrieve the said item and also modify an item based on its identity.
I think an Map stl...
|
by: Hunk |
last post by:
Hi
I have a binary file which contains records sorted by Identifiers
which are strings. The Identifiers are stored in ascending order. I
would have to write a routine to give the record given...
|
by: desktop |
last post by:
In the C++ standard page 472 it says that you can construct a std::set
in linear time if the constructor gets a sorted sequence of elements.
But how is this possible when insert takes logarithmic...
|
by: Matthias Pfeifer |
last post by:
Hi there,
a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a...
|
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,...
|
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...
| |
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,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
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...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
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...
|
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...
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |