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

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

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

Show all headers | View raw

On 5/28/21 10:44 AM, Scott Lurndal wrote:
> Paavo Helde <myfirstname@osa.pri.ee> writes:
...
>> 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.

The description for std::lower_bound<T>() says "They are especially
appropriate for random access iterators, because these algorithms do a
logarithmic number of steps through the data structure." (25.8.3p1). For
types other than bool, std::vector<T> is a contiguous container
(22.3.11.1), and therefore has "member types iterator and const_iterator
[that] meet the Cpp17 RandomAccessIterator requirements (23.3.5.6)"
(22.2.1p13). Therefore lower_bound should be O(ln(N)), not O(N/2),
regardless of whether there's a hit or a miss.


> And either the sort needs to be done after every insert or the insert

If lower_bound() fails to find an exact match, the value it does return
will indicate precisely where the new item should be inserted to keep
the vector in order, so there's no need to sort. On the other hand, it
is true that:

> complexity becomes high (due to the need to move all the higher
> elements up one in the vector).

That's true, but it's importance depends upon how frequently the sorted
vector will be searched compared with how frequently it will need to be
modified. The comment you were responding to was only about searching.

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