sorted vector instead of set

[nandor.sieben]

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

 

[mimi]

"(e-mail address removed) дµÀ£º
"

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.

 

[nandor.sieben]

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.

 

[eriwik]

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:riority_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.

 

[peter koch]

(e-mail address removed) 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

 

[anil.nelakanti]

Perhaps you want a std:riority_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,

 

[nandor.sieben]

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++.

 

[eriwik]

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.

 

[peter koch]

(e-mail address removed) skrev:

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

 

[Pete Becker]

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)

 

[peter koch]

Pete Becker skrev:

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