About SwSortedObjs

classic Classic list List threaded Threaded
6 messages Options
julien2412 julien2412
Reply | Threaded
Open this post in threaded view
|

About SwSortedObjs

This post was updated on .
Hello,

Taking a look again at fdo#42371 (see https://bugs.freedesktop.org/show_bug.cgi?id=42371), I wonder if SwSortedObjs  could be implemented with a set instead of the vector.
The goal would be to sort automatically the container and insert/remove more easily+quickly.

Of course, the pb is std::set doesn't have [] operator and needs an iterator + advance (or perhaps missed an easy way?) However, leafing through the use of SwSortedObjs (used by other classes) it seems that [] is mainly (exclusively?) used in loops.
So to make things easier to migrate (if it worths it of course! :-)), what about this 3 steps process:
1) Adding an iterator in  SwSortedObjs (quick)
2) use iterator in loops (must be long)
3) replace vector by set + simplify a bit by taking benefit of "set" (perhaps not too quick if tuning is needed)
?

Any idea?

Julien
Miklos Vajna-4 Miklos Vajna-4
Reply | Threaded
Open this post in threaded view
|

Re: About SwSortedObjs

Hi Julien,

On Fri, Mar 21, 2014 at 06:15:24PM -0700, julien2412 <[hidden email]> wrote:

> Of course, the pb is std::set doesn't have [] operator and needs an iterator
> + advance (or perhaps missed an easy way?) However, leafing through the use
> of SwSortedObjs (used by other classes) it seems that [] is mainly
> (exclusively?) used in loops.
> So to make things easier to migrate (if it worths it of course! :-)), what
> about this 3 steps process:
> 1) Adding an iterator in  SwSortedObjs (quick)
> 2) use iterator in loops (must be long)
> 3) replace vector by set (perhaps not too quick if tuning is needed)
> ?
Isn't the difference between std::set and std::map that the key is
separated from the value, i.e. it has an operator[] what you want here?

Miklos

_______________________________________________
LibreOffice mailing list
[hidden email]
http://lists.freedesktop.org/mailman/listinfo/libreoffice

signature.asc (205 bytes) Download Attachment
julien2412 julien2412
Reply | Threaded
Open this post in threaded view
|

Re: About SwSortedObjs

Hi Miklos,

Miklos Vajna-4 wrote
Isn't the difference between std::set and std::map that the key is
separated from the value, i.e. it has an operator[] what you want here?
The [] operator is to retrieve the nth element of the sorted vector. I don't figure out how map would replace vector here? What key to use?
Above all, do you think it worths it to spend some time on searching a way to replace the vector implementation or am I misleading? I must recognize it's just some guessing, I haven't profiled anything.

Julien
Miklos Vajna-4 Miklos Vajna-4
Reply | Threaded
Open this post in threaded view
|

Re: About SwSortedObjs

Hi Julien,

On Sat, Mar 22, 2014 at 06:47:05AM -0700, julien2412 <[hidden email]> wrote:
> The [] operator is to retrieve the nth element of the sorted vector. I don't
> figure out how map would replace vector here? What key to use?

Nah, you just mentioned in general, that you would need a set (which is
a sorted container where the key is not separated from the value) which
has an operator[], and I believe map is just that.

> Above all, do you think it worths it to spend some time on searching a way
> to replace the vector implementation or am I misleading? I must recognize
> it's just some guessing, I haven't profiled anything.

First, if you want to improve performance, then please always profile,
premature optimization just makes the code more complex without too much
benefits. :-)

Second, the logic to decide how to sort an SwSortedObj seems to be
ObjAnchorOrder (sw/source/core/layout/sortedobjs.cxx), if you want to
replace SwSortedObjs with something more generic, maybe use
o3tl::sorted_vector for this purpose?

That works quite well for e.g. SwRedlineTbl already.

Miklos

_______________________________________________
LibreOffice mailing list
[hidden email]
http://lists.freedesktop.org/mailman/listinfo/libreoffice

signature.asc (205 bytes) Download Attachment
julien2412 julien2412
Reply | Threaded
Open this post in threaded view
|

[SOLVED] Re: About SwSortedObjs

Thank you Miklos for the explanation.

Julien
Tomaž Vajngerl Tomaž Vajngerl
Reply | Threaded
Open this post in threaded view
|

Re: About SwSortedObjs

In reply to this post by Miklos Vajna-4
Hi,

On Sat, Mar 22, 2014 at 2:54 PM, Miklos Vajna <[hidden email]> wrote:
> Nah, you just mentioned in general, that you would need a set (which is
> a sorted container where the key is not separated from the value) which
> has an operator[], and I believe map is just that.

He didn't say that. He said that the current implementation has
operator[] but it is used in iterations only, so instead of
operator[], a iterator (which std:set supports ofcourse) would be
enough to replace those cases.

Anyway.. sorted data structures usually use binary search for any
insert which is also currently used (I hope). The only problem is the
vector as for any insert to an arbitrary position it has to copy all
succeeding elements, which can get slow when the number of elements
increases. But if this happens infrequently and the number of elements
is low, it just doesn't really matter.

Regards, Tomaž
_______________________________________________
LibreOffice mailing list
[hidden email]
http://lists.freedesktop.org/mailman/listinfo/libreoffice