[C++] std::set en merge

[Olaf van der Spek]

Wat is de beste manier om twee sets te mergen en het resultaat in de eerste set op te slaan? Wat er met de tweede set gebeurd maakt niet uit.

code:

template<class InIt1, class InIt2, class OutIt>
    OutIt merge(InIt1 first1, InIt1 last1,
      InIt2 first2, InIt2 last2, OutIt x);

Deze functie leek wel handig, maar wat gebruik ik als OutIt voor een set?

[Unicorn]

De laatste parameter is een output iterator. Wanneer je dus de gemergede set kwijt wil in set a, is dat std::inserter( a, a.begin() ).

[Verwijderd]

Begrijp ik het goed dat die set insert'ed items automatisch sorteert ?

Dan lijkt me een std::copy van set2 naar set1 beter (in combinatie met de inserter van Unicorn), aangezien het zowieso gevaarlijk kan zijn om in één statement zowel een inserter als range op te geven die naar dezelfde sequence refereren:

code:

copy(a.begin(), a.end(), inserter(a, a.end())); // lijpe soep voor bv een std::list

[MSalters]

Op zondag 17 maart 2002 16:51 schreef Sneechy het volgende:
Begrijp ik het goed dat die set insert'ed items automatisch sorteert ?

Ja; de iterator bij set::insert is alleen een hint.

Dan lijkt me een std::copy van set2 naar set1 beter (in combinatie met de inserter van Unicorn), aangezien het zowieso gevaarlijk kan zijn om in één statement zowel een inserter als range op te geven die naar dezelfde sequence refereren:

code:

copy(a.begin(), a.end(), inserter(a, a.end())); // lijpe soep voor bv een std::list

Of het gevaarlijk is hangt af van de iterator stabiliteit. deque en list iterators zijn stabiel bij insertion, dus je kunt gewoon naar je eigen begin() kopieeren. De source range iterators blijven gewoon geldig.

Voor set/map is het onzinnig om naar jezelf te kopieeren; je kunt toch geen dubbele elementen krijgen.

Alleen bij vector is het gevaarlijk om naar jezelf te kopieeren met inserter; als de insert een reallocation triggert (reserve() vergeten) dan lees je via invalid iterators.

[Verwijderd]

Op maandag 18 maart 2002 13:02 schreef MSalters het volgende:
deque en list iterators zijn stabiel bij insertion, dus je kunt gewoon naar je eigen begin() kopieeren. De source range iterators blijven gewoon geldig.

Dat voorbeeld-regeltje wat ik daarnet liet zien levert op mijn machine (WinXP, Borland C++ 5.5) voor een std::list een vastlopend programma op. De source range iterators van std::list zijn dus zowieso niet altijd 'stabiel'.

Alleen bij vector is het gevaarlijk om naar jezelf te kopieeren met inserter

Niet dus .

[MSalters]

Op maandag 18 maart 2002 13:24 schreef Sneechy het volgende:

[..]

Dat voorbeeld-regeltje wat ik daarnet liet zien levert op mijn machine (WinXP, Borland C++ 5.5) voor een std::list een vastlopend programma op. De source range iterators van std::list zijn dus zowieso niet altijd 'stabiel'.

Oh ja, misschien had ik erbij moeten zeggen wat stabiliteit betekent. De iterators blijven geldig cq. refereren nog steeds naar hetzelfde object, of het einde. Aangezien je echter voor het einde blijft inserten, wordt dat einde nooit bereikt bij het lezen. Dat ligt niet aan invalide iterators; dat is een buggy algoritme. Je probeert list.size() gelijk te maken aan list.size()+list.size(), en niet verwonderlijk werkt dat dus alleen als size==0.

Een vergelijkbaar probleem is als je een random number generator iterator kopieert naar een list inserter; dat stopt ook niet bij gebrek aan een einde.

[Olaf van der Spek]

Maar je insert toch in container 1 vanuit container 2? In container 2 bereik je het einde dan wel een keer.

[MSalters]

Op dinsdag 19 maart 2002 13:19 schreef OlafvdSpek het volgende:
Maar je insert toch in container 1 vanuit container 2? In container 2 bereik je het einde dan wel een keer.

Check Sneechy's code; hij insert midden in z'n source range. Dus het aantal elementen wat gekopieerd moet worden neemt niet af als er een element gekopieerd is.