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

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

Re: "Nearly a quarter-century later, why is C++ still so popular?"

Show all headers | View raw

Siri Cruise <chine.bleu@yahoo.com> wrote:
> Directed graphs are an ideal way of handling complex relations. 
> Encode the relation into a graph; use Tarjan's algorithm to find 
> strongly connected component; factor the graph by SCCs. The 
> resulting reduced graph is a DAG which is the partial order with 
> each SCC being an equivalence class. Do topological sorting on 
> the DAG. You can then deal with the original relation equivalence 
> class by equivalence class either from the sources or sinks. From 
> the sinks means every edge in the SCC is to the same SCC or to a 
> node of a previously processed equivalence class.

If you need to be constantly adding and removing elements from that
graph during the runtime of the program, then sure, it's probably
best to allocate individual elements and handle them by reference
(ie. pointer). Or, if for some reason the elements can be of
different types.

However, if what you describe is "build the graph at startup and
then just read its contents during the execution of the program",
it may well be more efficient to put all the elements in one
single array, and then have connections between the elements
with pointers or indices. This requires no memory management
of any kind (other than, obviously, freeing the array when
the graph isn't needed anymore).

There might even be room for low-level optimization by
rearranging the elements in an optimal way in the array so
that they are accessed as linearly as possible in most cases.
(With individually allocated elements you cannot do this
kind of optimization even if you wanted to.)

Moreover, this approach allows for Data-Oriented Design.
If the graph nodes contain several member variables, and
usually you are only interested in particular ones, you could
do the DOD thing and split the elements into their own
arrays, further increasing cache locality.

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

Thread

"Nearly a quarter-century later, why is C++ still so popular?" Lynn McGuire <lynnmcguire5@gmail.com> - 2021-07-27 14:59 -0500
  Re: "Nearly a quarter-century later, why is C++ still so popular?" Siri Cruise <chine.bleu@yahoo.com> - 2021-07-27 13:48 -0700
    Re: "Nearly a quarter-century later, why is C++ still so popular?" Vir Campestris <vir.campestris@invalid.invalid> - 2021-07-27 22:05 +0100
      Re: "Nearly a quarter-century later, why is C++ still so popular?" Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-07-27 14:23 -0700
        Re: "Nearly a quarter-century later, why is C++ still so popular?" legalize+jeeves@mail.xmission.com (Richard) - 2021-08-05 19:49 +0000
          Re: "Nearly a quarter-century later, why is C++ still so popular?" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-08-19 20:08 +0000
            Re: "Nearly a quarter-century later, why is C++ still so popular?" Siri Cruise <chine.bleu@yahoo.com> - 2021-08-19 18:20 -0700
              Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-08-20 06:13 +0000
              Re: "Nearly a quarter-century later, why is C++ still so popular?" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-08-20 06:17 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Siri Cruise <chine.bleu@yahoo.com> - 2021-08-20 00:03 -0700
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-08-20 11:03 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" mickspud@downthefarm.com - 2021-08-20 15:19 +0000
              Re: "Nearly a quarter-century later, why is C++ still so popular?" "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2021-08-20 14:26 +0200
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Öö Tiib <ootiib@hot.ee> - 2021-08-29 23:40 -0700
    Re: "Nearly a quarter-century later, why is C++ still so popular?" Cholo Lennon <chololennon@hotmail.com> - 2021-07-27 21:01 -0300
    Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-07-28 08:16 +0000
      Re: "Nearly a quarter-century later, why is C++ still so popular?" "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2021-07-28 16:22 +0200
        Re: "Nearly a quarter-century later, why is C++ still so popular?" Siri Cruise <chine.bleu@yahoo.com> - 2021-07-28 07:53 -0700
          Re: "Nearly a quarter-century later, why is C++ still so popular?" "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2021-07-28 21:23 +0200
            Re: "Nearly a quarter-century later, why is C++ still so popular?" Siri Cruise <chine.bleu@yahoo.com> - 2021-07-28 14:16 -0700
          Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-07-29 06:53 +0000
            Re: "Nearly a quarter-century later, why is C++ still so popular?" Öö Tiib <ootiib@hot.ee> - 2021-07-29 09:31 -0700
              Re: "Nearly a quarter-century later, why is C++ still so popular?" MrSpud_71i5@slwgrcbmd1l7yi1.org - 2021-07-30 11:21 +0000
              Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-08-01 08:28 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Öö Tiib <ootiib@hot.ee> - 2021-08-01 05:49 -0700
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-08-02 10:23 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" MrSpud_rLY23@_h_.co.uk - 2021-08-02 15:05 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Öö Tiib <ootiib@hot.ee> - 2021-08-03 04:57 -0700
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Juha Nieminen <nospam@thanks.invalid> - 2021-08-03 12:16 +0000
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Öö Tiib <ootiib@hot.ee> - 2021-08-03 06:01 -0700
                Re: "Nearly a quarter-century later, why is C++ still so popular?" Ian Collins <ian-news@hotmail.com> - 2021-08-08 13:03 +1200
                Re: "Nearly a quarter-century later, why is C++ still so popular?" "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-08-07 22:43 -0700
            Re: "Nearly a quarter-century later, why is C++ still so popular?" Vir Campestris <vir.campestris@invalid.invalid> - 2021-08-01 21:40 +0100
          Re: "Nearly a quarter-century later, why is C++ still so popular?" Chris Vine <chris@cvine--nospam--.freeserve.co.uk> - 2021-07-29 09:53 +0100
          Re: "Nearly a quarter-century later, why is C++ still so popular?" Manfred <noname@add.invalid> - 2021-07-30 13:51 +0200
      Re: "Nearly a quarter-century later, why is C++ still so popular?" Manfred <noname@add.invalid> - 2021-07-30 13:40 +0200
  Re: "Nearly a quarter-century later, why is C++ still so popular?" Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-28 04:05 +0200
    Re: "Nearly a quarter-century later, why is C++ still so popular?" MrSpud_oyam9ltRb0@khlkg.info - 2021-07-28 09:30 +0000
  Re: "Nearly a quarter-century later, why is C++ still so popular?" Bo Persson <bo@bo-persson.se> - 2021-07-28 08:19 +0200
  Re: "Nearly a quarter-century later, why is C++ still so popular?" "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-08-03 13:10 -0700
    Re: "Nearly a quarter-century later, why is C++ still so popular?" Lynn McGuire <lynnmcguire5@gmail.com> - 2021-08-03 18:37 -0500
      Re: "Nearly a quarter-century later, why is C++ still so popular?" Cholo Lennon <chololennon@hotmail.com> - 2021-08-05 18:17 -0300
  Re:"Nearly a quarter-century later, why is C++ still so popular?" Blue Hat <blue_hat@hackershaven.com.jm> - 2021-08-08 13:33 -0500

csiph-web