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

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

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

Show all headers | View raw

Lynn McGuire <lynnmcguire5@gmail.com> wrote:
> "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.

If you are programming something for efficiency, you should know the theory
behind algorithms and data containers. You should unerstand the difference
between linear-time operations and logarithmic-time operations. You should
know how data containers behave internally and what their computational
complexity is.

It's quite obvious that a binary search on a sorted data container (which
is essentially waht std::set does) is going to be exponentially faster
than a linear search on an unsorted data container (the larger the amount
of elements, the exponentially larger the difference in speed).

To a competent programmer something like std::set shouldn't merely be a
black box that does some strange magic inside. The competent programmer
knows what it's doing behind the scenes, and what its strengths and
weaknesses are.

In the same way as std::vector is not good for everything, likewise
std::set is not good for everything. There are many situations where
std::vector (even with a very large number of elements) is actually much
more efficient than std::set. It depends on what exactly you are doing.
(And, of course, std::vector and std::set are not fully interchangeable
in all situations, because std::set is an ordered data container. It does
not preserve the order of insertion, like std::vector does, but always
keeps the elements sorted. That's what allows the logarithmic search,
insertion and deletion of elements.)

When the logarithmic-time insertion, deletion and searching for a large
data container are not needed, std::set can be detrimental to performance
compared to an implementation that uses std::vector efficiently. That's
because std::set allocates memory dynamically for every single element
(and each element has quite some overhead in the form of several pointers
and other data members). This not only means that std::set consumes more
memory, but it's also slower to create new elements and, in some cases,
to traverse the container because the elements are not placed in
contiguous memory locations (and, even if they happened to be, they
would be spaced out a lot more, causing more cache misses).

Depending on the task at hand, std::vector can be as fast as, if not faster
than std::set even when requiring fast searching. This is if you can keep
the vector sorted and use binary searching (std::lower_bound). Of course
this applies mostly if you can generate the entire vector in one go and
then you just need to search but don't need to insert or remove elements.

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)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-28 06: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:05 +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 19:31 +0200
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-28 19:54 +0200
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" scott@slp53.sl.home (Scott Lurndal) - 2021-05-28 20:20 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:18 +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 21:50 +0000
          Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:25 +0200
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 05:42 +0200
            Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-05-29 10:44 +0000
              Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-29 13:00 +0200
        Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Paavo Helde <myfirstname@osa.pri.ee> - 2021-05-29 02:24 +0300
      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:31 +0000
      Re: "STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction)" Juha Nieminen <nospam@thanks.invalid> - 2021-05-30 06:40 +0000

csiph-web