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

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

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

Show all headers | View raw

Scott Lurndal <scott@slp53.sl.home> wrote:
>>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.
> 
> A vector miss will always be O(N).  The average hit will be O(N/2).  From a big-O
> perspective, they're identical complexities.

What do you mean by "vector miss"?

> And either the sort needs to be done after every insert or the insert
> complexity becomes high (due to the need to move all the higher
> elements up one in the vector).

I think the idea was that if you already have a sorted vector (for example
a dataset that you read eg. from a file and sorted once), making repeated
searches for different values will be as fast as, if not even slightly
faster than with std::set (not asymptotically faster, but faster in
terms of wallclock time).

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