Which is more efficient:STL:Set or array?

[Richard Herring]

Re: Which is more efficient:STL:S et or array?

In message <_qGdnawZo-FTgxDfRVn-hA@rcn.net>, Pete Becker
<petebecker@acm .org> writes[color=blue]
>CodeCracker wrote:[color=green]
>> I think I wasn't clear. Let me rehearse what I was telling.
>> I have some items( either simple values as int, float etc or objects (
>> some other classes of mine say FileClass).
>> Now every time somebody calls my function DoSomething() I do a search
>> inside my array to find that item and if it is found I call DoThis()
>> and if not found I call DoThat().
>> But the problem here is that if I use an array implementation I have to
>> write a whole lot of If statement or write a loop where it goes in
>> search of the current item in the array, for which it will make a whole
>> lot of comparison. Instead of doing all this if I use the STL:set
>> containers and insert my items once there and then search for my
>> current item every time in my set will it not be more efficient than
>> my array implementation.
>> Remember I am not creating my container from scratch and using the
>> existing containers only.
>>[/color]
>
>If you're going to populate your array once and then not change it
>you're probably better off with a vector, because it uses less memory.
>
>vector<whateve r> vec(first, last);
>sort(vec.begin (), vec.end());[/color]

And maybe vec.erase(uniqu e(vec.begin(), vec.end()), vec.end()) to remove
duplicates?[color=blue]
>
>when you need to find something, use
>
>find(vec.begin (), vec.end(), X)[/color]

Since it's sorted, binary_search (if you just want to know if X is
there) or lower_bound (if you need an iterator to it) might be better.[color=blue]
>
>Even if you're going to add or remove things occasionally, this is
>probably better. set wins when you add and remove things fairly often.
>[/color]

--
Richard Herring

[Pete Becker]

Re: Which is more efficient:STL:S et or array?

E. Robert Tisdale wrote:[color=blue]
> The object, as you have described it so far, is a set.
> You should implement it with a set template class.
> This will be the most efficient and portable implementation.
> Using any other class template will almost certainly
> result in a sub optimal implementation.
>[/color]

It depends on what's important. As I said earlier, a set will use more
memory than a vector of the same size. In addition, its implementation
requires more code.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Pete Becker]

Re: Which is more efficient:STL:S et or array?

Richard Herring wrote:
[color=blue]
>
> And maybe vec.erase(uniqu e(vec.begin(), vec.end()), vec.end()) to remove
> duplicates?[/color]

Sigh. Maybe. But designing from incomplete information is usually a
waste of time. I see no point in trying to fine-tune this example.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Pete Becker]

Re: Which is more efficient:STL:S et or array?

Richard Herring wrote:
[color=blue]
> In message <_qGdnawZo-FTgxDfRVn-hA@rcn.net>, Pete Becker
> <petebecker@acm .org> writes
>[color=green]
>>
>> when you need to find something, use
>>
>> find(vec.begin( ), vec.end(), X)[/color]
>
>
> Since it's sorted, binary_search (if you just want to know if X is
> there) or lower_bound (if you need an iterator to it) might be better.
>[/color]

Good point. That was the idea, but I used the wrong algorithm.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[E. Robert Tisdale]

Re: Which is more efficient:STL:S et or array?

Richard Herring wrote:
[color=blue]
> It's not what it "is", but what it _does_, that matters.[/color]

You are confused.

An object *is* what it *does*.

[CodeCracker]

Re: Which is more efficient:STL:S et or array?

I conclude that I can continue with set for now with a small set of
elements in it but if I am going to have a >50 elements in the set I
must consider vector and use the unique algo while deleting the
duplicates with erase.
I took the path of set for the ease of use and did not consider any
efficiency of it. I want to delay the effciency topic until my testing
shows I need to optimize my code here.
Is my conclusion correct?

[Pete Becker]

Re: Which is more efficient:STL:S et or array?

CodeCracker wrote:[color=blue]
> I conclude that I can continue with set for now with a small set of
> elements in it but if I am going to have a >50 elements in the set I
> must consider vector and use the unique algo while deleting the
> duplicates with erase.
> I took the path of set for the ease of use and did not consider any
> efficiency of it. I want to delay the effciency topic until my testing
> shows I need to optimize my code here.
> Is my conclusion correct?
>[/color]

Generally speaking, yes. On the other hand, if you're writing CAD
applications, every byte is important, and profiling is irrelevant:
always make things small. <g>

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[sam]

Re: Which is more efficient:STL:S et or array?

Pete Becker wrote:[color=blue]
> CodeCracker wrote:
>[color=green]
>> I think I wasn't clear. Let me rehearse what I was telling.
>> I have some items( either simple values as int, float etc or objects (
>> some other classes of mine say FileClass).
>> Now every time somebody calls my function DoSomething() I do a search
>> inside my array to find that item and if it is found I call DoThis()
>> and if not found I call DoThat().
>> But the problem here is that if I use an array implementation I have to
>> write a whole lot of If statement or write a loop where it goes in
>> search of the current item in the array, for which it will make a whole
>> lot of comparison. Instead of doing all this if I use the STL:set
>> containers and insert my items once there and then search for my
>> current item every time in my set will it not be more efficient than
>> my array implementation.
>> Remember I am not creating my container from scratch and using the
>> existing containers only.
>>[/color]
>
> If you're going to populate your array once and then not change it
> you're probably better off with a vector, because it uses less memory.
>
> vector<whatever > vec(first, last);
> sort(vec.begin( ), vec.end());
>
> when you need to find something, use
>
> find(vec.begin( ), vec.end(), X)
>[/color]
It is sure this using find is very elegant and efficent. But I've been
feeling pluzzl about how to create X for find. Is there any complex
example for defining X? eg. the comparison is not a primitive type like
int, float, etc...

Sam.
[color=blue]
> Even if you're going to add or remove things occasionally, this is
> probably better. set wins when you add and remove things fairly often.
>[/color]

[sam]

Re: Which is more efficient:STL:S et or array?

Pete Becker wrote:
[color=blue]
> Richard Herring wrote:
>[color=green]
>>
>> And maybe vec.erase(uniqu e(vec.begin(), vec.end()), vec.end()) to
>> remove duplicates?[/color]
>[/color]
how about vec.clear()?

Sam
[color=blue]
>
> Sigh. Maybe. But designing from incomplete information is usually a
> waste of time. I see no point in trying to fine-tune this example.
>[/color]

[Pete Becker]

Re: Which is more efficient:STL:S et or array?

sam wrote:[color=blue][color=green]
>>[/color]
> It is sure this using find is very elegant and efficent. But I've been
> feeling pluzzl about how to create X for find. Is there any complex
> example for defining X? eg. the comparison is not a primitive type like
> int, float, etc...
>[/color]

The three-argument version of find (and of binary_search which, as was
pointed out, is the right one to use <g>) takes an object of the type
that the iterator points to. The four-argument version takes an object
of an arbitrary type and a predicate that compares the object that the
iterator points to with the passed object.

struct data
{
int value;
// other stuff
};

struct predicate
{
bool operator()(cons t data& obj, int val)
{ return obj.value == val; }

binary_search(v ec.begin(), vec.end(), 3, predicate());

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Richard Herring]

Re: Which is more efficient:STL:S et or array?

In message <d6l6um$2mi$1@n ntp1.jpl.nasa.g ov>, E. Robert Tisdale
<E.Robert.Tisda le@jpl.nasa.gov > writes[color=blue]
>Richard Herring wrote:
>[color=green]
>> It's not what it "is", but what it _does_, that matters.[/color]
>
>You are confused.[/color]

Not in the least. I consider whether a class matches my requirements,
not what its name happens to be.[color=blue]
>
>An object *is* what it *does*.[/color]

I see you're getting the point. What it does, not what it's named. "is"
was in quotes above for a reason, referring to someone who said:
[color=blue]
>It is either a set or it isn't.[/color]

when they probably meant something more like

It is either being used for its set-like behaviour or it isn't.

--
Richard Herring