Re: [Development] implicit sharing and iterators in qt containers

On segunda-feira, 31 de julho de 2017 15:35:15 PDT Mandeep Sandhu wrote: > Well, if fast lookup isn't necessary, then I guess such a "container" is > not really needed, and one can simply implement it using a > QLinkedList (maybe with some added > restrictions). And that's what it should

Re: [Development] implicit sharing and iterators in qt containers

> > > It's still a key-value store in which items are retrieved by key, which > is sort of the definition of a "map". It just has inefficient look-up. > Right. Since this (fast lookup) is so ubiquitous amongst map like containers, I thought this was expected from all associative containers. If

Re: [Development] implicit sharing and iterators in qt containers

On Mon, Jul 31, 2017 at 2:57 PM, Thiago Macieira wrote: > On segunda-feira, 31 de julho de 2017 14:36:59 PDT Mandeep Sandhu wrote: > > > I'd expect to be able to use keys that do not define qHash or qLess. > > > > Why? > > My type key type may be or contain an opaque

Re: [Development] implicit sharing and iterators in qt containers

On 2017-07-31 17:36, Mandeep Sandhu wrote: >> I'd expect to be able to use keys that do not define qHash or qLess. > > Why? Why not? >> Search would be O(n). So be it. > > Well it wouldn't be much of a "map" then, would it? It's still a key-value store in which items are retrieved by key,

Re: [Development] implicit sharing and iterators in qt containers

On segunda-feira, 31 de julho de 2017 14:36:59 PDT Mandeep Sandhu wrote: > > I'd expect to be able to use keys that do not define qHash or qLess. > > Why? My type key type may be or contain an opaque non-orderable type, which would make implementing both qHash and qLess impossible. Right now,

Re: [Development] implicit sharing and iterators in qt containers

> > > I'd expect to be able to use keys that do not define qHash or qLess. > Why? > > Search would be O(n). So be it. > Well it wouldn't be much of a "map" then, would it? I see OrderedMap similar to a QMap, just with a different key ordering scheme. So in that way, constant time lookups would

Re: [Development] implicit sharing and iterators in qt containers

Mandeep Sandhu wrote: > For implicit sharing, I'll have to this instead when a non-const function > is called for the first time on the copy. This will cause a penalty when > calling such a function as the hash has to be repopulated with all entries > (eg: calling remove on the copy will take

Re: [Development] implicit sharing and iterators in qt containers

On segunda-feira, 31 de julho de 2017 13:36:49 PDT Mandeep Sandhu wrote: > > Maybe. I don't know how many would use it and whether it's worth spending > > our > > development time on it, though. > > It might be useful to a lazy programmer though, who doesn't want to > implement it on his/her own

Re: [Development] implicit sharing and iterators in qt containers

> > > Maybe. I don't know how many would use it and whether it's worth spending > our > development time on it, though. > It might be useful to a lazy programmer though, who doesn't want to implement it on his/her own :) It's not really a fundamental container itself, but rather uses a QHash &

Re: [Development] implicit sharing and iterators in qt containers

On segunda-feira, 31 de julho de 2017 11:59:54 PDT Mandeep Sandhu wrote: > On Mon, Jul 31, 2017 at 11:23 AM, Thiago Macieira > wrote: > > > > On segunda-feira, 31 de julho de 2017 11:20:43 PDT Matthew Woehlke wrote: > > > (p.s. This thread should probably be on

Re: [Development] implicit sharing and iterators in qt containers

On Mon, Jul 31, 2017 at 11:23 AM, Thiago Macieira wrote: > On segunda-feira, 31 de julho de 2017 11:20:43 PDT Matthew Woehlke wrote: > > (p.s. This thread should probably be on inter...@qt-project.org...) > > Unless you're planning to submit this code to Qt itself, in

Re: [Development] implicit sharing and iterators in qt containers

> > > So... right now your copy ctor is O(N) and remove is O(1), correct? > Yes. > Implicit sharing makes your copy ctor O(1) and detach() O(N). IOW, > you've just deferred the copy cost until a non-const method is called. > That's basically what COW does... > Yes I understand that. And people

Re: [Development] implicit sharing and iterators in qt containers

On segunda-feira, 31 de julho de 2017 11:20:43 PDT Matthew Woehlke wrote: > (p.s. This thread should probably be on inter...@qt-project.org...) Unless you're planning to submit this code to Qt itself, in which case you have to implement the implicit sharing as Qt requires. -- Thiago Macieira -

Re: [Development] implicit sharing and iterators in qt containers

On 2017-07-31 13:11, Mandeep Sandhu wrote: > Right now, I'm detaching the linked list during copy-construction (and > assignment). Detaching here means re-populating the LL with same entries > and then storing the new LL iterator's in the hash. > > For implicit sharing, I'll have to this instead

Re: [Development] implicit sharing and iterators in qt containers

> > > Your OrderedMap should itself be implicitly shared and clone the linked > list > on detach. > Right now, I'm detaching the linked list during copy-construction (and assignment). Detaching here means re-populating the LL with same entries and then storing the new LL iterator's in the hash.

Re: [Development] implicit sharing and iterators in qt containers

Mandeep Sandhu wrote: > However, due to the issue with implicit sharing & iterators, it's not > possible for a trivial assignment operator & copy c'tor. Is there any way > around it other than making a item-by-item copy of the linked list? Your OrderedMap should itself be implicitly shared and

[Development] implicit sharing and iterators in qt containers

Hi All, I recently stumbled upon an issue where using iterators of a QLinkedList, altered the "copy" of another QLinkedList. On reading the iterator docs, I came across this limitation of Qt containers with implicit sharing: http://doc.qt.io/qt-5/containers.html#implicit-sharing-iterator-problem