Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #79846

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

Show all headers | View raw

28.05.2021 04:03 Louis Krupp kirjutas:
> On 5/27/2021 2:38 PM, Vir Campestris wrote:
>> 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.
>>
> 
> The update code for vectors loops through elements until it finds a 
> match. In the Code Project page:
> 
>              for  (auto  it = _aPixelActionsVec.begin(); it != 
> _aPixelActionsVec.end(); it++)

One can have efficient search in vectors, beating std::set. But for that 
the vector must be sorted and one must use std::lower_bound(), not 
linear search.

Back to comp.lang.c++ | Previous | Next — Previous in thread | 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