text:
# bouncing Ball

This topic is 4801 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi to All i've just done a simple program with sdl in order to bounce a ball in a window. The program read two image file: the background and the ball. At each step of the program the background is redrawn and the ball redrawn in a new position. this procedure it seems quite slow because all the background is redrawn each time. So i want to redraw only the zone of the background that was deleted by the ball. Is this way correct? Has SDL a function that help me?

##### Share on other sites
It may seem odd, but it will really be just as fast to redraw everything each frame. You could do the calculations to figure out which protion of the screen needs to be redrawn, but doing this will probably be just as slow as blitting it all. Anyway, when you get to more advanced games, the whole screen will be in motion much of the time, so you will have to redraw it then anyway.

##### Share on other sites
Umm, I am not sure if this will work for what your doing, cause the ball is moving and keeps on moving. But I will post something that will work if you are controlling the ball or w/e. The source code is out of my source that I am creating.

<code>
void DrawScene()
{
DrawIMG(back, xpos-2, ypos-2, 132, 132, xpos-2, ypos-2);
DrawIMG(image, xpos, ypos);

SDL_Flip(screen);
}
</code>

I think (don't hold me to it, as I am VERY sick and not thinking right.) that is what you want. We draw the background as a box that starts 2 pixels before and above the (movable blue) box and ends 2 pixels after and below the box.

I hope this helps. Again I am sick and not thinking right. So if something is not right then I am VERY sorry.

##### Share on other sites
Quote:
 Original post by Chad SmithAgain I am sick and not thinking right. So if something is not right then I am VERY sorry.

That makes two of us, UGH not sure if it's allergies or just a cold. Anyways, Pinzix, there are two approaches as mentioned so far prety much. You can easily just clear the entire screen and redraw everything, or if you only wanted to to update what part has moved, you could do that.

If you want to simply clear the screen and redraw, that is the fastest and easiest way, but not always the best performance wise. Sample code is as follows:
// Clear the screen to blackSDL_FillRect( SDL_GetVideoSurface(), 0, 0);...// Draw...// Calls SDL_FLip if you are using double buffering or simply SDL_UpdateRect if you aren'tSDL_Flip( SDL_GetVideoSurface() );

Now that's it and you'd be all done. If you wanted to use the other method you'd need to do something like this:

1. Create a SDL_Surface the same size as your ball image.
2. At the start of the first frame, before you blit the ball, blit the destination rect of where it's going to be drawn onto the surface you made in step 1.
3. Draw the ball at the desired position.
4. Now before you update the balls, position, you need to store it to know where to draw the surface from step 1 at.
5. Update the ball's position
6. Blit the surface from step 1 at the old position of the ball.
7. Now start at step 2 and repeat again.

That's about it really, it's very straight forward, but as you can see more work and perhaps not as efficient as simply clearing the screen this time. In other more complex cases, such as if you had a static background, and weren't doublr buffering, then you'd want to use the second routine so you only have to draw the background once.

##### Share on other sites
The Cone3d tutorials cover this problem.

http://cone3d.gamedev.net

Look at the second and third one.

Pures

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633298
• Total Posts
3011256
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!


text:
Browse Questions

# There are two radioactive substances X & Y . If Decay constant of Y is 2 times of X . Initially both have equal number of nuclei . Then after n half lives of X rate of disintegration of both are equal . The value of n is

$(a)\;1\qquad(b)\;4\qquad(c)\;3\qquad(d)\;5$

Explanation :
Let
$\lambda x=\lambda \qquad$ & $\qquad\; \lambda y=2 \lambda$
Initially rate of disintegration of X is $\;\lambda N_{0}\;$ and that of Y is $\;2 \lambda N_{0}\;.$
After one half life of X , rate of disintegration of X will becomes $\;\large\frac{\lambda N_{0}}{2}\;$ and that of Y would also be $\;\large\frac{\lambda N_{0}}{2}\;$ ( half - life of B=$\large\frac{1}{2}\;$ half life of A )
So after one half of A or two half lives of B
$(-\large\frac{dN}{dt})_{A}=(-\large\frac{dN}{dt})_{B}$
$n=1$

format: plain


text:
# A particle of charge $-e$ orbits a particle of charge $Ze$, what is its orbital frequency?

A point particle $P$ of charge $Ze$ is fixed at the origin in 3-dimensions, while a point particle $E$ of mass $m$ and charge $-e$ moves in the electric field of $P$.

I have the Newtonian equation of motion as $$- \frac{Ze^2}{4 \pi \epsilon_{0}} \frac{\vec{r}}{r^3} = m \ddot{\vec{r}}$$ I derived this from Newton's law and Coulomb's law.

I then went on to show that the particle moves in a plane by showing it has a constant normal vector.

Can anyone help me find this if the orbit is circular about $P$ what it's orbital frequency is -in terms of the constants we have? I would be extremely grateful.

I have attempted this by parameterizing the orbit, differentiating with respect to time and substituting into the equation of motion, however all I get are two unsolvable differentials equations.

-
Hint: $v=r\omega$ for circular orbits, and $a=v^2/r$. –  Alex R. Oct 9 '12 at 19:11

If you already know that the orbit you're interested in, you don't need to solve differential equations as such. It doesn't take much thought to guess that the speed must be the same everywhere in a cirular orbit, bu symmetry -- so just postulate that the orbit has the standard parameterization of uniform circular motion: $$\vec r(t) = R\langle \cos(2\pi\nu t),\sin(2\pi\nu t)\rangle$$ for some $R$ and $\nu$.

Now compute $\ddot{\vec r}$ given this parameterization and plug into the equation of motion. What is left after some simplification is a system of two non-differential equations from which it should be easy to find the relation between $R$ and $\nu$ that make them true for all $t$.

-
Thank you! I was using parameters as the angle as a function of $t$, if you don't mind, why can we simply state the parameter as time? –  Freeman Oct 9 '12 at 20:06
I'm assuming that the circular motion is uniform, since it doesn't seem to make physical sense for symmetry reasons to have a non-uniform circular motion as a solution. Once we've decided to use uniform circular motion, the form of the parameterization is given up to a choice of radius, frequency (and initial angle which I'm here assuming for simplicity that we absorb into a choice of zero point for the time coordinate) –  Henning Makholm Oct 9 '12 at 20:12
Ah I could kiss you! I've been trying for hours to solve non-linear differential equations.. –  Freeman Oct 9 '12 at 20:16


text:
, 02.12.2019 23:29 Teenabrewer28

# Unit 4 lesson 8 independent practice: finding equivalent ratios c. compost (spicy) angela made some compost using 1 part coffee grounds, 6 parts food waste, 12 parts leaves, and 7 parts grass. she wants to adjust the mix so that it is 1/3 food waste. which adjustment will work? a. add 2 more parts food waste and 2 more parts grass. b. add 4 more parts food waste. c. add 5 more parts food waste. d. add 4 more parts food waste and 4 more parts leaves.

### Another question on Mathematics

Mathematics, 05.02.2019 03:36
Bradley completed latex: \frac{3}{5} 3 5 of his homework. what percent of his homework does he still need to complete?
Mathematics, 05.02.2019 01:13
Job a pays an annual salary of 90,600 , while job b pays 93900. the taxpayer choosing between the two jobs files his federal income tax return with a standard deduction of 5700, only himself as an exemption for 3650, and no additional adjustments to income. after taxes, what is the difference in pay between the two jobs? a. $924b.$825c. $2406d.$3300


text:
## Found 109 Documents (Results 1–100)

100
MathJax
Newest 1st

### Continuous advances in QCD 2002. Arkadyfest. Honoring the 60th birthday of Arkady Vainshstein. Proceedings of the conference, Minneapolis, USA, May 17–23, 2002. (English)Zbl 1027.00035

River Edge, NJ: World Scientific. xii, 646 p. (2002).
MSC:  00B25 81-06 81V05

### Fractals in multimedia. Based on a minisymposium held as part of the IMA annual program on mathematics in multimedia, Minneapolis, MN, USA, January 2001. (English)Zbl 0996.00032

The IMA Volumes in Mathematics and its Applications. 132. New York, NY: Springer. x, 257 p. (2002).

### Resource recovery, confinement, and remediation of environmental hazards. IMA Workshops: Univ. of Minnesota, Minneapolis, MN, USA, January 15–19, 2000 and February 9–13, 2000. (English)Zbl 0996.00049

The IMA Volumes in Mathematics and its Applications. 131. New York, NY: Springer. x, 299 p. (2002).
MSC:  00B25 76-06

### Atmospheric modeling. IMA workshop at the Univ. of Minnesota, Minneapolis, MN, USA, March 15–19, 2000. (English)Zbl 0993.00056

The IMA Volumes in Mathematics and its Applications. 130. New York, NY: Springer. xii, 335 p. (2002).
MSC:  00B25 76-06

### Membrane transport and renal physiology. Workshop at the Univ. of Minnesota, Minneapolis, MN, USA, February 8–12, 1999. (English)Zbl 0993.00064

The IMA Volumes in Mathematics and its Applications. 129. New York, NY: Springer. xv, 394 p. (2002).

### Decision making under uncertainty. Energy and power. IMA workshop, Minneapolis, MN, USA, July 20–24, 1999. (English)Zbl 0990.00072

The IMA Volumes in Mathematics and its Applications. 128. New York, NY: Springer. ix, 154 p. (2002).
MSC:  00B25 90-06 90B50

### Mathematics of the Internet. E-auction and markets. Proceedings of a workshop, Minneapolis, MN, USA, December 2000. (English)Zbl 0983.00063

The IMA Volumes in Mathematics and its Applications. 127. New York, NY: Springer. xi, 161 p. (2002).
MSC:  00B25 91-06 90-06

### Special issue: 14th ACM symposium on computational geometry. Selected papers from the symposium, Minneapolis, MN, USA, June 7–10, 1998. (English)Zbl 0990.00508

MSC:  00B25 65-06
Full Text:

### Computational modeling in biological fluid dynamics. Proceedings of the workshop, which was an integral part of the September 1998 to June 1999 IMA program on “Mathematics in biology”, Univ. of Minnesota, Minneapolis, MN, USA, January 1999. (English)Zbl 0964.00057

The IMA Volumes in Mathematics and its Applications. 124. New York, NY: Springer. x, 238 p. (2001).
Full Text:

### Codes, systems, and graphical models. IMA workshop, Minneapolis, MN, USA, August 2–13, 1999. (English)Zbl 0960.00082

The IMA Volumes in Mathematics and its Applications. 123. New York, NY: Springer. xi, 504 p. (2001).

### Multiple-time-scale dynamical systems. Proceedings of the IMA workshop, Minneapolis, MN, USA, 1997-98. (English)Zbl 0952.00030

The IMA Volumes in Mathematics and its Applications. 122. New York, NY: Springer. xi, 263 p. (2001).
MSC:  00B25 34-06 37-06
Full Text:

### Numerical methods for bifurcation problems and large-scale dynamical systems. Based on two workshops held as part of the 1997–1998 IMA academic year on emerging applications of dynamical systems. (English)Zbl 0940.00036

The IMA Volumes in Mathematics and its Applications. 119. New York, NY: Springer. x, 471 p. (2000).

### Parallel solution of partial differential equations. Proceedings of a workshop, Univ. of Minnesota, Minneapolis, MN, USA, June 9–13, 1997. (English)Zbl 0938.00013

The IMA Volumes in Mathematics and its Applications. 120. New York, NY: Springer. x, 297 p. (2000).
MSC:  00B25 65-06 35-06

### Dynamics of algorithms. Proceedings of the IMA workshop, Minneapolis, MN, USA, November 1997. (English)Zbl 0930.00048

The IMA Volumes in Mathematics and its Applications. 118. New York, NY: Springer. ix, 136 p. (2000).

### Structured adaptive mesh refinement (SAMR) grid methods. Proceedings of a special IMA workshop, Minneapolis, MN, USA, March 12–13, 1997. (English)Zbl 0930.00061

The IMA Volumes in Mathematics and its Applications. 117. New York, NY: Springer. xii, 172 p. (2000).

### Statistical models in epidemiology, the environment, and clinical trials. IMA summer program on Statistics in the health sciences, Univ. of Minnesota, Minneapolis, MN, USA, 1997. (English)Zbl 0930.00056

The IMA Volumes in Mathematics and its Applications. 116. New York, NY: Springer. ix, 274 p. (2000).

### Formal power series and algebraic combinatorics. Selected papers of the 8th conference on formal power series and algebraic combinatorics, Minneapolis, MN, USA, June 25–29, 1996. (English)Zbl 0935.00030

MSC:  00B25 05-06 33-06

### $$FLAC$$ and numerical modeling in geomechanics. Proceedings of the international $$FLAC$$ symposium held in Minneapolis, MN, USA, September 1–3, 1999. (English)Zbl 0942.74002

Rotterdam: A. A. Balkema International Publishers. xv, 512 p. (1999).

Full Text:

Full Text:

### New directions in time series analysis. Part I. Based on the IMA workshop, held July 2-27, 1990 in Minneapolis, MN, USA. (English)Zbl 0761.00003

The IMA Volumes in Mathematics and its Applications. 45. New York: Springer-Verlag. xviii, 389 p. (1992).
MSC:  00B25 62-06 62M10

### Heat transfer in unsteady flows. Proceedings of the 28th national heat transfer conference, July 28-31, 1991, Minneapolis, MN, USA. (English)Zbl 0825.76020

HTD-Vol. 158. New York, NY: American Society of Mechanical Engineers. v, 51 p. (1991).
MSC:  76-06 80-06 00B25 80A20

### Fundamentals of heat transfer in non-Newtonian fluids. Proceedings of the 28th national heat transfer conference, July 28-31, 1991, Minneapolis, MN, USA. (English)Zbl 0825.76021

HTD-Vol. 174. New York, NY: American Society of Mechanical Engineers. v, 73 p. (1991).
MSC:  76-06 76A05 00B25 80A20

### Patterns and dynamics in reactive media. Lectures of a workshop, held at the Institute for Mathematics and its Applications, Minneapolis, MI, USA, October 16-20, 1989. (English)Zbl 0741.00043

The IMA Volumes in Mathematics and Its Applications. 37. New York etc.: Springer-Verlag. 206 p. (1991).

### Dynamical issues in combustion theory. Proceedings of a workshop, held in November 1989, in Minneapolis, MN, USA. (English)Zbl 0742.00074

The IMA Volumes in Mathematics and its Applications. 35. New York etc.: Springer-Verlag. xiii, 257 p. with 64 ill. (1991).
MSC:  00B25 76-06

### Microlocal analysis and nonlinear waves. Proceedings of a workshop which was an integral part of the 1988-1989 IMA program on nonlinear waves. (English)Zbl 0758.00007

The IMA Volumes in Mathematics and its Applications. 30. New York etc.: Springer-Verlag. xiii, 199 p., 18 ill. (1991).
MSC:  00B25 35-06

### Distributed parameter control systems. New trends and applications. Proceedings from a workshop, held August 4-11, 1989, in Minneapolis, MN (USA). (English)Zbl 0725.00019

Lecture Notes in Pure and Applied Mathematics, 128. New York etc.: Marcel Dekker, Inc. x, 516 p. $125. (US and Canada);$ 150.00 (all other countries) (1991).
MSC:  00B25 93-06 49-06

### Directions in robust statistics and diagnostics. Part II. Proceedings of the IMA 1989 summer program ’Robustness, diagnostics, computing and graphics in statistics’, Minneapolis, MN (USA). (English)Zbl 0731.00019

The IMA Volumes in Mathematics and its Applications 34. New York etc.: Springer-Verlag (ISBN 0-387-97531-4). xviii, 380 p. (1991).
MSC:  00B25 62-06

### Directions in robust statistics and diagnostics. Part I. Proceedings of the IMA 1989 summer program ’Robustness, diagnostics, computing and graphics in statistics’, Minneapolis, MN (USA). (English)Zbl 0731.00018

The IMA Volumes in Mathematics and its Applications 33. New York etc.: Springer-Verlag (ISBN 0-387-97530-6). xviii, 252 p. (1991).
MSC:  00B25 62-06

### Radar and sonar. Part I. Lecture notes from the IMA summer program ’Radar and sonar’, June 18-June 29, 1990 in Minneapolis, MN (USA). (English)Zbl 0722.00053

The IMA Volumes in Mathematics and its Applications 32. New York etc.: Springer-Verlag (ISBN 0-387-97516-0). xi, 260 p. (1991).
MSC:  00B25 43-06 93-06

### Mathematical aspects of numerical grid generation. Based on the papers presented at the two minisymposia on numerical grid generation: mathematical aspects, parts I and II, held at the SIAM annual meeting in Minneapolis, MN, USA, in July 1988. (English)Zbl 0743.65002

Frontiers in Applied Mathematics. 8. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xiv, 157 p. (1991).
Reviewer: M.Plum (Köln)

### Nonlinear evolution equations that change type. Based on proceedings of a workshop which was an integral part of the 1988-89 IMA program on nonliner waves, Minneapolis, MN, USA. (English)Zbl 0712.00019

The IMA Volumes in Mathematics and its Applications, 27. New York etc.: Springer-Verlag. xiv, 284 p. DM 68.00 (1990).
MSC:  00B25 76-06 35-06

### Solitons in physics, mathematics, and nonlinear optics. Proceedings of two workshops which were an integral part of the 1988-89 IMA program on nonlinear waves. (English)Zbl 0698.00028

The IMA Volumes in Mathematics and Its Applications, 25. New York etc.: Springer-Verlag. vii, 215 p. DM 58.00 (1990).
MSC:  00B25 35-06

### Two phase flows and waves. Papers based on a symposium held January 3–10, 1989 at the University of Minnesota Institute for Mathematics and Its Applications, Minneapolis, MN (USA). (English)Zbl 0712.00021

The IMA Volumes in Mathematics and Its Applications, 26. New York etc.: Springer-Verlag. x, 164 p. DM 58.00 (1990).
MSC:  00B25 76-06

### Signal processing. Part II: Control theory and applications. Based on lectures held at the IMA, Minneapolis, MN (USA) from June 27 to August 5, 1988. (English)Zbl 0691.00018

The IMA Volumes in Mathematics and Its Applications 23. New York etc.: Springer-Verlag. xiii, 411 p. DM 78.00/hbk (1990).
MSC:  00B25 93-06

### Coding theory and design theory. Part II: Design theory. Proceedings of a workshop which was an integral part of the 1987-88 IMA program on applied combinatorics, Minneapolis, MN(USA). (English)Zbl 0693.00019

The IMA Volumes in Mathematics and its Applications 21. New York etc.: Springer-Verlag (ISBN 0-387-97231-5). xiii, 378 p. (1990).

### Coding theory and design theory. Part I: Coding theory. Proceedings of a workshop which was an integral part of the 1987-88 IMA program on applied combinatorics, Minneapolis, MN(USA). (English)Zbl 0693.00018

The IMA Volumes in Mathematics and its Applications 20. New York etc.: Springer-Verlag (ISBN 0-387-97228-5). xiv, 239 p. (1990).

all top 5

all top 5

all top 3

all top 3


text:
# Contents

## Idea of a situs

A situs is a notion of generalised topological space, and defined as a simplicial object of the category of filters on sets, i.e. a simplicial set equipped, for each $n\geq 0$, with a filter on the set of $n$-simplices such that under any face or degeneration map the preimage of a large set is large. We denote the category of situses by sዋ.

Intuitively, these filters are viewed as additional structure of topological nature on a simplicial set (“the situs structure on a simplicial set”) giving a meaning to the phrase “a simplex is sufficiently small”: by definition, we say “a property holds for all small enough $n$-simplices” iff it holds on a set in the filter, and we refer to sets in the filter as neighbourhoods. This extends to simplicial language the standard intuition of topology: given a topological structure on a set, the precise meaning of the phrase “a property $P_{x_0}(x)$ holds for all points $x$ sufficiently close to a given point $x_0$” is that the property holds on a neighbourhood of $x_0$; intuitively, $x$ near $x_0$ is thought of as small because $x$ approximates $x_0$ up to a small error.

Situses generalise metric and topological spaces, filters, and simplicial sets, and the concept is designed to be flexible enough to formulate categorically a number of standard basic elementary definitions in various fields, e.g. in analysis, limit, (uniform) continuity and convergence, equicontinuity of sequences of functions; in algebraic topology, being locally trivial and geometric realisation; in geometry, quasi-isomorphism; in model theory, stability and simplicity and several Shelah’s dividing lines, e.g. NIP, NOP, NSTOP, $NSOP_i$, $NTP_i$, of a theory.

No homotopy theory for situses has been developed, although the naive definition of an interval object (namely, the simplicial set represented by the linear order $[0,1]$ equipped with some situs structure based on the metric/topology) leads to a directed (not symmetric) notion of homotopy.

## Examples

We now give a number of examples demonstrating the expressive power of the category of situses.

### Simplicial sets as situses

A simplicial set can be equipped with discrete or indiscrete situs structure: %The (in)discrete situs structure on a simplicial set for each $n$, equip $X_n$ with the discrete or indiscrete filter, respectively.

### Metric spaces: uniformly continuous maps and quasi-isometries

Let $M$ be a metric space. View $M$ as a simplicial set represented by the set of points of $M$, and equip each $M^n$ with the filter generated by uniform neighbourhoods of the diagonal, i.e. subsets containing all tuples of small enough diameter. With this situs structure, a map $f:M\to N$ is uniformly continuous iff it induces a morphism $f_\bullet:M_\bullet\to N_\bullet$ of situses. In fact this defines a fully faithful embedding of the category of metric spaces with uniformly continuous maps into the category of situses.

We can also consider a different situs structure capturing the notion of quasi-isomorphism in large scale geometry. Equip each $M^n$ with the filter such that a subset of $M^n$ is large iff it contains all $n$-tuples such that the distance between distinct points is at least $D$, for some $D\geq 0$. With this situs structure, for quasi-geodesic metric spaces, a map $f_\bullet:M_\bullet\to N_\bullet$ is an isomorphism of situses iff $f:M\to N$ is an quasi-isometry.

### A filter as a situs

Given a filter $\mathfrak{F}$ on a set $X$, there is a coarsest situs structure on $X$ viewed as a simplicial set (i.e. the simplicial set $|X|_\bullet$ represented by $X$) such that its filter on the set $X$ of $0$-simplices is finer than $\mathfrak{F}$. Dually, there is a finest situs structure on $|X|_\bullet$ such that its filter on the set of $0$-simplices is coarser than $\mathfrak{F}$. We denote these situses by $|X^\mathfrak{F}|_\bullet^{\operatorname{cart}}$ and $|X^\mathfrak{F}|_\bullet^{\operatorname{diag}}$, respectively.

In fact this gives two fully faithful embeddings of the category of filters into the category of situses

$|-^\mathfrak{F}|_\bullet^{\operatorname{cart}}, |-^\mathfrak{F}|_\bullet^{\operatorname{diag}} : ዋ \to sዋ$

In a similar way one can define two fully faithful embeddings of the category of filters on preorders and continuous monotone maps. We denote these by $X^{\leq\mathfrak{F}}_\bullet^{\operatorname{cart}}$ and $X^{\leq\mathfrak{F}}_\bullet^{\operatorname{diag}}$, respectively.

### Topological and uniform spaces as situses

More generally, given an arbitrary simplicial set $X_\bullet$ and a filter $\mathfrak{F}$ on the set of $n$-simplices $X_n$, there is a coarsest/finest situs structure on $X_\bullet$ such that its filter on the set of $n$-simplices is finer/coarser than $\mathfrak{F}$. Taking $n=0$ and the filter $\mathfrak{F}$ always indiscrete gives two fully faithful embeddings of the category of simplicial sets into the category of situses.

We use this to define situses corresponding to uniform and topological spaces.

#### Uniform spaces as situses

Take a set $X$ and view it as a simplicial set $X_\bullet$ (represented by $X$). A uniform structure on $X$ is a filter on $X\times X$; take the coarsest situs structure with this filter on the set $X\times X$ of $1$-simplices. This is the situs associated with the uniform structure on $X$.

In fact, it is easy to define uniform spaces in terms of situses. A filter on $X\times X$ is a uniform structure iff it is symmetric (i.e. the endomorphism of $X\times X$, $(x,y)\mapsto (y,x)$ permuting the coordinates is continuous) and this construction produces a situs such that the filter on $X\times X\times X$ is the coarsest filter such that the two maps $X^3\to X\times X$, $(x_1,x_2,x_3)\mapsto (x_i,x_{i+1}),i=1,2$ are continuous. This can be used to characterise situses arising from uniform structures as those symmetric situses such that the filter of $X\times X\times X$ has this property. We say that a situs is symmetric iff it factors though the category of non-empty finite sets.

#### Topological spaces as situses

The situs associated to a topological structure on $X$ is defined in the same way starting from the filter of non-uniform neighbourhoods of the diagonal on $X\times X$ defined as consisting of the subsets of form $\bigcup_{x\in X} \{x\}\times U_x$ where $U_x\ni x$ is a not necessarily open neighbourhood of $x\in X$.

A trivial verification shows these constructions define fully faithful embeddings of the categories of topological and of uniform spaces into the category of situses, and in fact there are corresponding forgetful functors to these categories such that the following compositions are the identity:

$Top \to sዋ \to Top$
$UniformSpaces \to sዋ \to UniformSpaces .$

### Cauchy sequences and equicontinuity

A filter $\mathfrak{F}$ on a metric space $M$ is Cauchy iff $\mathfrak{F}^{\operatorname{cart}}_\bullet \to M_\bullet$ is continuous.

A sequence of functions $f_i:L \to M$, $i\in \mathbb{N}$ of metric spaces is uniformly equicontinuous iff the map $(\mathbb{ N}^{cofinite})^{\operatorname{diag}}_\bullet\times L_\bullet \to M_\bullet$ is continuous.

A sequence of functions $f_i:X \to M$, $i\in \mathbb {N}$ from a topological space $X$ to a metric space $M$ is equicontinuous iff the map $(\mathbb{ N}^{cofinite})^{\operatorname{diag}}_\bullet\times X_\bullet \to M_\bullet$ is continuous.

### Limits, compactness, and completeness

An endomorphism of the category $\Delta$ of finite linear orders gives rise to an endomorphism of the category of situses. Of particular interest is the shift endomorphism $\Delta\to\Delta$ adding a new least element (decalage considers the endomorphism adding a new greatest element rather than least) on objects, $n\mapsto 1+n$, and on morphisms, $f:n\to m$ goes to $f[+1]:1+n\to 1+m$, $f(0)=0$, $f[+1](1+i)=1+f(i)$, $0\leq i\leq n$. The object $X_\bullet\circ [+1]$ and morphism $X_\bullet\circ [+1]\to X$ allows one to talk about local properties of $X_\bullet$, e.g. limits and local triviality.

#### Limits via shift endomorphism

For example, taking a limit of a filter $\mathfrak{F}$ on a topological or metric space $X$ corresponds to taking the factorization

$\mathfrak{F}^{\operatorname{diag}}_\bullet\to X_\bullet\circ [+1]\to X_\bullet.$

Indeed, the underlying simplicial set of $\mathfrak{F}^{\operatorname{diag}}_\bullet$ is connected and thus maps to a single connected component of $X_\bullet\circ [+1]=\sqcup_{x\in X} \{x\}\times X_\bullet$ (here we consider the equality of the underlying simplicial sets); continuity of the map $\mathfrak{F} \to X\times X$, $x\mapsto (x_0,x)$ means exactly that the first coordinate $x_0$ is a limit point of $\mathfrak{F}$ on $X$.

#### Compactness and completeness as lifting properties

Diagram chasing reformulation of the notion above allows to define compactness and completeness as lifting properties.

Let $\mathbb{N}^{cofinite}$ and $\mathbb{N}^{\leq cofinite}$ denote the set, resp. the linear order $\mathbb{N}^\leq$, equipped with the filter of cofinite subsets.

A metric space $M$ is complete iff either of the following equivalent conditions holds:

i. $\bot\to (\mathbb{N}^{\leq cofinite})^{\operatorname{cart}}_\bullet \rightthreetimes M_\bullet\circ [+1]\to M_\bullet$.

ii. $\bot\to (\mathbb{N}^{cofinite})^{\operatorname{cart}}_\bullet \rightthreetimes M_\bullet\circ [+1]\to M_\bullet$.

iii. $(\mathbb{N}^{\leq cofinite})^{\operatorname{cart}}_\bullet\to (\mathbb{N}^{\leq cofinite}\cup\{\infty\})^{\operatorname{cart}}_\bullet \rightthreetimes M_\bullet\to\top$.

Such a reformulation raises the question whether the notion of completeness may be defined with help of the archetypal counterexample: is a metric space $M$ complete iff

$M_\bullet\circ [+1]\to M_\bullet \in (\mathbb {R}_\bullet\circ [+1]\to \mathbb{R}_\bullet)^{\rightthreetimes lr} ?$

It also allows to define the completion of a metric space in terms of a weak factorisation system

$M_\bullet \xrightarrow{((\mathbb{N}^{\leq cofinite})^{\operatorname{cart}}_\bullet\to (\mathbb{N}^{\leq cofinite}\cup\{\infty\})^{\operatorname{cart}}_\bullet)^{rl}} \hat M_\bullet \xrightarrow{((\mathbb{N}^{\leq cofinite})^{\operatorname{cart}}_\bullet\to (\mathbb{N}^{\leq cofinite}\cup\{\infty\})^{\operatorname{cart}}_\bullet)^r} \top$

A topological space $X$ is compact iff for each ultrafilter $\mathfrak{U}$ either of the following equivalent conditions holds:

i. $\bot\to \mathfrak{U}^{\operatorname{diag}}_\bullet \rightthreetimes X_\bullet\circ [+1]\to X_\bullet$.

ii. $\mathfrak{U}^{\operatorname{diag}}_\bullet \to (\mathfrak{U}\cup\{\infty\})^{\operatorname{diag}}_\bullet \rightthreetimes X_\bullet\to \top$.

A topological space $K$ is compact iff

$K_\bullet \circ [+1]\to K_\bullet \in (\{\{o\},\{o,1\}\}^{\operatorname{cart}}_\bullet \cup \{\{1\},\{o,1\}\}^{\operatorname{cart}}_\bullet\to \{\{o,1\}\}^{\operatorname{cart}}_\bullet)^{\rightthreetimes lr}.$

Here $\{\{o\},\{o,1\}\}$, $\{\{1\},\{o,1\}\}$, and $\{\{o,1\}\}$ are viewed as filters on the set $\{o,1\}$. (needs verification)

### Local triviality

A map $f:X\to Y$ of topological or metric spaces is locally trivial with fibre $F$ iff in sዋ becomes a direct product with $F_\bullet$ (“globally trivial”) after base-change $Y_\bullet\circ [+1]\to Y_\bullet$. That is,
$f_\bullet:(Y_\bullet\circ [+1])\times_{Y_\bullet} X_\bullet \to Y_\bullet\circ [+1]$ is of form $(Y_\bullet\circ [+1])\times F_\bullet \to Y_\bullet\circ [+1]$.

### Geometric realisation

The notion of geometric realization involves topological spaces and simplicial sets, which both are situses. This allows one to interpret the Besser-Drinfeld-Grayson construction of geometric realisation in sዋ, as follows.

View the standard geometric simplex in $\mathbb{R}^n$ as the space of monotone maps $[0,1]^\leq \to (n+1)^\leq$ with Skorokhod-type metric $dist(f,g):= sup_{x} inf_{y} \{ |x-y| : f(x)=g(y) \}$. The category of situses allows us to view both linear orders as situses: the situs structure on $[0,1]_\bullet$ “remembers” the metric, and the situs structure on $\Delta_n=Hom(-,(n+1)^\leq)$ “remembers” the equality $f(x)=g(x)$, i.e. is the finest situs structure such that the filter on the set of 0-simplices is indiscrete.
Then one may define a situs structure on the inner hom

$HHom_{Skorokhod}([0,1]_\bullet, -) :sዋ\to sዋ$

of the underlying simplicial sets motivated by the definition of Skorokhod metric.

This gives the construction of geometric realisation due to
Besser, Drinfeld, and Grayson. See details at section 3.2 of geometric realization.

### The interval object and homotopy theory

No homotopy theory for situses has been developed. The naive definition of an interval object used to define in sዋ geometric realisation eqipped with some situs structure “remembering” the topology, does not appear very useful, particularly for dealing with situses arising in model theory and the lifting properties defining stability and simplicity (defined below). However, note that the naive interval object $[0,1]^\leq_\bullet$ reminds one of directed topological spaces: it is directed by definition and so would be any naive notion of homotopy associated with it: a homotopy from $A$ to $B$ cannot in general be reversed to get a homotopy from $B$ to $A$.

### Stability and simplicity in model theory

Let us now describe how situses can be used to reformulate two notions of model theory: stability and simplicity of a first-order theory.

#### Stability.

Consider a model $M$ in a language $\mathcal {L}$, and a linear order $I$. For an $r$-ary $\mathcal {L}$-formula $\phi(x_1,...,x_r)$, we say that a sequence $(a_i)_{i\in I}$ of elements of $M$ is $\phi$-indiscernible (with repetitions) iff for either all or none of the subsequences $(a_{i_1},...,a_{i_r}), i_1\le ... \le i_r$ (of distinct elements) the formula $\phi(a_{i_1},...,a_{i_r})$ holds in $M$.

Equip $M^n$ with the filter generated by the sets of all $n$-tuples which are $\phi$-indiscernible with repetitions, where $\phi$ varies through all $\mathcal{L}$-formulas. The situs so obtained is called {the generalised pre-Stone space of $M$ in sዋ} because the forgetful functor $sዋ\to Top$ takes it to the set of elements of $M$ equipped with the preimage of Stone topology?; by this we mean the topology on $M$ generated by sets of elements realising unary $\mathcal{L}$-formulas. There are many variants of this definition, notably instead of being $\phi$-indiscernible one may require being a part of an {infinite} $\phi$-indiscernible sequence, and instead of $M^n$ consider the set of $n$-types $S_n(\emptyset)$ or $S_n(M)$.

We shall reformulate the following characterisation of stable theories as a lifting property in sዋ.

A first-order theory is stable iff in a saturated enough model it holds that each $\phi$-indiscernible sequence of $n$-tuples is in fact a $\phi$-indiscernible set, for each $n\ge 0$ and each formula $\phi$ of the language of the theory.

For $n=1$ this can be reformulated as a lifting property in sዋ as follows.

Fix a linear order $I$.
Let $I^\leq_\bullet:=(T^\leq)^{\operatorname{cart}}_\bullet$ be the situs associated with the preorder $I^\leq$ with the indiscrete filter. Recall that this is the simplicial set $n^\leq \mapsto Hom_{preorders} (n^\leq, I^\leq)$ represented by $I^\leq$ as a linear order, equipped with indiscrete filters. Let $(I^{\leq tails})^{\operatorname{cart}}_\bullet$ denote the situs associated with the preorder $I^\leq$ with the {filter of tails} generated by the subsets containing all elements large enough.

Let $(|I|^{tails})^{\operatorname{cart}}_\bullet$ denote the situs associated with the filter of tails on the set of elements of $I$.

An indiscernible sequence indexed by a linear order $I$ is an injective continuous map $(I^{\leq})^{\operatorname{cart}}_\bullet \to M_\bullet$.

An indiscernible set indexed by $I$ is an injective continuous map $|I|^{\operatorname{cart}}_\bullet \to M_\bullet$.

An eventually indiscernible sequence indexed on a linear order $I$ is an injective continuous map $(I^{\leq tails})^{ cart}_\bullet \to M_\bullet$.

###### Proposition

Let $M$ be a model. The following are equivalent:

i. each $\phi$-indiscernible sequence of elements is in fact a $\phi$-indiscernible set.

ii. the situs $M_\bullet$ is symmetric

iii. the following lifting property holds in sዋ:

$(I^{\leq tails})^{\operatorname{cart}}_\bullet\to (|I|^{tails})^{\operatorname{cart}}_\bullet \rightthreetimes M_\bullet\to \top .$

(Simon,2021) implies that a theory is stable iff the lifting property iii. holds for the situs associated with $M\times M$ considered in the language with arbitrary parameters, for a saturated enough model $M$ of the theory.

#### Simplicity.

The definition of simplicity is not as simple combinatorially.

First let us introduce the situs associated with a model for this purpose; this situs structure is defined to talk about consistency of instances of a formula. Fix a formula $\phi$. As usual, the situs is based on the simplicial set represented by the set of elements of $M$. The filter on $M^n$ is generated by a single set of those tuples $(a_1,...,a_n)$ such that
$M\models \exists x \bigwedge_{1\leq i\leq n} \phi(x,a_i)$. Let us denote this situs by $M_\bullet^{\exists\phi}$ and call it the $\phi$-characteristic situs of model $M$. Note that $\phi$-characteristic situs captures the same structure as the characteristic sequence of a first order formula in (M.Malliaris. The characteristic sequence of a first-order formula. 2010), see also (M.Malliaris. “Edge distribution and density in the characteristic sequence).

##### Finite Cover Property

Let $P_n$ denote the formula $\exists x \wedge_{i\leq n} \phi(x,y_i)$.

###### Theorem

1. $\phi$ has no finite cover property

2. the characteristic sequence $\lt P_n\gt$ has finite support (in terminology of Malliaris, Def.2.5(2))

3. the situs $M^{\{\phi\}}_\bullet$ has finite dimension, i.e. for some $k$ for each $n$ the filter on $M^{\{\phi\}}_\bullet(n)=M^n$ is the coarsest filter such that all the simplicial maps $M^{\{\phi\}}_\bullet(n)=M^n\to M^{\{\phi\}}_\bullet(k)=M^k$ are continuous

4. there is $k$ such that for each $n$ $\exists x \wedge_{i\leq n} \phi(x,y_i)$ holds iff $\exists x \wedge_{i\leq n} \phi(x,y_i)$ for any $k$-element subset $y_{i_1},...,y_{i_k}$

5. there is $k$ such that for each $n$ $\exists x \wedge_{i\leq n} \phi(x,y_i)\leftrightarrow \wedge_{1\leq i_1\le ...\le i_k\le n}\exists x \wedge_{1\leq l\leq k} \phi(x,y_{i_l})$

###### Proof

Items 1 and 2 are Remark 2.6 of Malliaris, item 4 and 5 are both item 2 and item 3 written explicitly.

##### No tree property NTP

The reformulation in terms of situses uses the definition of a simple first-order theory which says that each formula of the theory has NTP (“not the tree property”) see Tent-Ziegler, Def.7.2.1, or 3,\S9 NTP is defined as a lifting property with respect to a morphism involving the following combinatorial structures.

We recall the definition of NTP and a simple theory.

###### Definition

[Tent-Ziegler,7.2.1] 1. A formula $\varphi(x, y)$ has the tree property (with respect to k) if there is a tree of parameters $(a_s\,\,|\,\,\emptyset \neq s \in {}^{\lt\omega}\omega )$ such that:

a) For all $s\in {}^{\lt\omega}\omega$, $(\varphi(x, a_{si} )\,\,|\,\,i \lt\omega )$ is $k$-inconsistent.

b) For all $\sigma\in {}^{\omega}\omega$ $\{\varphi(x, a_s )\,\,|\,\,\emptyset \neq s\subseteq \sigma \}$ is consistent.

1. A theory T is simple if there is no formula $\varphi(x, y)$ with the tree property.

Let $T^\leq$ be an infinitely branching tree of infinite depth, viewed as preorder, and equipped with the indiscrete filter.
We may take $T^\leq$ to be ${}^{\lt\omega}\omega$. Let $T^\leq_\bullet:=(T^\leq)^{cart}_\bullet$ denote the corresponding situs. Recall that by definition $T^\leq_\bullet(n)$ is the set of ordered (weakly increasing) $n$-tuples of vertices of $T$, and there is only one large subset, namely the whole set.

Note that to give a morphism $T^\leq_\bullet \to M_\bullet^{\exists\phi}$ of the underlying simplicial sets is the same as to give a a tree of parameters $(a_s\,\,|\,\,\emptyset \neq s \in {}^{\lt\omega}\omega )$. This morphism is continious iff these parameters satisfy item b, in notation of the definition: indeed, continuity means that the preigame of the large (by definition) set of $\phi$-consistent tuples is large, i.e. the whole set $T^\leq_\bullet(n)$ of ordered tuples, for each $n$.

Let $|T|_\bullet$ be the simplicial set represented by the set $|T|$ of vertices of $T$, namely $|T|_\bullet(n^\leq)=|T|^n$.

###### Definition

Let $|T|^{TP}_\bullet$ denote the simplicial set $|T|_\bullet$ equipped with the $TP$-tautological filter on $|T|_\bullet(n^\leq)$ defined as follows: a subset is not small iff it either contains

1) some tuple in weakly increasing order, or

2) all the lexicographically ordered tuples required to be inconsistent by the tree property with respect to a subtree-counterexample to the tree property.

In more detail, a subset $\epsilon$ is large iff

1’) it contains the subset of tuples in weakly increasing order

2’) for each isomorphic copy of $T'={}^{\lt\omega}\omega$ in $T^\leq$ there is a vertex $v\in T'$ and its immediate (in $T'$) descendants $v_1\leq_{lex}...\leq_{lex} v_k$ such that $(v_1,..,v_k) \in \epsilon \cap T'$. %A verification shows that this indeed defines a filter.

Note that by item (i) the map $T^\leq_\bullet \to |T|_\bullet^{TP}$ is continuous. Also note that no tuple of increasing elements is required to be $\phi$-inconsistent by the tree property.

###### Proposition

The following are equivalent:

i. the formula $\phi$ has NTP with respect $k$ in the model $M$

ii. in sዋ there is no morphism $\tau:T^\leq_\bullet\to M_\bullet^{\exists\phi}$ such that for each tuple $k$-tuple $v_1,..,v_k$, for each $k$, of immediate descendants of the same vertex, $M \models\neg \exists x (\phi(x,\tau(v_1))\wedge ... \wedge \phi(x,\tau(v_n))$

iii. In sዋ the following lifting property holds: $T^\leq_\bullet \to |T|^{TP}_\bullet \rightthreetimes M_\bullet^{\exists\phi}\to \top$

###### Proof

ii. is exactly the definition of NTP for formula $\phi$ as stated in (Tent-Ziegler, Def.7.2.1), cf. 3,\S9. In iii., one only needs to check that the unique lifting is continuous, namely that the set of tuples $(v_1,...,v_k)$ such that $M \models \exists x (\phi(x,\tau(v_1))\wedge ... \wedge \phi(x,\tau(v_k))$ is large. By the definition of the filter, this set is large iff there is an infinitely branching subtree of infinite depth satisfying ii. This implies that ii. and iii. are equivalent.

Finally, let us prove our $TP$-tautological filters are well-defined. We need only to show that the union of any two small sets $X\cup Y$ is small. Assume it is not small. Label each vertex of the tree with the largest $n\lt\omega$ such that the first small subset contains above the vertex all tuples required to be inconsisent in some copy of ${}^{\lt n}\omega$. Above each vertex in $X$ there are at most finitely many vertices in $X$ labelled by the same or greater number. Removing them leaves $X\cup Y$ not small. But then we get that vertices of $X$ are labelled by numbers strictly decreasing along any branch, hence $X$ is of finite depth. Now pick a vertex labelled $0$. This means that below that vertex there is no infinite set of siblings that each lexicographically ordered tuple is in $X$, hence among any infinite set of siblings by Ramsey theorem there is an infinite set of siblings not in $X$, i.e. in $Y$. Hence, $Y$ is not small.

###### Remark

One can similarly define $TP_i$-tautological situs of a tree $T$, for $i=1$, and see that $TP_i$ is defined by a lifting property. The same argument gives lifting properties related to cdt, inp, and sct patterns in classification theory.

###### Remark

This raises the question whether $NTP=NTP_1\&NTP_2$ holds in the category of situses. It seems the standard proof would go through if one defines the corresponding lifting properties carefully enough. In particular, to reflect the use of Ramsey theorem, it may be necessary to replace $|M|_\bullet$ by the simplicial set of types $S^M_\bullet$ where $S^M(n)$ is the set of $n$-types, and also do the same for $T^\leq_\bullet$ and $|T|^{TP}_\bullet$ for quantifier-free types in an appropriate language.

In fact, it would seem that the standard proof of $NTP=NTP_1\&NTP_2$ gives that $T^\leq_\bullet\to |T|_\bullet^{TP}$ is the pushout of $T^\leq_\bullet\to |T|_\bullet^{TP_1}$ and $T^\leq_\bullet\to |T|_\bullet^{TP_2}$, just as diagram chasing considerations show would be sufficient for the corresponding relation between the lifting properties. Though, possibly one needs to modify the definitions of the filters appropriately modified to reflect the need to use Ramsey theorem and consider the tree properties with respect all the finite conjunctions $\&_i\phi(x,y_i)$ of $\phi(x,y)$ at the same time.

###### Remark

The notion of a $\phi$-characteristic situs captures the same structure as the characteristic sequence of a first order formula in (M.Malliaris. The characteristic sequence of a first-order formula. 2010), see also (M.Malliaris. “Edge distribution and density in the characteristic sequence). Moreover, it appears that several properties of characteristic sequences can be defined as lifting properties in the category of situses.

### Shelah’s dividing lines NOP, NSOP, FCP, etc, and tautological filters

We show that several dividing lines of Shelah can also be defined by lifting properties in . Namely, we show that properties NOP, NSOP, and $NSOP_n$, $n\gt 3$, can be defined by lifting properties using tautological filters.

This subsection is preliminary.

Let $\phi(-,-)$ be a binary formula, and let $M^{\{\phi\}}_\bullet$ be the situs on simplicial set $|M|_\bullet$ represented by the set of elements of $M$ where $|M|^n$ is equipped with the filter generated by the set of all $\phi$-indiscernible sequences

$\{(x_1,...,x_n): \forall 1\leq i\le j\leq n, 1\leq k \le l\leq n \phi(x_i,x_j)\leftrightarrow \phi(x_k,x_l)\}\subset |M|^n.$

#### No order property NOP

Recall a formula $\phi(-,-)$ has NOP (no order property) iff there no sequence $(a_i)_{i\in\omega}$ such that

$\phi(a_i,a_j) \leftrightarrow i\leq j$

Let $I^{\leq tails}_\bullet$ be the situs associated with the filter of final segments on the linear order $I$.

###### Definition

Let $|I|^{NOP}_\bullet$ be the simplicial set $|I|_\bullet$ represented by the set $|I|$ of elements of $I$, equipped with NOP-tautological filters defined as follows.

1. A subset $X\subset |I|^3$ is large in the NOP-tautological filter on $|I|^n$ iff

a. it contains each triple $(a_i,a_j,a_k)$ for $i\leq j\leq k$

b. for each infinite increasing subsequence $a_i\in I, i\in\omega$ there is a pair $i\lt j$ such that $(a_i,a_j,a_i)\in X$

1. for $n\neq 3$ the filter on $|I|^n$ is the coarsest filter such that all the simplcial maps $I^n\to I^3$ are continuous.

We call this filter tautological because by definition any large subset contains a “witness” $\phi(a_i,a_j)\leftrightarrow \phi(a_j,a_i)$ of failure of the order property. More precisely, by very definition both maps $a_\bullet: I^{\leq tails}_\bullet\to M^{\{\phi\}}$ and $a_\bullet: |I|^{NOP}_\bullet\to M^{\{\phi\}}$ are continuous iff (a) $a_i$ is a sequence such that $\phi(a_i,a_j)$ whenever $i\leq j$, and (b) each (infinite) subsequence of $(a_i)_{i\in I}$ does not have the order property for $\phi$. A little argument using Ramsey theorem shows that the NOP-tautological filter is indeed a filter, as follows. Assume that the intersection $X\cap Y$ of two large subsets is not large, i.e. there is an infinite subsequence $a_{i_l}$ such that for each $k\lt l$ either $(a_{i_k},a_{i_l},a_{i_k})\notin X$ or $(a_{i_k},a_{i_l},a_{i_k})\notin Y$. This gives a colouring of pairs $i\lt j$ in two colours, and by Ramsey theory there is an infinite clique of the same colour, which by definition means that either $X$ or $Y$ is not large.

The following theorem summarises the considerations above.

###### Theorem

1. formula $\phi$ has NOP

2. there no sequence $(a_i)_{i\in\omega}$ such that $\phi(a_i,a_j) \leftrightarrow i\leq j$

3. the following lifting property holds in sዋ:

$I^\leq_\bullet \to |I|^{NOP}_\bullet \rightthreetimes M^{\{\phi\}}_\bullet\to\top$

###### Proof

Each map $I^\leq_\bullet \to M^{\{\phi\}}_\bullet$ corresponds to a sequence $(a_i)_{i\in I}$ such that $i\leq j\implies \phi(a_i,a_j)$.

If NOP fails, take $(a_i)_{i\in I}$ to be a witness of this. Then evidently the induced map $|I|^{NOP}_\bullet \to M^{\{\phi\}}_\bullet$ is not continuous as there are no witnesses for (b).

Assume NOP. Then for each infinite subsequence there is a witness of NOP, i.e. a tuple as in (b) contained in the preimage of the set of $\phi$-consistent tuples in $M$. Hence, this preimage is large and the induced diagonal map is continuous.

The trick behind the definition of tautological filter works for some other dividing lines such as NSOP and tree properties. We discuss the tree properties in the next section.

#### No strict order property NSOP

To define NSOP-tautological filters we need to define a notion of a witness to failure of NSOP formulated in terms of $\phi$-indiscernible sequences.
The following reformulation is convenient for us: we say that a formula $\phi(-,-)$ has NSOP’ iff there is an infinite sequence $(a_i)_I$ such that

(a) $\phi(a_i,a_j)$ iff $i\leq j$

(b) $\phi(M,a_i)\subset \phi(M,a_j)$ for $i\leq j$.

Failure of this is witnessed by

(a’) a sequence $(a_i,a_j,a_i)$ being $\phi$-indiscernible for $i\lt j$

(b’) both sequences $(x,a_i,a_j)$ and $(x,a_l,a_k)$ being $\phi$-indiscernible for $i\lt j, k\lt l$, and $j\lt l$.

More precisely:

###### Statement

1. If items (a) and (b) hold for $\phi$, then items (a’) and (b’) never hold

1. If items (a’) and (b’) never hold for formula $\phi$ and a long enough sequence $(a_i)_i$, then (a) and (b) holds for subsequence $(a_i)_{0\lt i\lt \omega}$ and formula $\phi'(x,y)$ or $\neg\phi'(x,y)$ where
$\phi'(x,y):=\phi(x,y) \wedge \neg \phi(x,a_0)\wedge \phi(x,a_\omega)$

###### Proof

Indeed, assuming (a), item (b’) means that $\phi(x,a_i),\phi(x,a_j)$, $\neg \phi(x,a_k)$, and $\neg \phi(x,a_l)$, for some $i\lt j, k\lt l$, and $j\lt l$, which does contradict (b).

Item (a’) means that for each $i\lt j$ $\phi(a_i,a_j)\leftrightarrow \neg\phi(a_j,a_i)$, hence by Ramsey theory (a) holds for an infinite subsequence, possibly replacing $\phi$ by $\neg\phi$. So without loss of generality we may assume (a) holds for $\phi$.

Now let us prove that (a) and (b’) imply SOP’ holds for some infinite subsequence $(a_i)_{0\lt i\lt \omega}$ and

$\phi'(x,y):=\phi(x,y) \wedge \neg \phi(x,a_0)\wedge \phi(x,a_\omega)$

We only need to prove that (a) and (b’) implies that (b’’) $\phi'(M,a_i)\subset \phi'(M,a_j)$ for $i\leq j$. Indeed, let $i\lt j$ and $x$ be a counterexample, i.e.
$\phi(x,a_i) \wedge \neg \phi(x,a_0)\wedge \phi(x,a_\omega)$ and $\neg (\phi(x,a_j) \wedge \neg \phi(x,a_0)\wedge \phi(x,a_\omega))$. These formulae imply that $\neg\phi(x,a_j)$ and thus both $(x,a_0,a_i)$ and $(x,a_\omega,a_j)$ are $\phi$-indiscernible.

Hence we define NSOP-tautological filters on $|I\cup I^4|_\bullet$ as:

###### Definition

1. A subset $U\subset |I\cup I^4|^3$ is large in the {\em $NSOP$-tautological filter} on $|I\cup I^4|^3$ iff each infinite subsequence $I'\subset I$ contains a witness of (a’) and (b’), i.e.

i. there is a pair $i\lt j,i,j\in I'$ such that $(a_i,a_j,a_i)\in U$

ii. there are $i\lt j, k\lt l$, and $j\lt l$, $i,j,k,l\in I'$ such that $((i,j,k,l),i,j)\in U$ and $((i,j,k,l),a_l,a_k)\in U$

1. for $n\neq 3$ the filter on $|I\cup I^4|^n$ is the coarsest filter such that all the simplcial maps $|I\cup I^4|^n\to |I\cup I^4|^3$ are continuous.

###### Theorem

1. theory $T$ has NSOP

2. there no formula $\phi$ and an infinite sequence $(a_i)_{i\in\omega}\in M$ satisfying (a’) and (b’) above, for some saturated model $M$

3. for each linear order $I$, model $M$ and formula $\phi$ it holds

$|I|^\leq_\bullet \to |I\cup I^4|^{NSOP}_\bullet \rightthreetimes M^{\{\phi\}}_\bullet\to\top$

###### Proof

Let $(a_i)_{i\in I}$ be a witness for SOP. Take the corresponding map $|I|^\leq_\bullet \to M^{\{\phi\}}_\bullet$. By SOP there are no witnesses of (b’) in $M$, thus wherever I^4 is sent to, the preimage of the subset of $\phi$-consistent tuples will not contain a witness of ii., hence by definition is large in the NTP-tautological filter. Therefore the lifting property fails.

Now assume NOP and let us show the lifting property holds. The map $|I|^\leq_\bullet \to M^{\{\phi\}}_\bullet$ corresponds to a sequence $(a_i)_{i\in I}$ witnessing (a). If this sequence has only finitely many distinct elements, then (b) is witnessed by all tuples where $i,j,k,l$ belong to an infinite constant subsequence, and therefore the preimage of the subset of $\phi$-consistent tuples is large.

Thus we may assume that all $a_i$‘s are distinct. Take the diagonal map sending each $(i,j,k,l)\in I^4$ into a witness of (b’) whenever it exists. Each infinite subsequence also fails SOP, hence there is a witness of (b’) for this. Hence, the preimage of the subset of $\phi$-consistent tuples is large.

#### $NSOP_n$ for $n\gt 3$

Recall that a formula $\phi$ has $SOP_n$ iff there is an infinite sequence $(a_i)_{i\in \omega}$ such that

(a) $\phi(a_i,a_j)$ iff $i\leq j$

($b_n$) there are $(a_i)_{0\leq i \leq n-1}$ such that $\phi((a_i,a_{(i+1)mod\,n})$ for any $0\leq i\leq n$

Say a formula $\phi$ has $SOP'_n$ iff there is an infinite sequence $(a_i)_{i\in \omega}$ such that

(a) $\phi(a_i,a_j)$ iff $i\leq j$

($b'_n$) there are $(a_i)_{0\leq i \leq n-1}$ such that for any $0\leq i\leq n$ the sequence $(a_i,a_{(i+1)mod\,n},a_{(i+2)mod\,n})$ is $\phi$-indiscernible.

It is easy to see that for $n\gt 3$ $SOP'_n(\phi)\leftrightarrow SOP_n(\phi)\vee SOP_n(\neg\phi)$.

Indeed, either there is a 3-cycle $\phi(a_i,a_{(i+1)mod\,n}), \phi(a_{(i+1)mod\,n},a_{(i+2)mod\,n}), \phi(a_{(i+2)mod\,n},a_{i})$ or for each $0\leq i\less n$ $\neg\phi(a_{(i+2)mod\,n},a_{i})$, hence there is an $n$-cycle $n-1,..,(n-1-2k)mod\,n,..(n-1-2n)mod\,n$ for $\neg\phi$.

Let us reformulate this as a lifting property.

Let $|\{0,...,n-1\}|^{cycle}_\bullet$ be the situs associated with the filter on $|\{0,...,n-1\}|^3$ generated by the set of triples $(a_i,a_{(i+1)mod\,n},a_{(i+2)mod\,n})$, $0\leq i\leq n-1$.

###### Theorem

A formula $\phi$ has $NSOP'_n$ iff $\phi$ has NOP and the following lifting property holds:

$|\{0,...,n-1\}|^{diag}_\bullet \to |\{0,...,n-1\}|^{cycle}_\bullet \rightthreetimes M^{\{\phi\}}\to \top$

###### Proof

The proof is straightforward.

### References

Some of these constructions are sketched in the drafts below.

Topology and analysis:

• [1] Misha Gavrilovich. The category of simplicial sets with a notion of smallness. (pdf)

Geometric realisation:

• [2] Misha Gavrilovich, Konstantin Pimenov. Geometric realisation as the Skorokhod semi-continuous path space endofunctor. (pdf)1

Stability and simplicity:

• [TentZiegler] K.Tent, M.Ziegler. A Course in Model Theory. CUP. 2012.

• Maryanthe Malliaris. The characteristic sequence of a first-order formula. J Symb Logic 75, 4 (2010) 1415-1440. (pdf)

• Maryanthe Malliaris. “Edge distribution and density in the characteristic sequence,” Ann Pure Appl Logic 162, 1 (2010) 1-19. pdf

• [Scow2012] Lynn Scow. Characterization of nip theories by ordered graph-indiscernibles. Annals of Pure and Applied Logic, 163(11):1624 – 1641, 2012. (pdf)

• [Simon2021] Pierre Simon. A note on stability and NIP in one variable. (pdf)

• [3] Misha Gavrilovich. Remarks on Shelah’s classification theory and Quillen’s negation. (pdf)

Last revised on May 8, 2021 at 07:58:54. See the history of this page for a list of all contributions to it.


text:
# Thermodynamics & Thermal Energy

1. Dec 9, 2007

### dals2002

(SOLVED)Thermodynamics & Thermal Energy

1. The problem statement, all variables and given/known data
a 6.0m X 8m X 3m room contains air at 20 Degrees Celcius

2. Relevant equations
What is the room's thermal energy

3. The attempt at a solution

now i know that oxygen is a diatomic atom so i used

E(thermal)= 5/2 NkbT= 5/2 nRT

i tried to find the amount of moles by doing pv=nrt -> 5/2 pv=5/2 nRT but i don't know either the pressure exerted neither the number of moles

so i was think to find pV i could use pV= 2/3N*$$(\epsilon)$$(Average Translational kinetic energy)
where $$(\epsilon)$$= 3/2 KbT

so i have one question would it work like that?

Last edited: Dec 9, 2007
2. Dec 9, 2007

### dals2002

any info or help is appreciated, anything cause i have no idea if that process is right

3. Dec 9, 2007

### Roger Wilco

I am not sure, but I believe you could find n by using the volume of the room and the fact that it is at 20 Celsius.

That is since density=mass/volume.

I am just guessing though.

RW

4. Dec 9, 2007

### Andrew Mason

Use n = PV/RT to find the number of moles. Then use:

$$U = \frac{5}{2}nRT$$ where T = temperature in Kelvins, to find the total internal energy of the air.

This, of course, assumes it is a perfect ideal gas so that the heat capacity of the air is 5R/2 at all temperatures which is not true.

AM

Last edited: Dec 9, 2007
5. Dec 9, 2007

### dals2002

yeah i took a look at that but because the temperature is higher than STP i don't know density or mass

6. Dec 9, 2007

### Andrew Mason

You are supposed to assume that it is at atmospheric pressure. It is a room in a building, not a sealed chamber.

AM

7. Dec 9, 2007

### dals2002

WOW thanks this really helped me i didn't knew that the temperature didn't affect the atmospheric pressure, i solved it thanks


text:
# Proof of the Correspondence theorem (group theory)

I'm trying to prove the correspondence theorem differently than my professor did. Is this valid?

Theorem: Let $G$ be a group and $N \le G$ be a normal subgroup. Then there is a $1-1$ correspondence between subgroups of $G/N$ and subgroups of $G$ containing $N$.

Proof: Let *Sub*$(G/N)$ and *Sub*$(G)$ denote the set of subgroups of $G/N$ and subgroups of $G$ containing $N$ respectively. Define the map $f$: *Sub*$(G)$ $\to$ *Sub*$(G/N)$ by $f(H) = H/N$. This map is injective since if $f(H) = f(H')$, by the fact that the cosets partition a group,

$$H = \bigcup_{a \in H} aN = \bigcup_{a \in H'} aN = H'$$

To show that $f$ is surjetive, let $K \le G/N$ be a subgroup. We show that $V = \cup_{\alpha \in K} \alpha$ is a subgroup. Let $x,y \in V$. It follows that $x = an$ and and $y = bn'$ where $a,b \in G$ and $n, n' \in N$. So $xy = (an)(bn') = abn''n$ for some $n'' \in N$ , and hence $xy \in V$. Furthermore, for any $an \in V$ $(an)^{-1} =n^{-1}a^{-1} \in V$, so $V$ is a subgroup which clearly contains $N$, and $f(V) = K$.

-

You get into trouble here:

To show that $f$ is surjetive, let $K \le G/N$ be a subgroup. We show that $V = \cup_{\alpha \in K} \alpha$ is a subgroup. Let $x,y \in V$. It follows that $x = an$ and and $y = bn'$ where $a,b \in G$ and $n, n' \in N$. So $xy = (an)(bn') = abn''n$ for some $n'' \in N$ , and hence $xy \in V$. Furthermore, for any $an \in V$ $(an)^{-1} =n^{-1}a^{-1} \in V$, so $V$ is a subgroup which clearly contains $N$, and $f(V) = K$.

The fact that you never used the hypothesis that $K$ is a group should make you very suspicious. A minor point first: normality of $N$ in $G$ gives you $(an)(bn')=abn''n'$ for some $n''\in N$, not $abn''n$. (You’re using $nb=bn''$.) Let’s assume that that’s been fixed, so that you know that $xy=abm$ for some $m\in N$ and $a,b\in G$; how does that tell you that $xy\in V$?

In order to show that $xy\in V$, you must find an $\gamma\in K$ such that $xy\in\gamma$. This can be done, but you have to work a bit more. Start with the assumption that $x,y\in V$: this means that there are $\alpha,\beta\in K$ such that $x\in\alpha$ and $y\in\beta$, and there are $a,b\in G$ such that $\alpha=aN$ and $\beta=bN$. Now pick your $n_x,n_y\in N$ such that $x=an_x$ and $y=bn_y$, so that $xy=an_xbn_y=abnn_y$ for some $n\in N$ by normality of $N$ in $G$. Clearly, then, $xy\in abN$, and we now want to show that $abN\in K$. The obvious candidate is $\alpha\beta$, so the natural things to do next is to try to prove that $abN=\alpha\beta$. But that’s just proving that $abN=(aN)(bN)$, which you presumably already proved when constructing quotient groups in the first place, so we’ve shown that $V$ is closed under the group operation.

Your argument for closure under taking inverses has the same problem. You can’t say that $n^{-1}a^{-1}\in V$ unless you can show that there is some $\gamma\in K$ such that $n^{-1}a^{-1}\in\gamma$. If $a\in\alpha\in K$, the obvious candidate is $\alpha^{-1}$, where the inverse is taken in $G/N$, and you can finish off the argument much as I did the one for closure under the operation.

-
Would this prove closure under inverse? Let $an \in V$. Since $aN \in K$, $a^{-1}N = Na^{-1} \in K$ and so $n^{-1}a^{-1} \ in V$ –  Jonah777 Sep 23 '12 at 6:44
@1111: It would be better to be a little more explicit: If $a\in V$, then $a\in\alpha$ for some $\alpha\in K$. Since $a\in aN$, we can even say that $aN=\alpha\in K$, so $a^{-1}N=(aN)^{-1}=\alpha^{-1}\in K$, since $K$ is a subgroup of $G/N$. And $a^{-1}\in a^{-1}N$, so $a^{-1}\in V$. –  Brian M. Scott Sep 23 '12 at 6:46


text:
# Proving generating functions equality

What do you use to prove the following equality (and possibly more general ones of the kind)?

\begin{align*}\sum_{r,s,t} \frac{q^{r^2+rs+s^2+st+t^2}}{(q)_r (q)_s (q)_t} z_1^{r+s} z_2^{s+t} = \sum_{a,b} \frac{q^{a^2-ab+b^2}}{(q)_a (q)_b} z_1^a z_2^b \end{align*}

Thanks!

-
I know it should be easy to prove it, but I am trying to pin down the simplest way to do it. It is mentioned on pg 28 of arxiv.org/pdf/hep-th/9308079.pdf. Since I am not an expert in the field, I was hoping I could get a hint from some of you... –  Andrew Jun 26 '12 at 20:01
You might want to start with 2.3.2 in my survey: math.ucla.edu/~pak/papers/psurvey.pdf –  Igor Pak Jun 27 '12 at 0:02

I keep the notation $(q)_s=\prod_{i=1}^s(1-q^i)$, and in addition set $$\binom{a}{s}_q=\frac{(q)_a}{(q)_s(q)_{a-s}},$$the Gaussian binomial coefficient.

Comparing coefficients, the question amounts to showing that $$\sum_s\binom{a}{s}_q\binom{b}{s}_q(q)_sq^{(a-s)(b-s)}=1.$$

This, however follows immediately from induction over $a$: The assertion is obvious for $a=0$. Now suppose $a\ge1$. Use $$\binom{a}{s}_q=q^s\binom{a-1}{s}_q+\binom{a-1}{s-1}_q$$ to replace $\binom{a}{s}_q$. The contribution from the first summand of the right hand side gives $q^b$ (I omit the trivial calculation), by applying the induction hypothesis to $a-1$. In order to handle the contribution from the second summand, we note that $$\binom{b}{s}_q(q)_s=(1-q^b)(q)_{s-1}\binom{b-1}{s-1}_q.$$ So, applying the induction hypothesis for $a-1$ once again, we see that this other contribution is $1-q^b$. Now $q^b+(1-q^b)=1$ yields the result.

-

Actually, I believe the generating functions are in fact not equal. They differ on the coefficient for $z_1 z_2$. The left-hand side is $1+z_1+z_2+2z_1 z_2 + \cdots$, and the right-hand side is $1+z_1+z_2+z_1 z_2 /q + \cdots$ (this is assuming you start the running variables all at 0; starting some of them at 1 doesn't fix this inequality).

-
I don't see how: e.g. r+s=1 and s+t = 1 gives r=0, s=1, t=0, and r = 1, s=0, t=1, which leads to \frac{q}{(q)} + \frac{q^2}{(q)^2}, which is the same when you take a=1 and b=1 and calculate the corresponding coefficient –  Andrew Jun 27 '12 at 11:58
I agree with your calculation for the coefficient on the LHS (which simplifies to just $\frac{q}{(q)} + \frac{q^2}{(q)^2} = 1 + 1 = 2$). But as I said, the RHS coefficient (for $a=b=1$) is $q^{1-1+1}/(q)^2 = q/q^2 = 1/q$. There's a fine chance that I'm doing something quite stupid, in which case, let me know! –  Pat Devlin Jun 27 '12 at 14:08
OK, i understand now - in my notation $(q)_a$ means $\prod_{i=1}^{a}(1−q^i)$. Sorry for not clarifying... – Andrew 0 secs ago –  Andrew Jun 27 '12 at 14:16
Ah! I had guessed it was the Pochhammer symbol. –  Pat Devlin Jun 27 '12 at 14:26
Andrew: perhaps edit your original question too to clarify the notation, so that other readers aren't confused. –  Zsbán Ambrus Sep 5 '12 at 16:54


text:
# Modern C++¶

## Copy Elision / Return Value Optimization (RVO)¶

Copy elision is one of the two forms of optimization, alongside allocation elision and extension, that is allowed to change the side effects.

Sometimes copy elision is also called return value optimization (RVO) or named return value optimization (NRVO).

In the following example, even though no optimization flag is used, the copy is optimized out.

### Make a Tracker Class for Copy¶

To show that the copy construction is not called, we make a help class:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class IsCopied { public: static IsCopied & instance() { static IsCopied inst; return inst; } IsCopied & void on() { m_status = true; return *this; } operator bool() const { return m_status; } ~IsCopied() = default; private: IsCopied() : m_status(false) {} IsCopied(IsCopied const & ) = delete; IsCopied(IsCopied &&) = delete; IsCopied & operator=(IsCopied const & ) = delete; IsCopied & operator=(IsCopied &&) = delete; bool m_status; };

In the copy constructor of the class of interest is called, it will set the status to be true.

### Copy Elision in Action¶

In the testing program, we will check for the copy status:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 class Data { public: constexpr const static size_t NELEM = 1024*8; Data() { std::cout << "Data constructed @" << this << std::endl; } Data(Data const & other) { copy_from(other); std::cout << "Data copied to @" << this << " from @" << &other << std::endl; } ~Data() { std::cout << "Data destructed @" << this << std::endl; } void copy_from(Data const & other) { for (size_t it=0; it < NELEM; ++it) { m_buffer[it] = other.m_buffer[it]; } IsCopied::instance().on(); } private: // A lot of data that we don't want to reconstruct. int m_buffer[NELEM]; }; void manipulate_with_reference(Data & data, int value) { std::cout << "Manipulate with reference: " << &data << std::endl; for (size_t it=0; it < data.size(); ++it) { data[it] = value + it; } // In a real consumer function we will do much more meaningful operations. // However, we cannot destruct an object passed in with a reference. } Data worker1() { Data data; // Manipulate the Data object. manipulate_with_reference(data, 3); return data; } Data worker2() { Data data = worker1(); // Manipulate the Data object, again. manipulate_with_reference(data, 8); return data; } int main(int argc, char ** argv) { std::cout << (bool(IsCopied::instance()) ? "Something" : "Nothing") << " is copied" << std::endl; Data data = worker2(); std::cout << (bool(IsCopied::instance()) ? "Something" : "Nothing") << " is copied" << std::endl; }

While running it, we will see that the copy constructor is not called.

Execution Results

code/03_elision/01_copy.cpp

Build 01_copy.cpp
$g++ 01_copy.cpp -o 01_copy -std=c++17 -g -O3  Run 01_copy  1 2 3 4 5 6 7 $ ./01_copy Nothing is copied Data constructed @0x7ffee9ebe1c0 Manipulate with reference: 0x7ffee9ebe1c0 Manipulate with reference: 0x7ffee9ebe1c0 Nothing is copied Data destructed @0x7ffee9ebe1c0

## Move Semantics and Copy Elision¶

Move semantics greatly helps us to avoid copying expensive resources. To take advantage of that, our Data class should be changed to use dynamic allocation:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class Data { public: constexpr const static size_t NELEM = 1024*8; Data() { m_buffer = new int[NELEM]; std::cout << "Data constructed @" << this << std::endl; } Data(Data const & other) { m_buffer = new int[NELEM]; copy_from(other); std::cout << "Data copied to @" << this << " from @" << &other << std::endl; } Data & operator=(Data const & other) { if (nullptr == m_buffer) { m_buffer = new int[NELEM]; } copy_from(other); std::cout << "Data copy assigned to @" << this << " from @" << &other << std::endl; return *this; } Data(Data && other) { m_buffer = other.m_buffer; other.m_buffer = nullptr; std::cout << "Data moved to @" << this << " from @" << &other << std::endl; Status::instance().set_moved(); } Data & operator=(Data && other) { if (m_buffer) { delete[] m_buffer; } m_buffer = other.m_buffer; other.m_buffer = nullptr; std::cout << "Data move assigned to @" << this << " from @" << &other << std::endl; Status::instance().set_moved(); return *this; } ~Data() { if (m_buffer) { delete[] m_buffer; } std::cout << "Data destructed @" << this << std::endl; } }

### Forced Move Is a Bad Idea¶

Although the move semantics indeed avoids copy the expensive buffer in the Data class, it cannot avoid copy the Data object itself. However, copy elision (RVO & NRVO) can.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 Data worker1() { Data data; // Manipulate the Data object. manipulate_with_reference(data, 3); return data; } Data worker2() { Data data = worker1(); // Manipulate the Data object, again. manipulate_with_reference(data, 8); #ifdef FORCEMOVE // Explicit move semantics destroys copy elision. return std::move(data); #else return data; #endif } int main(int argc, char ** argv) { std::cout << "Status:" << (bool(Status::instance().is_copied()) ? " copied" : " uncopied") << (bool(Status::instance().is_moved()) ? " moved" : " unmoved") << std::endl; Data data = worker2(); std::cout << "Status:" << (bool(Status::instance().is_copied()) ? " copied" : " uncopied") << (bool(Status::instance().is_moved()) ? " moved" : " unmoved") << std::endl; }

### Compiler Does Copy Elision¶

Execution Results

code/03_elision/02_move.cpp

Build 02_move.cpp without optimization
$g++ 02_move.cpp -o 02_move -std=c++17 -g  Run 02_move  1 2 3 4 5 6 7 $ ./02_move Status: uncopied unmoved Data constructed @0x7ffee0ac61b8 Manipulate with reference: 0x7ffee0ac61b8 Manipulate with reference: 0x7ffee0ac61b8 Status: uncopied unmoved Data destructed @0x7ffee0ac61b8

### Forced Move Incurs More Operations¶

Execution Results

code/03_elision/02_move.cpp

Build 02_move.cpp without optimization
$g++ 02_move.cpp -o 02_move -std=c++17 -g -DFORCEMOVE  Run 02_move  1 2 3 4 5 6 7 8 9 $ ./02_move Status: uncopied unmoved Data constructed @0x7ffee90cb0d0 Manipulate with reference: 0x7ffee90cb0d0 Manipulate with reference: 0x7ffee90cb0d0 Data moved to @0x7ffee90cb168 from @0x7ffee90cb0d0 Data destructed @0x7ffee90cb0d0 Status: uncopied moved Data destructed @0x7ffee90cb168

## Data Concatenation¶

Because of copy elision, for readability it is prefer to write:

std::vector<int> worker_return();

than

void worker_argument(std::vector<int> & output /* output argument */);

Because in consumer code:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 // It reads clearly that the worker produces new result. std::vector result = worker_return(); // It takes a second to understand that the worker is using result as a buffer // for output. std::vector result; worker_argument(result); /* * The result is pre-populated before sending to the worker. From the * following lines we can't know how the worker will use result. * * By reading the worker signature we know that result may be used for output. * We can only be sure that result is used for output after reading the full * implemnetation of the worker. * * The worker may or may not expect the output argument to be pre-populated. * Regardless, it has to use runtime check to ensure either case. */ std::vector result(100); std::fill(result.begin(), result.end(), 7); worker_argument(result);

The ambiguity is a productivity killer. (Runtime performance is another story.)

### Style 1: Return vector¶

The first style returns a vector from inner and appends it in outer. It is easier to read and test. The inner worker:

  1 2 3 4 5 6 7 8 9 10 11 std::vector inner1(size_t start, size_t len) { std::cout << "** inner1 begins with " << start << std::endl; std::vector ret; for (size_t it=0; it < len; ++it) { Data data(start+it); ret.emplace_back(std::move(data)); } return ret; }

The outer worker:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void outer1(size_t len) { std::cout << "* outer1 begins" << std::endl; std::vector vec; for (size_t it=0; it < len; ++it) { std::cout << std::endl; std::cout << "* outer1 loop it=" << it << " begins" << std::endl; std::vector subvec = inner1(vec.size(), it+1); std::cout << "* outer1 obtained inner1 at " << vec.size() << std::endl; vec.insert( vec.end() , std::make_move_iterator(subvec.begin()) , std::make_move_iterator(subvec.end()) ); std::cout << "* outer1 inserted subvec.size()=" << subvec.size() << std::endl; } std::cout << "* outer1 result.size() = " << vec.size() << std::endl << std::endl; }

Execution Results

code/03_elision/03_accumulate.cpp

Build 03_accumulate.cpp with -DOTYPE=1
$g++ 03_accumulate.cpp -o 03_accumulate -std=c++17 -g -O3 -DOTYPE=1  Run 03_accumulate   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 $ ./03_accumulate * outer1 begins * outer1 loop it=0 begins ** inner1 begins with 0 Data #0 constructed @0x7ffee4a620c8 Data #0 moved to @0x7fe29d405ab0 from @0x7ffee4a620c8 Data #0 destructed @0x7ffee4a620c8 * outer1 obtained inner1 at 0 Data #0 moved to @0x7fe29d405ac0 from @0x7fe29d405ab0 * outer1 inserted subvec.size()=1 Data #0 destructed @0x7fe29d405ab0 * outer1 loop it=1 begins ** inner1 begins with 1 Data #1 constructed @0x7ffee4a620c8 Data #1 moved to @0x7fe29d405ab0 from @0x7ffee4a620c8 Data #1 destructed @0x7ffee4a620c8 Data #2 constructed @0x7ffee4a620c8 Data #2 moved to @0x7fe29d405ae0 from @0x7ffee4a620c8 Data #1 copied to @0x7fe29d405ad0 from @0x7fe29d405ab0 Data #1 destructed @0x7fe29d405ab0 Data #2 destructed @0x7ffee4a620c8 * outer1 obtained inner1 at 1 Data #1 moved to @0x7fe29d405b00 from @0x7fe29d405ad0 Data #2 moved to @0x7fe29d405b10 from @0x7fe29d405ae0 Data #0 copied to @0x7fe29d405af0 from @0x7fe29d405ac0 Data #0 destructed @0x7fe29d405ac0 * outer1 inserted subvec.size()=2 Data #2 destructed @0x7fe29d405ae0 Data #1 destructed @0x7fe29d405ad0 * outer1 loop it=2 begins ** inner1 begins with 3 Data #3 constructed @0x7ffee4a620c8 Data #3 moved to @0x7fe29d504080 from @0x7ffee4a620c8 Data #3 destructed @0x7ffee4a620c8 Data #4 constructed @0x7ffee4a620c8 Data #4 moved to @0x7fe29d5040a0 from @0x7ffee4a620c8 Data #3 copied to @0x7fe29d504090 from @0x7fe29d504080 Data #3 destructed @0x7fe29d504080 Data #4 destructed @0x7ffee4a620c8 Data #5 constructed @0x7ffee4a620c8 Data #5 moved to @0x7fe29d5040d0 from @0x7ffee4a620c8 Data #4 copied to @0x7fe29d5040c0 from @0x7fe29d5040a0 Data #3 copied to @0x7fe29d5040b0 from @0x7fe29d504090 Data #4 destructed @0x7fe29d5040a0 Data #3 destructed @0x7fe29d504090 Data #5 destructed @0x7ffee4a620c8 * outer1 obtained inner1 at 3 Data #3 moved to @0x7fe29d504120 from @0x7fe29d5040b0 Data #4 moved to @0x7fe29d504130 from @0x7fe29d5040c0 Data #5 moved to @0x7fe29d504140 from @0x7fe29d5040d0 Data #2 copied to @0x7fe29d504110 from @0x7fe29d405b10 Data #1 copied to @0x7fe29d504100 from @0x7fe29d405b00 Data #0 copied to @0x7fe29d5040f0 from @0x7fe29d405af0 Data #2 destructed @0x7fe29d405b10 Data #1 destructed @0x7fe29d405b00 Data #0 destructed @0x7fe29d405af0 * outer1 inserted subvec.size()=3 Data #5 destructed @0x7fe29d5040d0 Data #4 destructed @0x7fe29d5040c0 Data #3 destructed @0x7fe29d5040b0 * outer1 result.size() = 6 Data #5 destructed @0x7fe29d504140 Data #4 destructed @0x7fe29d504130 Data #3 destructed @0x7fe29d504120 Data #2 destructed @0x7fe29d504110 Data #1 destructed @0x7fe29d504100 Data #0 destructed @0x7fe29d5040f0

The unwanted copies come from std::vector resizing. To mitigate it, we should mark the move constructor with noexcept:

Data(Data && other) noexcept
{
m_serial = other.m_serial;
m_buffer = other.m_buffer;
other.m_buffer = nullptr;
std::cout << "Data #" << m_serial << " moved to @" << this << " from @" << &other << std::endl;
}

Execution Results

code/03_elision/03_accumulate.cpp

Build 03_accumulate.cpp with -DMOVENOEXCEPT -DOTYPE=1
$g++ 03_accumulate.cpp -o 03_accumulate -std=c++17 -g -O3 -DMOVENOEXCEPT -DOTYPE=1  Run 03_accumulate   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 $ ./03_accumulate * outer1 begins * outer1 loop it=0 begins ** inner1 begins with 0 Data #0 constructed @0x7ffee11510a8 Data #0 moved to @0x7fcf16405ab0 from @0x7ffee11510a8 Data #0 destructed @0x7ffee11510a8 * outer1 obtained inner1 at 0 Data #0 moved to @0x7fcf16405ac0 from @0x7fcf16405ab0 * outer1 inserted subvec.size()=1 Data #0 destructed @0x7fcf16405ab0 * outer1 loop it=1 begins ** inner1 begins with 1 Data #1 constructed @0x7ffee11510a8 Data #1 moved to @0x7fcf16405ab0 from @0x7ffee11510a8 Data #1 destructed @0x7ffee11510a8 Data #2 constructed @0x7ffee11510a8 Data #2 moved to @0x7fcf16405ae0 from @0x7ffee11510a8 Data #1 moved to @0x7fcf16405ad0 from @0x7fcf16405ab0 Data #1 destructed @0x7fcf16405ab0 Data #2 destructed @0x7ffee11510a8 * outer1 obtained inner1 at 1 Data #1 moved to @0x7fcf16405b00 from @0x7fcf16405ad0 Data #2 moved to @0x7fcf16405b10 from @0x7fcf16405ae0 Data #0 moved to @0x7fcf16405af0 from @0x7fcf16405ac0 Data #0 destructed @0x7fcf16405ac0 * outer1 inserted subvec.size()=2 Data #2 destructed @0x7fcf16405ae0 Data #1 destructed @0x7fcf16405ad0 * outer1 loop it=2 begins ** inner1 begins with 3 Data #3 constructed @0x7ffee11510a8 Data #3 moved to @0x7fcf16504080 from @0x7ffee11510a8 Data #3 destructed @0x7ffee11510a8 Data #4 constructed @0x7ffee11510a8 Data #4 moved to @0x7fcf165040a0 from @0x7ffee11510a8 Data #3 moved to @0x7fcf16504090 from @0x7fcf16504080 Data #3 destructed @0x7fcf16504080 Data #4 destructed @0x7ffee11510a8 Data #5 constructed @0x7ffee11510a8 Data #5 moved to @0x7fcf165040d0 from @0x7ffee11510a8 Data #4 moved to @0x7fcf165040c0 from @0x7fcf165040a0 Data #3 moved to @0x7fcf165040b0 from @0x7fcf16504090 Data #4 destructed @0x7fcf165040a0 Data #3 destructed @0x7fcf16504090 Data #5 destructed @0x7ffee11510a8 * outer1 obtained inner1 at 3 Data #3 moved to @0x7fcf16504120 from @0x7fcf165040b0 Data #4 moved to @0x7fcf16504130 from @0x7fcf165040c0 Data #5 moved to @0x7fcf16504140 from @0x7fcf165040d0 Data #2 moved to @0x7fcf16504110 from @0x7fcf16405b10 Data #1 moved to @0x7fcf16504100 from @0x7fcf16405b00 Data #0 moved to @0x7fcf165040f0 from @0x7fcf16405af0 Data #2 destructed @0x7fcf16405b10 Data #1 destructed @0x7fcf16405b00 Data #0 destructed @0x7fcf16405af0 * outer1 inserted subvec.size()=3 Data #5 destructed @0x7fcf165040d0 Data #4 destructed @0x7fcf165040c0 Data #3 destructed @0x7fcf165040b0 * outer1 result.size() = 6 Data #5 destructed @0x7fcf16504140 Data #4 destructed @0x7fcf16504130 Data #3 destructed @0x7fcf16504120 Data #2 destructed @0x7fcf16504110 Data #1 destructed @0x7fcf16504100 Data #0 destructed @0x7fcf165040f0

### Style 2: Use Output vector¶

The second style uses an output argument which is passed from outer to inner. The inner worker:

 1 2 3 4 5 6 7 8 9 void inner2(size_t start, size_t len, std::vector & result /* for output */) { std::cout << "** inner2 begins with " << start << std::endl; for (size_t it=0; it < len; ++it) { Data data(start+it); result.emplace_back(std::move(data)); } }

The outer worker:

  1 2 3 4 5 6 7 8 9 10 11 12 void outer2(size_t len) { std::cout << "* outer2 begins" << std::endl; std::vector vec; for (size_t it=0; it < len; ++it) { std::cout << std::endl; std::cout << "* outer2 loop it=" << it << " begins" << std::endl; inner2(vec.size(), it+1, vec); } std::cout << "* outer2 result.size() = " << vec.size() << std::endl << std::endl; }

There is no longer the intermediate vector and it saves quite a number of movement. The prize we pay is less testability.

Execution Results

code/03_elision/03_accumulate.cpp

Build 03_accumulate.cpp with -DMOVENOEXCEPT -DOTYPE=2
$g++ 03_accumulate.cpp -o 03_accumulate -std=c++17 -g -O3 -DMOVENOEXCEPT -DOTYPE=2  Run 03_accumulate   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 $ ./03_accumulate * outer2 begins * outer2 loop it=0 begins ** inner2 begins with 0 Data #0 constructed @0x7ffee68c60c8 Data #0 moved to @0x7f898c405ab0 from @0x7ffee68c60c8 Data #0 destructed @0x7ffee68c60c8 * outer2 loop it=1 begins ** inner2 begins with 1 Data #1 constructed @0x7ffee68c60c8 Data #1 moved to @0x7f898c405ad0 from @0x7ffee68c60c8 Data #0 moved to @0x7f898c405ac0 from @0x7f898c405ab0 Data #0 destructed @0x7f898c405ab0 Data #1 destructed @0x7ffee68c60c8 Data #2 constructed @0x7ffee68c60c8 Data #2 moved to @0x7f898c405b00 from @0x7ffee68c60c8 Data #1 moved to @0x7f898c405af0 from @0x7f898c405ad0 Data #0 moved to @0x7f898c405ae0 from @0x7f898c405ac0 Data #1 destructed @0x7f898c405ad0 Data #0 destructed @0x7f898c405ac0 Data #2 destructed @0x7ffee68c60c8 * outer2 loop it=2 begins ** inner2 begins with 3 Data #3 constructed @0x7ffee68c60c8 Data #3 moved to @0x7f898c405b10 from @0x7ffee68c60c8 Data #3 destructed @0x7ffee68c60c8 Data #4 constructed @0x7ffee68c60c8 Data #4 moved to @0x7f898c405b60 from @0x7ffee68c60c8 Data #3 moved to @0x7f898c405b50 from @0x7f898c405b10 Data #2 moved to @0x7f898c405b40 from @0x7f898c405b00 Data #1 moved to @0x7f898c405b30 from @0x7f898c405af0 Data #0 moved to @0x7f898c405b20 from @0x7f898c405ae0 Data #3 destructed @0x7f898c405b10 Data #2 destructed @0x7f898c405b00 Data #1 destructed @0x7f898c405af0 Data #0 destructed @0x7f898c405ae0 Data #4 destructed @0x7ffee68c60c8 Data #5 constructed @0x7ffee68c60c8 Data #5 moved to @0x7f898c405b70 from @0x7ffee68c60c8 Data #5 destructed @0x7ffee68c60c8 * outer2 result.size() = 6 Data #5 destructed @0x7f898c405b70 Data #4 destructed @0x7f898c405b60 Data #3 destructed @0x7f898c405b50 Data #2 destructed @0x7f898c405b40 Data #1 destructed @0x7f898c405b30 Data #0 destructed @0x7f898c405b20

### Style 3: Use a Class for Both Return and Output Argument¶

The third style uses a class so that it support both vector returning and output argument for the vector. The class is:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 struct Accumulator { public: // This can be called if consumers want the sub-operation one by one, and // make the code more testable. But it isn't really used in the example. std::vector inner1(size_t start, size_t len) { std::cout << "** Accumulator::inner1 begins with " << start << std::endl; std::vector ret; ret.reserve(len); inner2(start, len, ret); return ret; } private: void inner2(size_t start, size_t len, std::vector & ret) { std::cout << "** Accumulator::inner2 begins with " << start << std::endl; for (size_t it=0; it < len; ++it) { Data data(start+it); ret.emplace_back(std::move(data)); } } public: // This is used when batch operation is in demand. void outer(size_t len) { std::cout << "* Accumulator::outer begins" << std::endl; result.reserve(len*(len+1)/2); for (size_t it=0; it < len; ++it) { std::cout << std::endl; std::cout << "* Accumulator::outer loop it=" << it << " begins" << std::endl; inner2(result.size(), it+1, result); } std::cout << "* Accumulator::outer result.size() = " << result.size() << std::endl << std::endl; } public: std::vector result; }; /* end struct Accumulator */

Although Accumulator::outer still calls the function Accumulator::inner2 that takes an output argument, we also have the function Accumulator::inner1 that wraps around Accumulator::inner2 and make it testable.

To further reduce unwanted movements, we pre-calculate the number of elements to be populated in the vector and reserve the space.

Execution Results

code/03_elision/03_accumulate.cpp

Build 03_accumulate.cpp with -DMOVENOEXCEPT -DOTYPE=3
$g++ 03_accumulate.cpp -o 03_accumulate -std=c++17 -g -O3 -DMOVENOEXCEPT -DOTYPE=3  Run 03_accumulate   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 $ ./03_accumulate * Accumulator::outer begins * Accumulator::outer loop it=0 begins ** Accumulator::inner2 begins with 0 Data #0 constructed @0x7ffee47640a8 Data #0 moved to @0x7fdb66c05ab0 from @0x7ffee47640a8 Data #0 destructed @0x7ffee47640a8 * Accumulator::outer loop it=1 begins ** Accumulator::inner2 begins with 1 Data #1 constructed @0x7ffee47640a8 Data #1 moved to @0x7fdb66c05ac0 from @0x7ffee47640a8 Data #1 destructed @0x7ffee47640a8 Data #2 constructed @0x7ffee47640a8 Data #2 moved to @0x7fdb66c05ad0 from @0x7ffee47640a8 Data #2 destructed @0x7ffee47640a8 * Accumulator::outer loop it=2 begins ** Accumulator::inner2 begins with 3 Data #3 constructed @0x7ffee47640a8 Data #3 moved to @0x7fdb66c05ae0 from @0x7ffee47640a8 Data #3 destructed @0x7ffee47640a8 Data #4 constructed @0x7ffee47640a8 Data #4 moved to @0x7fdb66c05af0 from @0x7ffee47640a8 Data #4 destructed @0x7ffee47640a8 Data #5 constructed @0x7ffee47640a8 Data #5 moved to @0x7fdb66c05b00 from @0x7ffee47640a8 Data #5 destructed @0x7ffee47640a8 * Accumulator::outer result.size() = 6 Data #5 destructed @0x7fdb66c05b00 Data #4 destructed @0x7fdb66c05af0 Data #3 destructed @0x7fdb66c05ae0 Data #2 destructed @0x7fdb66c05ad0 Data #1 destructed @0x7fdb66c05ac0 Data #0 destructed @0x7fdb66c05ab0

Evolution of the three styles demonstrate how one may develop sophisticated code from a standalone helper to an optimized class library.

Variadic template allows us to capture any number of template arguments in a function template. Assuming we have 2 constructors for Data:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Data(size_t serial, ctor_passkey const &) : m_serial(serial) { m_buffer = new int[NELEM]; initialize(0); std::cout << "Data #" << m_serial << " constructed @" << this << "(serial=" << m_serial << ")" << std::endl; } Data(size_t serial, int base, ctor_passkey const &) : m_serial(serial+base) { m_buffer = new int[NELEM]; initialize(0); std::cout << "Data #" << m_serial << " constructed @" << this << "(serial=" << m_serial << ")" << "(base=" << base << ")" << std::endl; }

We will need two factories methods for them:

 1 2 3 4 5 6 7 8 9 static std::shared_ptr create(size_t serial) { return std::make_shared(serial, ctor_passkey()); } static std::shared_ptr create(size_t serial, int base) { return std::make_shared(serial, int, ctor_passkey()); }

It’s tedious to add the corresponding factory functions, although it is not too much an issue, since the compiler will complain. Let’s assume we forgot the add the second factory overload and see what may happen.

Execution Results

code/04_template/01_factory.cpp

Build 01_factory.cpp and show the missing factory method
$g++ 01_factory.cpp -o 01_factory -std=c++17 -g -O3 -DUSE_CREATE 01_factory.cpp:142:37: error: too many arguments to function call, expected single argument 'serial', have 2 arguments data = Data::create(it, base); ~~~~~~~~~~~~ ^~~~ 01_factory.cpp:22:5: note: 'create' declared here static std::shared_ptr<Data> create(size_t serial) ^ 1 error generated.  Variadic template can conveniently help us summarize the two overloads into one template function, and also capture every new public constructor that will be added in the future.  1 2 3 4 5 6 template < typename ... Args > static std::shared_ptr make(Args && ... args) { // Forget about the 'forward' for now. It will be discussed later. return std::make_shared(std::forward(args) ..., ctor_passkey()); }  Run the following code:   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 void outer1(size_t len) { std::cout << "* outer1 begins" << std::endl; std::vector> vec; for (size_t it=0; it < len; ++it) { std::cout << std::endl; std::cout << "* outer1 loop it=" << it << " begins" << std::endl; std::vector> subvec = inner1(vec.size(), it+1); std::cout << "* outer1 obtained inner1 at " << vec.size() << std::endl; vec.insert( vec.end() , std::make_move_iterator(subvec.begin()) , std::make_move_iterator(subvec.end()) ); std::cout << "* outer1 inserted subvec.size()=" << subvec.size() << std::endl; } std::cout << "* outer1 result.size() = " << vec.size() << std::endl << std::endl; std::cout << "* outer1 end" << std::endl << std::endl; } std::vector> inner1(size_t base, size_t len) { std::cout << "** inner1 begins with " << base << std::endl; std::vector> ret; for (size_t it=0; it < len; ++it) { std::shared_ptr data; if (0 == base) { data = Data::make(it); } else { data = Data::make(it, base); } ret.emplace_back(data); } return ret; }  Execution Results code/04_template/01_factory.cpp Build 01_factory.cpp $ g++ 01_factory.cpp -o 01_factory -std=c++17 -g -O3

Run 01_factory
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 $./01_factory * outer1 begins * outer1 loop it=0 begins ** inner1 begins with 0 Data #0 constructed @0x7ff4af405ac8(serial=0) * outer1 obtained inner1 at 0 * outer1 inserted subvec.size()=1 * outer1 loop it=1 begins ** inner1 begins with 1 Data #1 constructed @0x7ff4af405b28(serial=1)(base=1) Data #2 constructed @0x7ff4af405b68(serial=2)(base=1) * outer1 obtained inner1 at 1 * outer1 inserted subvec.size()=2 * outer1 loop it=2 begins ** inner1 begins with 3 Data #3 constructed @0x7ff4af405bf8(serial=3)(base=3) Data #4 constructed @0x7ff4af405c38(serial=4)(base=3) Data #5 constructed @0x7ff4af405c78(serial=5)(base=3) * outer1 obtained inner1 at 3 * outer1 inserted subvec.size()=3 * outer1 result.size() = 6 * outer1 end Data #5 destructed @0x7ff4af405c78 Data #4 destructed @0x7ff4af405c38 Data #3 destructed @0x7ff4af405bf8 Data #2 destructed @0x7ff4af405b68 Data #1 destructed @0x7ff4af405b28 Data #0 destructed @0x7ff4af405ac8  ## Perfect Forwarding¶ In the previous section we used std::forward, which enables perfect forwarding:  1 2 3 4 5 template < typename ... Args > static std::shared_ptr make(Args && ... args) { return std::make_shared(std::forward(args) ..., ctor_passkey()); }  The template forwards the reference. Like std::move, it serves as a cast to rvalue reference. The difference is that: 1. std::move unconditionally casts the input to rvalue reference. 2. std::forward casts to rvalue reference only when it can. When we write Data &&, it is a rvalue reference. With T && as a template argument, when we write T &&, it can be either lvalue or rvalue, and is called universal reference. The rule of thumb is that when T is a deductible type (auto && falls into this category too), T && is a universal reference rather a strict rvalue reference. So std::forward<Args>(args) preserves the type of reference of the arguments, and the pattern is called perfect forwarding. Because the arguments of Data constructors were both fundamental types, it doesn’t matter whether or not we use perfect forwarding. To demonstrate how it works, we add the two wrapper:  1 2 3 // Proxy to copy and move constructor. Data(Data const & other, ctor_passkey const &) : Data(std::forward(other)) {} Data(Data && other, ctor_passkey const &) : Data(std::forward(other)) {}  And we use a slightly different outer:   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 void outer1(size_t len) { std::cout << "* outer1 begins" << std::endl; std::vector> vec; for (size_t it=0; it < len; ++it) { std::cout << std::endl; std::cout << "* outer1 loop it=" << it << " begins" << std::endl; std::vector> subvec = inner1(vec.size(), it+1); std::cout << "* outer1 obtained inner1 at " << vec.size() << std::endl; vec.insert( vec.end() , std::make_move_iterator(subvec.begin()) , std::make_move_iterator(subvec.end()) ); std::cout << "* outer1 inserted subvec.size()=" << subvec.size() << std::endl; } std::cout << "* outer1 result.size() = " << vec.size() << std::endl << std::endl; // Exercise the perfect forwarding. vec.emplace_back(Data::make(*vec[0])); vec.emplace_back(Data::make(std::move(*vec[1]))); std::cout << "* outer1 end" << std::endl << std::endl; }  Execution Results code/04_template/01_factory.cpp Build 01_factory.cpp and show perfect forwarding $ g++ 01_factory.cpp -o 01_factory -std=c++17 -g -O3 -DSHOW_PERFECT_FORWARD

Run 01_factory
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 $./01_factory * outer1 begins * outer1 loop it=0 begins ** inner1 begins with 0 Data #0 constructed @0x7ff6abc05ac8(serial=0) * outer1 obtained inner1 at 0 * outer1 inserted subvec.size()=1 * outer1 loop it=1 begins ** inner1 begins with 1 Data #1 constructed @0x7ff6abc05b28(serial=1)(base=1) Data #2 constructed @0x7ff6abc05b68(serial=2)(base=1) * outer1 obtained inner1 at 1 * outer1 inserted subvec.size()=2 * outer1 loop it=2 begins ** inner1 begins with 3 Data #3 constructed @0x7ff6abc05bf8(serial=3)(base=3) Data #4 constructed @0x7ff6abc05c38(serial=4)(base=3) Data #5 constructed @0x7ff6abc05c78(serial=5)(base=3) * outer1 obtained inner1 at 3 * outer1 inserted subvec.size()=3 * outer1 result.size() = 6 Data #0 copied to @0x7ff6abc05cb8 from @0x7ff6abc05ac8 Data #1 moved to @0x7ff6abc05ba8 from @0x7ff6abc05b28 * outer1 end Data #1 destructed @0x7ff6abc05ba8 Data #0 destructed @0x7ff6abc05cb8 Data #5 destructed @0x7ff6abc05c78 Data #4 destructed @0x7ff6abc05c38 Data #3 destructed @0x7ff6abc05bf8 Data #2 destructed @0x7ff6abc05b68 Data #1 destructed @0x7ff6abc05b28 Data #0 destructed @0x7ff6abc05ac8  ## Lambda Expression¶ C++ lambda expression enables a shorthand for anonymous function. The syntax (no variable is captured) is: [] (/* arguments */) { /* body */ }  It works basically like a functor.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct Functor { bool operator()(int v) { return 0 == v % 23; } }; /* end struct Functor */ int main(int argc, char ** argv) { std::vector data(63712); for (size_t i=0 ; i Execution Results code/05_lambda/01_lambda.cpp Build 01_lambda.cpp and show perfect forwarding $ g++ 01_lambda.cpp -o 01_lambda -std=c++17 -g -O3

Run 01_lambda
 1 2 3 $./01_lambda Number divisible by 23 (count by functor): 2771 Number divisible by 23 (count by lambda): 2771  ### Keep a Lambda in a Local Variable¶ Lambda is considered as anonymous function, but we can give it a “name” by assigning it to a variable. There are two choices: auto or std::function.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 int main(int argc, char ** argv) { std::vector data(63712); for (size_t i=0 ; i condition_function = [](int v){ return 0 == v%23; }; std::cout << "Number divisible by 23 (count by lambda in std::function): " << std::count_if(data.begin(), data.end(), condition_function) << std::endl; return 0; }  Execution Results code/05_lambda/02_stored.cpp Build 02_stored.cpp $ g++ 02_stored.cpp -o 02_stored -std=c++17 -g -O3

Run 02_stored
 1 2 3 4 $./02_stored Number divisible by 23 (count by lambda inline): 2771 Number divisible by 23 (count by lambda in auto): 2771 Number divisible by 23 (count by lambda in std::function): 2771  ### Difference between auto and std::function¶ Although both auto and std::function can hold a lambda, the two ways are not exactly the same. A lambda works like a functor and the auto type reflects that. A std::function is more versatile than it, and takes more memory as well. This is a list of targets (callables) that a std::function can hold: free functions, member functions, functors, lambda expressions, and bind expressions.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 std::cout << std::endl << "The differences between lambda and std::function" << std::endl; std::cout << "type name of lambda: " << typeid(condition).name() << std::endl; std::cout << "type name of std::function: " << typeid(condition_function).name() << std::endl; std::cout << "size of lambda: " << sizeof(condition) << std::endl; std::cout << "size of std::function: " << sizeof(condition_function) << std::endl;  Execution Results code/05_lambda/02_stored.cpp Build 02_stored.cpp and show the difference in types $ g++ 02_stored.cpp -o 02_stored -std=c++17 -g -O3 -DSHOW_DIFF

Run 02_stored
  1 2 3 4 5 6 7 8 9 10 $./02_stored Number divisible by 23 (count by lambda inline): 2771 Number divisible by 23 (count by lambda in auto): 2771 Number divisible by 23 (count by lambda in std::function): 2771 The differences between lambda and std::function type name of lambda: Z4mainE3$_1 type name of std::function: NSt3__18functionIFbiEEE size of lambda: 1 size of std::function: 48

## Closure¶

So far our use of lambda expressions doesn’t capture any local variables. When it does, we call the lambda expression a closure.

We must tell the compiler what type of capture the lambda expression would like to use. Otherwise the compilation fails.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int main(int argc, char ** argv) { std::vector data(63712); for (size_t i=0 ; i

Execution Results

code/05_lambda/03_closure.cpp

Show compiler error of wrong capture in 03_closure.cpp
$g++ 03_closure.cpp -o 03_closure -std=c++17 -g -O3 -DWRONG_CAPTURE 03_closure.cpp:16:77: error: variable 'divisor' cannot be implicitly captured in a lambda with no capture-default specified << std::count_if(data.begin(), data.end(), [](int v){ return 0 == v%divisor; }) ^ 03_closure.cpp:11:9: note: 'divisor' declared here int divisor = 23; ^ 03_closure.cpp:16:52: note: lambda expression begins here << std::count_if(data.begin(), data.end(), [](int v){ return 0 == v%divisor; }) ^ 1 error generated.  We may explicitly tell the compiler that we want divisor to be captured by the lambda expression by value: int divisor = 23; std::cout << "Count (lambda explicitly capture by value): " << std::count_if(data.begin(), data.end(), [divisor](int v){ return 0 == v%divisor; }) << " (divisor: " << divisor << ")" << std::endl;  Use = to implicitly capture by value: std::cout << "Count (lambda implicitly capture by value): " << std::count_if(data.begin(), data.end(), [=](int v){ return 0 == v%divisor; }) << " (divisor: " << divisor << ")" << std::endl;  Use & to capture by reference:  1 2 3 4 5 std::cout << "Count (lambda explicitly capture by reference): " << std::count_if(data.begin(), data.end(), [&divisor](int v){ divisor = 10; return 0 == v%divisor; }) << " (divisor: " << divisor << ")" << std::endl;  & can also be put standalone in [] to indicate that the default capture is by reference. The execution results: Execution Results code/05_lambda/03_closure.cpp Build 03_closure.cpp $ g++ 03_closure.cpp -o 03_closure -std=c++17 -g -O3

Run 03_closure
 1 2 3 4 \$ ./03_closure Count (lambda explicitly capture by value): 2771 (divisor: 23) Count (lambda implicitly capture by value): 2771 (divisor: 23) Count (lambda explicitly capture by reference): 6372 (divisor: 10)

The lambda expression and closure allow functional style of programming. As shown in the std::count_if example, it is a convenient tool to reduce the lines of code. It generally makes the code looks cleaner and easier to maintain. That buys us time to do more important things or optimize performance hotspot.

But there are times that we cannot entrust the optimization to the compiler. Lambda expressions are not the easiest place to add intrinsics or assemblies.

When working on a container object equipped with proper iterator interface, I go with the functional style. The lambda expression may help avoid expensive intermediate buffers. It works well at least for the initial prototype.

## Exercises¶

1. Measure the performance between using an output vector and returning a new vector.

## References¶

 [1] Copy elision at cppreference.com .
 [2] Lambda expressions at cppreference.com .