Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)"

From	Vir Campestris <vir.campestris@invalid.invalid>
Newsgroups	comp.lang.c++
Subject	Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)"
Date	2021-05-27 21:38 +0100
Organization	A noiseless patient Spider
Message-ID	<s8p002$jvd$1@dont-email.me> (permalink)
References	<s8mavg$2um$1@dont-email.me> <3ryrI.2$EW.1@fx04.iad>

Show all headers | View raw

On 26/05/2021 21:44, Scott Lurndal wrote:
> Lynn McGuire <lynnmcguire5@gmail.com> writes:
>> "STL: Amazing Speed Differences between std::vector and std::set
>> (Observed with an UndoRedoAction)"
>>
>> https://www.codeproject.com/Tips/5303529/STL-Amazing-Speed-Differences-between-std-vector-a
>>
>> I have seen this myself.   We used a std::map for a very large set
>> (>10,000 members) just because it is much faster than std::vector.
> 
> Isn't that computer science 101?   O(N) vs. [O(1) .. O(Log N)] for
> vector  vs std::map (red-black tree).
> 
It's funny, I usually say "Use vector. No really, use vector. Oh, 
perhaps if you have a special case..."

But having glanced through that code It's not clear to me _why_ set 
works so much better for that case. Most likely lots of insertions or 
searches.

Andy

Back to comp.lang.c++ | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Vir Campestris <vir.campestris@invalid.invalid> - 2021-05-27 21:38 +0100
  Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Louis Krupp <lkrupp@invalid.pssw.com.invalid> - 2021-05-27 19:03 -0600
    Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Paavo Helde <myfirstname@osa.pri.ee> - 2021-05-28 08:59 +0300
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 14:44 +0000
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" James Kuyper <jameskuyper@alumni.caltech.edu> - 2021-05-28 11:25 -0400
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 17:23 +0000
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-28 16:45 +0000
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 17:13 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 17:50 +0000
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 21:41 +0000
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-28 18:46 +0200
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-28 17:02 +0000

csiph-web