Verctor/List what is best for my design?

[Sims]

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

so my structure would be something like

struct _POS{
int x;
int y;
};

struct _ITEMLOC{
_POS pos_start;
_POS pos_end;
};

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

something like Search( top, left, bottom, right). And that would return all
the items whose line are within that square, (either partially or totally).

Does anybody know how i could achieve that?

Many thanks in advance.
Sims

[Peter Koch Larsen]

"Sims" <si*********@ho tmail.com> skrev i en meddelelse
news:bu******** ****@ID-162430.news.uni-berlin.de...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

so my structure would be something like

struct _POS{
This is a nonportable name. Use a better name.
int x;
int y;
};

struct _ITEMLOC{
And so is this. The reason: all identifiers containing two consecutive
underscores or beginning with one underscore and an uppercase letter are
reserved for the implementation (the compiler).
_POS pos_start;
_POS pos_end;
};

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

something like Search( top, left, bottom, right). And that would return all the items whose line are within that square, (either partially or totally).
Does anybody know how i could achieve that?

Many thanks in advance.
Sims

There really is no big difference between a list and a vector here, but the
vector would be faster in this case. You just have to look at the entiere
solution to determine what operations are needed. But if you stick to
std::containers and iterators, it should not be a problem to replace the
container and try both alternatives.

Kind regards
Peter

[Chris Theis]

"Peter Koch Larsen" <pk*@mailme.d k> wrote in message
news:40******** *************@d read14.news.tel e.dk...
[SNIP]

There really is no big difference between a list and a vector here, but

the vector would be faster in this case.

IMHO this depends very much on what the user does more often - insert/delete
or search for elements. However, you're of course right that both containers
are easily exchangeable. Thus this discussion might not really lead to
something unless it is tested for the actual case.

[SNIP]

Chris

[Chris Theis]

"Sims" <si*********@ho tmail.com> wrote in message
news:bu******** ****@ID-162430.news.uni-berlin.de...

Hi,
[SNI] something like Search( top, left, bottom, right). And that would return all the items whose line are within that square, (either partially or totally).

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison
to a vector or a list.

Regards
Chris

[Sims]

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison
to a vector or a list.

Regards
Chris

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

How would i do a search for a two dimensional array?

I know how to do a search in a list that is sorted, (in alphabetical order
for example), but how would search for items that are start/end points given
a square?

Also i will have in the region of 200 000 items does that make a dif when it
comes to list/vector?

Sims

[Chris Theis]

"Sims" <si*********@ho tmail.com> wrote in message
news:bu******** ****@ID-162430.news.uni-berlin.de...

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison to a vector or a list.

Regards
Chris

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

How would i do a search for a two dimensional array?

Why would you want to use a 2D array? I'd propose for example a collection
of collections (e.g. vector of vectors) for this.

I know how to do a search in a list that is sorted, (in alphabetical order
for example), but how would search for items that are start/end points given a square?
The search algorithms of the standard library accept a user defined unary
predicate function that can be used to supply your search criterium.
Furthermore you could pre-sort your collection based on the starting
coordinates for example.

Also i will have in the region of 200 000 items does that make a dif when it comes to list/vector?
That's difficult to say. In general vectors are fast when inserting or
deleting at the end of the collections, whereas lists are better if
inserting/deletion is required anywhere. On the other hand vectors provide
random access which is not supplied by the list class. Furthermore (in
comparison to sets for example) vectors are considered to be "slow" for
searching and lists are considered "very slow" with respect to this
requirement. As not many insertion/deletion statements will be needed but
searching is required quite often I'd suggest thinking about using a set<>.

Sims

Chris

[Jerry Coffin]

In article <bu************ @ID-162430.news.uni-berlin.de>,
si*********@hot mail.com says...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).
[ ... ]
So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

IMO, the representation you've chosen is probably less than optimal for
the job at hand, at least assuming you're doing searches relatively
frequently.

For frequent searches, I'd instead represent the points in polar
coordinates, and convert the corners of the rectangle to polar
coordinates as well.

What this will do is let you define an area roughly similar to a slice
of a donut (with a size and position defined by your square), and _very_
quickly eliminate the vast majority of lines that don't fall within that
area. Once you've done that, you can check the remaining lines to see
whether they really intersect your square, or just happen to be close to
it. This test is substantially more expensive, so eliminating it most
of the time will probably be a real win.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <bu************ @ID-162430.news.uni-berlin.de>,
si*********@hot mail.com says...

[ ... ]

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

In that case, you almost certainly want to use a vector rather than a
set or map -- the latter offer logarithmic time on insertions and
deletions, but in exchange for this, they normally lose some searching
speed (at least on most processors).

The reason is simple: they're normally implemented as trees, with each
node individually allocated, so they have poor locality of reference. A
vector is always contiguous, so it generally has substantially better
locality of reference, making it much more cache-friendly.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Karl Heinz Buchegger]

Jerry Coffin wrote:

In article <bu************ @ID-162430.news.uni-berlin.de>,
si*********@hot mail.com says...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

[ ... ]

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

IMO, the representation you've chosen is probably less than optimal for
the job at hand, at least assuming you're doing searches relatively
frequently.

For frequent searches, I'd instead represent the points in polar
coordinates, and convert the corners of the rectangle to polar
coordinates as well.

What this will do is let you define an area roughly similar to a slice
of a donut (with a size and position defined by your square), and _very_
quickly eliminate the vast majority of lines that don't fall within that
area.

Never heard of that idea.
But ... to speed up the testing (using cartesian coordinates), simple techniques
have been developed in the 60's. The OP should consult any literature on
computer graphics and look up the section which talkes about window clipping
using 'end point codes' (Cohen-Sutherland clipping).

Or google:

http://www.google.com
"window clipping end point code"

--
Karl Heinz Buchegger
kb******@gascad .at

[Karl Heinz Buchegger]

Jerry Coffin wrote:

In article <bu************ @ID-162430.news.uni-berlin.de>,
si*********@hot mail.com says...

[ ... ]

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

In that case, you almost certainly want to use a vector rather than a
set or map -- the latter offer logarithmic time on insertions and
deletions, but in exchange for this, they normally lose some searching
speed (at least on most processors).

But still sorting the squares eg. on the left x-coordinate can speed
up the process.
The reason is simple: Walking linearly through the vector and testing
the primitiv against it, once you found a square, which has a left
x-coordinate greater then the maximum x coordinate of the primitive
(lies entirely to the right of the primtive) you know that all other
squares will also be completely right of the primtive and thus the
test can be terminated early.

But as always: profile, if it makes a difference. Especially with
computer graphics it's not always obvious where the time is spent.

--
Karl Heinz Buchegger
kb******@gascad .at