
We ([Moz.com](https://Moz.com)) have been doing a lot of interviews for new engineers lately. I have been asked to help out trying to find the great new team members from the hordes of applicants (luckily we have a great team pre-screening applicants before they get to engineers (thanks you guys).

One of the things the most non-programmers are surprised about is the severity of programming interviews.

An on-site interview (after you have passed all the phone screens) consists of seeing between six and eight people (depending on company); this is going to take a full day and you will be utterly exhausted by the end.
But why are "Software Engineer" interviews so exhaustive? [I think this sums it up](https://programmers.stackexchange.com/questions/47778/why-are-sw-engineering-interviews-disproportionately-difficult-vs-research-inte/47784#47784)

### What types of interview do I do?
My field of expertise is technical (not the "[touchy feely](https://blog.sironaconsulting.com/sironasays/2011/03/is-your-hr-manager-more-miss-marple-or-hr-20-fun-infographic.html)" HR stuff or ["can you work as a team"](https://imgur.com/gallery/4D6wd) management stuff). As a result I basically stick to one type of interview with two sub variations:

* Can you think on your feet
 * Do you know the basics (algorithms/data structures/Big O/CS theory)
 * Design an interacting systems at a high level thinking about the interaction

I have not done phone screens in a while (this is a different skill set). I have no problem with doing them I just think other people are better than me at this kind of interview. Personally I think it is really hard to get technical information over the phone (even if you use one of those collaborative online writing tools) I would rather render my ~~judgement~~ opinion on the candidate based on talking to them face to face.

### So how do you get good information from a candidate?
Heck if I know. During the interview it is a lot of gut feeling and pressing the candidate to expresses themselves and provide feedback on what they are thinking. **Please**; <span style={{color: 0x993366}}>if you are a candidate explain what you are doing*</span>, I want to know how you got the solution more than I want to know the solution you provided.

 When asking a candidate about the basics, their inability to answer the question does not really tell me much (you may just not have used that technique in a while or missed that one class at college) so don't worry too much I will find something you can answer; but note, your ability to answer the question only tells me a little more (not much).

So when you do answer I want to know **why** you are using a particular technique, are there **any other techniques** and if so **why** use your initial choice over another ('it would take too much wide board space' is a great answer as it means you understand the alternative is very complex (but now I am going to ask you to do it :-) ))

Unless the company is looking for a skill in a particular language then generally my interview question are language agnostic and I will let the candidate use the language that they are most comfortable with on a white board. Though the language is not important to me, **<em style={{ textAlign: 'justify' }}>the usage of the language is important</em>** (you better not leak memory in C/C++, you better not build strings with java.lang.string in Java, you better know how to use regular expression matching in Perl, you should understand how to use the fundamental list/dictionary types in python etc.) and most importantly **you better be able to use fluently any language you list on your resume** (if you are just learning/fiddling with a language make that clear).

Notice I have not said anything about syntax. Personally I think this is irrelevant in an interview situation. I mean I get code wrong all the time when I write it (that's why I have the compiler as my first line of defense and unit tests as the second). As long as I can see what you are logically trying to achieve I will not complain about missing semi-colon.

### The dos and don'ts for a candidate
This article has a [basic guide on general etiquette](https://jobs.aol.com/articles/2011/09/12/tips-for-interviews-interviewing-etiquette-infographic/) for interviews. While this one has some more specific guidance on what to expect at [programming interview](https://programmers.stackexchange.com/questions/80065/preparing-for-interviews/80073#80073).

Both mention to study the company; when I was younger I always though this was silly (I was naive once a long time ago) as I did not think it would help me do my job, but I accepted the advice of my elders and did study the companies before interviews and I must say it always paid off (but never in ways you expect).

Remember that I only have an hour to try and extract as much information as I can from you so don't go off on wild tangents stick to the point and answer the question I ask. If you can show off quickly then do so but make it quick. You should also note that interviewers generally have their questions arranged in themes, if you can answer the questions quickly he is going to move onto the next part of the same question which extends the question making it harder trying to draw more knowledge from you (can you make that more efficient/ can you see the common pit falls how do you avoid them etc..).

On the same line don't give the most optimal solution first (unless that is obviously what the interviewer is looking for and you can justify it), a good interviewer is going to walk you up to the optimal solution and see if you know why its the optimal solution (But its also part of the communication I mentioned above, if you explain what you are doing (I will start with a brute force solution) even a bad interviewer should know you have an alternative optimizes solution).

Don't gloss over the complex bit (unless the interviewer tells you too), this is probably the bit they want you to explain, whatever you don't try BS your answer. The interviewer has probably asked the question a hundred times before he has heard all the good/standard ways of solving the problem (and some more exotic ways), if you don't know just let the interviewer know.

### The don'ts for a interviewer
I hate interviewers that ask those silly logic problems. They do not tell you anything about a candidates ability to write code or think critically about coding. All it tells you is that they are good a logic problems.

* Why is a man hole cover round?
* If a man rows a boat at 4 mph downstream on a river traveling 2 mph. He drops his hat overboard but does not notice for an hour. How long does he need to row upstream to meet his hat?
* Russian roulette: I have a six shooter with 2 bullets in consecutive location. I spin the chamber then shoot myself first (it does not go off). I pass the gun to you. Do you spin the chamber before shooting or not?
* You have 1000 bottles of champagne. One bottle is contaminated and drinking from it will cause vomiting in an hour. You have an hour and ten staff to help you. What is the fewest bottles you need to discard to guarantee none of your guests gets poisoned?
* Many more.

Personally I like the problems and do well at interviews that ask them. But I don't think it tells you anything about me as a software engineer. As a result I don't ask these types of question.

Other people argue that it shows people that can think critically about problems. Sorry I disagree. It tends to find people that have heard the problem before and these problems turn up on websites all the time.

### The coding interview
I previously did a second type. Sit the interviewee in front of a laptop and ask them to write code to solve a particular problem. This would involve: user input (from keyboard or file (as user input was involved I would look for error checking, but since a file was involved no error recovery)). I would provide documentation to an existing library to see if they could read and understand it enough to use it. *But this is blog entry for another time. But if you have some hints and comments about please post a comment below*.


One of the things the most non-programmers are surprised about is the severity of programming interviews. So why are they so intense?

Interviews Processes

This is the first article in the series
OK. Lets do this.

I keep trying to think about something big and interesting to write about. But that is just not working. All my time is spent trying to think of the blockbuster idea; which just gets in the way of actually writing. So lets start with the small things. If I can get into the habit of writing something a couple of times a week. Then maybe we can work up to interesting stuff.

Step one; write about something I know. C++; we now start the "So you want to learn C++" series of posts.

I am going to assume two things.

* You know how to use the compiler
* That you have some basic programming experience C/Java/C#/Perl/PHP (nearly anything)
So you understand the basics of program but are unfamiliar with C++

First thing everybody needs is to get something working; here is the classic "Hello World" in C++

helloworld.cpp
```c
#include <iostream>

int main()
{
    std::cout << "Hello World\n";
}
```

The next step is to accepts user input and generates a response based on that input. Lets move on to the not quite as classic "Hi There Bob" :-)

hitherebob.cpp
```c
#include <iostream>
#include <string>

int main()
{
    std::cout << "Hi there what's your name?\n";

    std::string  line;
    std::getline(std::cin, line);

    std::cout << "It was good to meet you " << line << "\n";
}
```

The above code is relatively simple and only a few things to note:

* `#include <iostream>`
Imports the standard input and output facilities so you can print messages to the user and read user input.
    + `std::cin`
Is the standard input stream. From this you can read user input.
    + `std::cout`
Is the standard output stream. You can print text to the user console.
* `#include <string>`
Imports the standard string handling function. Most importantly it imports the type `std::string`.
    + `std::string`
This is one of the standard types and holds strings (a list of characters). We will go over types (and variables) in a lot more details in subsequent articles. But for just accept that `line` is a variable (of type std::string) used to hold a line of user input.
    + `std::getline()`
This is a function that reads a line of text from a `std::istream` into a `std::string`. In this case we use `std::cin` as the input stream (it is a specialization of a std::istream and can thus be used as the input). Thus we read `a line` of input from the user.



There are a lot of other concepts encapsulated above that I don't want to get into quite yet. But don't worry I will cover them all.


C++ for beginners. Part 1 Hello World. I keep trying to think about something big and interesting to write about. But that is just not working. All my time is spent trying to think of the blockbuster idea; which just gets in the way of actually writing. So lets start with the small things. If I can get into the habit of writing something a couple of times a week. Then maybe we can work up to interesting stuff.

So you want to learn C++

Hello World


Setting up WordPress to display syntax highlighted code was a struggle due to different plugins that don’t all seem to work together, the different types of editor, etc. I don’t want to learn all about WordPress. I just want to write some simple articles.

I am at the point where I am productive and don’t destroy my articles accidentally by switching between Visual editor and Text editor, however, I am still not totally happy. Writing articles in pure HTML is not the best solution. Even with help buttons, this is the realm of the web developer that needs to lay out elements perfectly. The article writer (blogger) just needs text to flow and highlight with a smattering of subtle color. I would prefer some slightly higher level markup such as in `Stackoverflow` or `github` preferably. If you have worked through this problem and have a good solution, drop me a line.

Here is a list of things I did to make myself productive:

* Turn off the Visual Editor
    Switching between the `visual` editor and the `text` editor always seems to destroy something in the code. What survived and what was mutated depended on the plugins but the result was always disastrous. Therefore turn it off.
    Of course this means I am now writing in HTML (not perfect buy I can manage).
    Goto `Users->Your Profile`. The first option allows you to disable the visual editor
* Install the plugins:
    + Crayon Syntax Highlighter:
    There are a lot of syntax highlighters out there. It does not matter which one you choose as they all seem to use the same back-end to do the coloring. This one worked for me.
    + Preserve Code Formatting:
    This prevents WordPress from mucking with the spaces between the &lt;pre&gt; tags.




Setting up WordPress to display syntax highlighted code was a struggle due to different plugins that don’t all seem to work together, the different types of editor, etc. I don’t want to learn all about WordPress. I just want to write some simple articles.

Want to set up WordPress to write about Programming


### 1: using namespace

Every new developer that comes to C++ always starts writing code like this:

myfirstprog.cpp
```c
#include <iostream>

using namespace std;
```

It seems reasonable and every book on learning C++ out there perpetrates the same mistake. The problem is the " **using namespace std;** ". On programs that are only 10 lines long (like in most books) it does not cause any problems. But as soon as your code strays to any meaningful size then it starts to become an issue. The problem with teaching new developers this technique is that they are not aware of the problems it causes and so it becomes a habit for all code they write. Break this habit **now** before you start doing it without thinking at the top of every source file you write.

So what are the actual issues? Please read this article: [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/14065) and the [best Answer](https://stackoverflow.com/a/1453605/14065) that explains what the problem is in detail.

We call this problem namespace pollution. What the `using` clause is doing is pulling everything from the named namespace into the current namespace; this will cause issues if there is already code in the current namespace. Doing this in your source file is bad enough but even worse is doing this in your header file. The problem with doing it in a header file is that you pollute the namespace for every source file that includes your header file. If the user of the header file is not aware of this pollution then trying to track down a suddenly new issue becomes really very hard.

But not doing this is causing my much more typing!

toomuch.cpp
```c
#include <iostream>
int main()
{
    cout << "Hello World\n";

    // Now looks much longer
    std::cout << "Hello World\n";
}
```

If you think adding `std::` as a prefix to anything in the standard namespace is a bother (then you need another language); there is a solution. Only pull into the current namespace what you actually need. And then try and restrict the scope so it is tight as possible;

short.cpp
```c
#include <iostream>
int main()
{
    using std::cout;
    // The using clause is scoped and thus cout is only in the global namespace for
    // the scope of the main() function.
    cout << "Hello Workld\n";
}
```

An additional technique to shorten namespace prefixes are namespace alias. These are very useful when things are nested inside multiple namespaces' (or have very long unhelpful names)

alias.cpp
```c
#include <boost/numeric/ublas/vector.hpp>

// Here we define bnu as an alias too: boost::numeric::ublas
// We can use either as the prefix to things in the that namespace;
namespace bnu = boost::numeric::ublas;

bnu::vector<double>                      data1;
boost::numeric::ublas::vector<double>    data2;
```

### 2: Prefixing identifiers with &#39;&#95;&#39;
A lot of developers new to C++ try to learn by browsing the standard libraries and getting there habits from things done there or bring conventions from their current favorite languages into there C++ code. One of the things they ultimately pick up on is using '&#95;' as a prefix for identifiers.

Though technically not wrong in all situations the actual rules on using the '&#95;' as an identifier prefix are non trivial. Thus making it a habit will eventually get you burnt. The issue is that most identifiers that have prefix '&#95;' are reserved for use by the implementation, thus the compiler/linker may potentially do special things with them. You can read up on the issue here: [What are the rules about using an underscore in a C++ identifier?](https://stackoverflow.com/q/228783/14065).

### 3: void main()
There are only two valid declarations from main in C++

main.cpp
```c
// Version 1: You don't care about command line parameters.
int main()
{
}

// Version 2: You do care about command line parameters.
int main(int argc, char* argv[])
{
        // Note: The parameters argc and argv are not actually required as a name.
        //       But they are so commonly defined that way that using any other
        //       names would cause experienced developers to do a double take.
        //       It is best to just stick with the convention.
}

// Version 2a: You do care about command line parameters.
#include <vector>
int main(int argc, char* argv[])
{
        // If you want to convert all the command line parameters to strings.
        // This simple trick can be useful:
        std::vector<std::string>  args(argv, argv+argc);
}
```


C++ for beginners. Part 2 Common Mistakes

Common Mistakes


## Variables

In most programming languages you have the concept of variables. These are simply named objects that hold a value (more formerly refereed to as state). By manipulating a variable you manipulate the state of the object that the variable referees too.

add.cpp
```c
void addFunction()
{
    int   x = 0;      // Declare (and initialize) a variable called "x"

    x = x + 5;        // Manipulate the variable "x".
                      // The variable "x" now holds the value "5"

    int   y = x + 3;  // Declare (and initialize) a variable called "y"
                      // This will take the value "8" by adding "+" 3
                      // to the value of "x"
}
```

C++ is a strongly typed language. This means that each variable has a specific type that does not change (above that type is **int**). The operations that can be performed on an object are dependent on the type of the object and the result of the operation can depend on the types involved. C++ has several built in types (listed below) but allows the definition of new user defined types (which will be described in a later article). The standard library provides a set of commonly used user defined types (listed below).

Built in Types
```c
char                    // Represents a character.
bool                    // Represents a boolean true/false value.
short                   // Represents an integer of at least 16 bits
int                     // Represents an integer of at least 32 bits
long                    // Represents an integer of at least 32 bits
long long               // Represents an integer of at least 64 bits
float                   // Represents a floating point number
double                  // Represents a double precision floating point number
```

Standard Types
```c
// This is a list of the most commonly used types (there are many more)
std::string             // Represents a string of characters.
std::vector<T>          // Represents a dynamically sizable array
                        //     of objects with the type 'T'
std::array<T, size>     // Represents a fixed 'size'  array
                        //     of objects with the type 'T'
std::list<T>            // Represents a list of objects with the type 'T'
std::map<Key, Value>    // Represents a dictionary of key, value pairs (index by key).
                        //     The key   has type 'Key'
                        //     The value has type 'Value'
std::set<Key>           // Represents a set of keys of type 'Key'
```

The list may seem a bit daunting at first, but while you are learning if you restrict yourselves to three built in types (**bool**, **int** and **double**) and two standard types (**std::string** and **std::vector&lt;T&gt;**) you will be able to solve most beginner/training problems.

The other built in types are usually used when you need larger range of values or need to save space. The additional standard type (shown above) are different types of container and provide different accesses characteristics (which will be explained later). We will cover all these types in due course.

So an example of usage of the most common types is:

variables.cpp
```c
#include <string>
#include <vector>
#include <iostream>

int main()
{
    int                       age   = 28;
    std::string               name  = "Loki";
    double                    grade = 12.45;
    std::vector<std::string>  courseNames = { "C++", "Teaching", "Maths", "Art", "Music"};

    std::cout << "Name: " << name  << "\n";
    std::cout << "Age:  " << age   << "\n";
    std::cout << "Grade:" << grade << "\n";
    std::cout << "Course 1: " << courseNames[1] << "\n";
}
```


C++ for beginners. Part 3 Variables. In most programming languages you have the concept of variables. These are simply named objects that hold a value (more formerly refereed to as state). By manipulating a variable you manipulate the state of the object that the variable referees too.

Variables


### Usage
All C++ applications must have at least one function; this is called `main()`. Additionally, you can have user defined functions that encapsulate individual tasks, thus allowing the code to be cleaner and easier to read. Therefore, this is a useful feature if you repeat the same task many time with only slight variations:

function1.cpp
```c
#include <string>
#include <iostream>

int main(int argc, char* argv[])
{
     std::cout << "What is your first name?\n";
     std::string firstName;
     std::cin >> firstName;

     std::cout << "What is your second name?\n";
     std::string secondName;
     std::cin >> secondName;

     std::cout << "What is your Mother's name?\n";
     std::string motherName;
     std::cin >> motherName;

     std::cout << "What is your Father's name?\n";
     std::string fatherName;
     std::cin >> fatherName;
}
```

It is easy to spot the obvious repetition here. We can simplify this code by using a function that does all the common work. Anything that is unique we can pass as parameters to the function.

function2.cpp
```c
#include <string>
#include <iostream>

std::string getNameFor(std::string who)
{
    std::cout << "What is your " << who << " name?\n";
    std::string result;
    std::cin >> result;
    return result;
}

int main(int argc, char* argv[])
{
     std::string firstName  = getNameFor("first");
     std::string secondName = getNameFor("second");
     std::string motherName = getNameFor("Mother's");
     std::string fatherName = getNameFor("Father's");
}
```

### Definition
OK. We have seen an example but what is the exact format of a function

function3.cpp
```c
// A function definition is very simple
<ReturnType>  <FunctionName>(<OptionalArgumentList>)
{
    <OptionalCode>
}

//  ReturnType:            This is the name of any type (built in or user defined)
//                         At the end of function you must have a statement
//                         that returns an object of this type.
//
//  FunctionName:          A unique name that identifies the function.
//
//  OptionalArgumentList:  This is either empty.
//                         Or a comma separated list of parameters.
//                         Because C++ is strongly typed each parameter is defined
//                         with both a type and a name.
//
//  OptionalCode:          We will be discussing this in more detail throught
//                         these articles. But the new statement to learn is
//                         `return <Value>`. This is the value returned by the
//                         function to the original caller.
//
//  Value:                 Notice that above I use the term `Value` and not object.
//                         A `Value` here can be an explicit object or the result
//                         of evaluating an expression (temporary object). Note
//                         one type of expression is a function call.
//
//                         return "An explicit String Object";
//
//                         return theResultOfAFunctionCall("Get A Result");
```

If a function has `void` return type then you don't need to **Return Statement**. With any other return type your function must exit by using a **Return Statement**. The **Return Statement** determines the value returned to the caller from the function. The one exception to this rule (and their has to be an exception to make it a rule) is `int main()`. If you don't explicitly have a **Return Statement** int `int main()` the compiler will plant `return 0;` for you.


### Forward Declaration

One thing to note about a function is that you can not use it before a declaration. We rewrite the original example above as:

function4.cpp
```c
#include <string>
#include <iostream>

int main(int argc, char* argv[])
{
     std::string firstName  = getNameFor("first");
     std::string secondName = getNameFor("second");
     std::string motherName = getNameFor("Mother's");
     std::string fatherName = getNameFor("Father's");
}

std::string getNameFor(std::string who)
{
    std::cout << "What is your " << who << " name?\n";
    std::string result;
    std::cin >> result;
    return result;
}
```

The only difference from above here is that I have moved the `main()` function before the `getNameFor()` function. This will generate a compilation error as you are using the function `getNameFor()` before a declaration. This may seem a potential problem but it is a deliberate technique that makes sure you spell things correctly before use. In the above situation the only change you need to make is a forward declaration. This allows you to declare a function before you define it. The utility of this will become clear when we start defining modules.

function5.cpp
```c
#include <string>
#include <iostream>

// Add a forward declaration
extern std::string getNameFor(std::string who);

// A forward declaration is basically a function declaration without a body.
// Add an extern prefix and a semicolon on the end (the rest you should copy
// and paste from the function definition).
//
//
// Note: For the languages lawyers who want to complain about the extern.
//       Just hold your horses we will get to the intricacies in due course;
//       this is only lesson 4.

int main(int argc, char* argv[])
{
     std::string firstName  = getNameFor("first");
     std::string secondName = getNameFor("second");
     std::string motherName = getNameFor("Mother's");
     std::string fatherName = getNameFor("Father's");
}

std::string getNameFor(std::string who)
{
    std::cout << "What is your " << who << " name?\n";
    std::string result;
    std::cin >> result;
    return result;
}
```



C++ for beginners. Part 4 Functions. All C++ applications must have at least one function; this is called `main()`. Additionally, you can have user defined functions that encapsulate individual tasks, thus allowing the code to be cleaner and easier to read. Therefore, this is a useful feature if you repeat the same task many time with only slight variations.

Functions


## Switching to OctoPress and Github

I have not blogged much, until recently, so I am not an HTML/CSS/Javascript expert. Thus layout, or layout during writing an article, is not of supreme importance for me. I expect the framework to handle that all for me. But that was my issue with WordPress. As a normal blogger I am sure it is not an issue, but the tools for blogging about code are rudimentary and not well integrated in to WordPress; basically forcing me to write in HTML (see [Set up WordPress](https://lokiastari.com/posts/WanttosetupWordPresstowriteaboutProgramming)). I do write a lot on other sites that specialize in coding and these sites have developed a style called &lt;MarkDown&gt;. The two most common versions are '[StackOverFlow markdown](https://stackoverflow.com/editing-help)' and '[GitHub markdown](https://daringfireball.net/projects/markdown/syntax)'.

### MarkDown

Markdown is a very simplistic form of 'Markup' (yes programmers think they are funny with the up/down thing) that is designed specifically to be simple and deal with the common issues of writing word based articles. Coder sites usually extend this with basic support for placing code (or pre-formatted text) directly into the article. It is not designed for non technical people (they should be using a 'Visual' interface not markup) but for the technical writer who does not want the full blown power of HTML, but wants slightly more control than visual interfaces provide.

### Attack Vector

WordPress is also infamous for being the target of attackers, thus new attacks are constantly being developed (the joy of being top dog). This can be mitigated by putting your WordPress site on [wordpress.com](https://wordpress.com). This not only provides you with free hosting, but they do keep on top of security vulnerabilities and make sure all hosted sites are not overexposed.

If you want use your own domain name (i.e. [LokiAstari.com](https://LokiAstari.com)) or any other "featured" services then you either need to fork up the cash (not an insignificant sum) or run your own WordPress site. So I have been running my own WordPress sites. However, running your own site opens you to the vulnerabilities of WordPress attacks. To be honest not a big deal until I actually tweeted about my articles (now very much so).

So the combination of these two issues has made me look for alternatives.

### OctoPress

[OctoPress](https://octopress.org) was suggested by a colleague [Dan Lecocq](https://github.com/danlecocq). It is basically an off-line blogging system that takes your articles and creates a set of static pages. You can then use several systems to publish these static pages. As the pages are generated once (each time you create a new article) the requirements for the hosting system are minimal, and consequently, because there is no dynamic content, there are no attack vectors that can be used against the site. Note: This does not mean the site has to be simple or boring as the pages can still have dynamic content loaded from other sites (like twitter/github/facebook etc.) It is just that the dynamic content will be fetched by the browser from other sites.

The other major advantage is that it natively supports MarkDown. In fact, you plug in your favorite MarkDown engine (I have currently stuck with the default 'GitHub markdown'). So you can write your article in MarkDown, and it will translate to the appropriate HTML.

Like WordPress it has multiple themes, unlike WordPress the user base is small so the pool of user created themes is tiny in comparison (a couple of dozen). Though not as well established as WordPress, you can easily extend it and build your own themes. There are already a couple of themes based on [Bootstrap](https://github.com/twbs/bootstrap) the most commonly forked HTML5/CSS/Javascript web-site project on [GitHub](https://github.com).

### GitHub

OctoPress also integrates with [GitHub Pages](https://pages.github.com/) a feature of the site designed to allow you to create documentation for your software.

Though this is still not my perfect writing environment; OctoPress is a step up from using WordPress (for me, if you are not used to writing code it will not be good for you and I would stick to WordPress's Visual editor). There are a couple of tweaks I still need to iron out here and there. Once I have got a basic system working perfectly I will talk about exactly what I did. I have some ideas on how to improve the basics which may be down the road a bit (I need to perform more research how others are using this tool so I don't reinvent the wheel).







Switching to OctoPress


So far we have demonstrated basic programs that just do a single task without making any decisions. Most (all but the most trivial) programming languages provide constructs for decision making (Conditional Branching).

C++ provides two forms of branching. The **"If Statement"** and the **"Switch Statement"** .

Note: Looping is also a form of branching. The looping concept is extensive enough that we will deal with looping separately in its own article.

### If Statement

The **"If Statement"** allows code to be executed when a certain condition is fulfilled and optionally an alternative piece of code otherwise.

ifstatement.cpp
```c
// First versin of "If Statement"
// Execute code if <Condition> is true.
//
if (<Condition>)
{
    <code to execute if Condition is true>
}


// Second version of "If Statement"
// Execute code1 if <Condition> is true or code2 if <Condition> is false
//
if (<Condition>)
{
    <code1: execute if Condition is true>
}
else
{
    <code2: execute if Condition is false>
}
```

The standard comparison operators that you find in most languages can be used. These operators are defined for all the built-in types. On user defined types in the standard library they are defined in ways that makes their usage obvious. When you define these for your user defined types you should also make sure that they behave in the logical manner described below; the language does not enforce this, **BUT** if you don't follow this suggestion your types will scare people and they will not be used, so follow the expected behavior.

Standard Comparison Operators
```
/*
| Operator  | Usage   | Result Type | Meaning                                                           |
| ----------|---------|-------------|-------------------------------------------------------------------|
|    !      |  !A     |  bool       | Not A. If A is true then false, if A is false then true.          |
|           |         |             | If A us not a bool type it is converted (see below)               |
|    ==     |  A == B |  bool       | true if A and B logically equivalent, otherwise false.            |
|    !=     |  A != B |  bool       | Should mean !(A == B)                                             |
|    <      |  A <  B |  bool       | true if A is logically less than B.                               |
|    <=     |  A <= B |  bool       | true if A is logically less than or equal to B.                   |
|    >      |  A >  B |  bool       | true if A is logically greater than B.                            |
|    >=     |  a >= B |  bool       | true if A is logically greater than or equal to B.                |
|    &&     |  A && B |  bool       | true if A is true **AND** B is true.                              |
|           |         |             | If the expressions A or B are not actually bool then              |
|           |         |             | it is converted (see below). Also worth noting is that            |
|           |         |             | if A is **false** then the expression for B is not evaluated.     |
|           |         |             | This is known as a shortcut operator we will describe this later. |
|    ||     |  A || B |  bool       | true if A is true **OR** B is true.                               |
|           |         |             | If the expressions A or B are not actually a bool then            |
|           |         |             | it is converted (see below). Also worth noting is that            |
|           |         |             | if A is **true** then the expression for B is not evaluated.      |
|           |         |             | This is known as a shortcut operator we will describe this later. |
|-----------|---------|-------------|-------------------------------------------------------------------|
*/
```

If the expression you use in &lt;Condition&gt; does not actually result in a bool value the compiler will insert a conversion that will result in a bool (true/false) value. If no conversion is possible it results in a compile time error.

Type conversion
```
/*
| Type             | false      | true            | Notes                                               |
|------------------|------------|-----------------|-----------------------------------------------------|
| bool             | false      | true            | Should be obvious: No actual conversion used.       |
| Integers         | 0          | (anything else) | Integer shorthand for (char/short/int/long)         |
| Pointers         | NULL       | (anything else) | Will discuss pointers in detail later.              |
| User Define Type | ?          | ?               | If a cast operator to bool/Integer/pointer exists   |
|                  |            |                 | this will be used.                                  |
|------------------|------------|-----------------|-----------------------------------------------------|
*/
```

An example of using an **If Statement**:

itest.cpp
```c
#include <iostream>
#include <string>

int main()
{
    std::string    name;
    std::cout << "Please enter your name\n";
    std::cin >> name;

    if (name == "Loki")
    {
        std::cout << "Hello Admin\n";
    }
    else
    {
        std::cout << "Hello Muggle\n";
    }

    int   value;
    std::cin >> value;
    std::cout << "Please enter a non zero integer value\n";
    if (value) // integer value converted to bool
    {
        std::cout << "You got it correct. Must use a non zero value.\n";
    }
}
```

### Switch Statement

The **"Switch Statement"** is an alternative to the **"If Statement"**. Prefer the switch when you have lots of options derived from the same expression. Unlike other high level language C++ can only use **Integer** types in a switch statement; thus in all `Case &lt;Value&gt; the &lt;Value&gt; must be an integer **literal** value.

switch.cpp
```c
switch(<Test Expression>)
{
    case <value1>:
    {
        <code1>
        break;
    }
    case <value2>:
    {
        <code2>
        break;
    }
    case <value3>:
    {
        <code3>
        break;
    }
    default:
    {
        <code Default>
        break
    }
}
//
//
// Equivalent "If Statement"

int test = <Test Expression>;
if (<value1> == test)
{
    <code1>
}
else
{
    if (<value2> == test)
    {
        <code2>
    }
    else
    {
        if (<value3> == test)
        {
            <code3>
        }
        else
        {
            <code Default>
        }
    }
}
```

If you use a non Integer expression in the switch statement the compiler will try and convert the value to an integer. If this is not possible it generates a compile time error.

switch.cpp
```c
    #include <iostream>

    int main()
    {
        int  value;
        std::cout << "Input a value between 0 and 5\n";
        std::cin >> value;

        switch(value)
        {
            case 0: {std::cout << "You used zero\n";    break;}
            case 1: {std::cout << "You used one\n";     break;}
            case 2: {std::cout << "You used two\n";     break;}
            case 3: {std::cout << "You used three\n";   break;}
            case 4: {std::cout << "You used four\n";    break;}
            case 5: {std::cout << "You used five\n";    break;}
            default: {std::cout << "You failed to follow instructions\n";break;}
        }
    }
```

Note I: The language does not require you to use a **Break Statement** in each block. **BUT** you should and compilers will warn you when you don't.
Note II: You should always use a **Default Statement** . If the value does not hit a value specified in a **Case Statement** then the **Default Statement** is used; If the **Default Statement** is not defined in this situation it results in undefined behavior. To avoid problems you should always define the **Default Statement**, even if all this does is generate an error. This will avoid maintenance issues down the road.







C++ for beginners. Part 5 Control Flow. So far we have demonstrated basic programs that just do a single task without making any decisions. Most (all but the most trivial) programming languages provide constructs for decision making (Conditional Branching).

Control Flow

## New Year/New Resolution
They say you can only get better at something by doing it.

I want to get better at writing articles about what I do so I better keep trying. Reading the articles I wrote last year (with the hindsight of a year) it seems my pros are a bit dry and laborious. So I am going to try again with an eye on fixing this problem.

My two main inspirations are colleges who do this rather well. [Kate Mate](https://katemats.com/) a highly talented manager whose opinions I respect and [Rand Fiskin](https://moz.com/rand/) the Wizard of Moz (though I am not sure he uses this tittle anymore). Both are highly respected in their fields and have the ability to write comprehensively and interestingly about subjects.


Nearly New Year/New Resolution

On [codereview.stackexchange.com](https://codereview.stackexchange.com) in the C++ tag it seems that it is a write of passage to implement your own version of a smart pointer. A quick search brings up the following:

* 02/Sep/2011 - [shared_ptr implementation](https://codereview.stackexchange.com/q/4550/507)
* 26/Nov/2011 - [Shared Pointer implementation](https://codereview.stackexchange.com/q/6320/507)
* 18/Apr/2013 - [Request for review: reference counting smart pointer](https://codereview.stackexchange.com/q/25214/507)
* 20/May/2013 - [Efficient smart pointer implementation in C++](https://codereview.stackexchange.com/q/26353/507)
* 11/Aug/2013 - [C++98 Unique Pointer Implementation](https://codereview.stackexchange.com/q/29629/507)
* 14/Aug/2013 - [I wrote a class to implement auto_ptr](https://codereview.stackexchange.com/q/29734/507)
* 28/Aug/2013 - [yet another shared pointer](https://codereview.stackexchange.com/q/30398/507)
* 04/Mar/2014 - [Smart pointer implementation](https://codereview.stackexchange.com/q/43472/507)
* 13/May/2014 - [One more shared pointer](https://codereview.stackexchange.com/q/49672/507)
* 14/Jun/2014 - [Is this a meaningful Intrusive Pointer Class?](https://codereview.stackexchange.com/q/54220/507)
* 04/Aug/2014 - [Simple shared pointer](https://codereview.stackexchange.com/q/59004/507)
* 08/Oct/2014 - [Smart but simple pointers](https://codereview.stackexchange.com/q/65127/507)
* 15/Nov/2014 - [Simple auto_ptr](https://codereview.stackexchange.com/q/69943/507)
* 19/Dec/2014 - [Yet another smart pointer implementation for learning](https://codereview.stackexchange.com/q/74166/507)

Writing you own implementation of a smart pointer is a bad idea (IMO). The standardization and testing of smart pointers was a nine year process through [boost](https://www.boost.org/), with [boost::shared_ptr](https://www.boost.org/doc/libs/1_57_0/libs/smart_ptr/shared_ptr.htm) and [boost::scoped_ptr](https://www.boost.org/doc/libs/1_57_0/libs/smart_ptr/scoped_ptr.htm), finally resulting in the standardized versions being released in C++11: [std::shared_ptr](https://en.cppreference.com/w/cpp/memory/shared_ptr) and [std::unique_ptr](https://en.cppreference.com/w/cpp/memory/unique_ptr).

I would even say that I dislike the smart pointer as a learning device; it seems like a very simple project for a newbie, but in reality (as indicated by the nine year standardization processes) getting it working correctly in all contexts is rather a complex endeavor.

But because it is such a frequent request for review; I want to take a look at smart pointers as a teaching exercise. In the next couple of articles I will step through the processes of building a smart pointer and look at some of the common mistakes that I see (and probably make a few as I go).

### Warning:
This article is not for absolute beginners. I assume you already know the basics of C++.

## First Bash
So lets get started. The two most common smart pointers are `unique` and `shared`. So lets start with the one that seems the simplest (`unique`)and see where we go.

It would seem that we could bash out a quick unique pointer like this:

ThorsAnvil::UP Version 1
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*   data;
        public:
            UP(T* data)
                : data(data)
            {}
            ~UP()
            {
                delete data;
            }
            T* operator->() {return data;}
            T& operator*()  {return *data;}
            T* release()
            {
                T* result = nullptr;
                std::swap(result, data);
                return result;
            }
            // So it can be used in conditional expression
            operator bool() {return data;}
    };
}
```
### Problem 1: Rule of Three Violation
The first problem here is that we are not obeying the "[rule of three](https://stackoverflow.com/q/4172722/14065)". Since we have a destructor that does memory management we should also handle the copy constructor and assignment operator. Otherwise the following is allowed and will cause undefined behavior:

Rule of Three Copy Constructor
```c

int test1()
{
    ThorsAnvil::UP   sp1<int>(new int(5));
    ThorsAnvil::UP   sp2<int>(sp1);  // copy construction

             // Here the compiler generated copy constructor
             // kicks in and does a member wise copy of sp1
             // into sp2. That in itself is not a problem.
}
// But when sp2 goes out of scope its destructor kicks in
// and deletes the pointer. When sp1 subsequently follows
// sp2 out of scope it will also call delete on the same
// pointer (as they share a copy of the pointer).
//
// This is known as a double delete and causes
// undefined behavior (UB).
```

 The assignment operator is slightly worse:

Rule of Three Assignment Operator
```c
int test2()
{
    ThorsAnvil::UP   sp1<int>(new int(5));
    ThorsAnvil::UP   sp2<int>(new int(6));

    sp2 = sp1; // Assignment operation.

             // Here the compiler generated assignment
             // operator kicks in and does a member wise
             // assignment of sp1 into sp2.
             //
             // The main problem with the assignment here
             // is that we have lost the original pointer
             // that sp2 was holding.
}
// Same issues with double delete as the copy constructor.
```
This is caused by the compiler atomically generating default implementations of certain methods (see discussion on the [rule of three](https://stackoverflow.com/q/4172722/14065)) if the user does not explicitly specify otherwise. In this case the problem comes because of the compiler generated versions of the copy constructor and assignment operator (see below)

Compiler Generated Methods.
```c
namespace ThorsAnvil
{
    .....
        // Compiler Generated Copy Constructor
        UP(UP const& copy)
            : data(copy.data)
        {}

        // Compiler Generated Assignment Operator
        UP& UP::operator=(UP const& rhs)
        {
            data    = rhs.data;
            return *this;
        }
}
```
I have heard this described as a language bug; but I have to disagree with that sentiment, as these compiler generated methods do exactly as you would expect in nearly all situations. The one exceptions is when the class contains "owned raw pointers".
### Problem 2: Implicit construction.
The next issue is caused by C++ tendency to eagerly convert one type to another if given half a chance. If your class contains a constructor that takes a single argument then the compiler will use this as a way of converting one type to another.

Example
```c
void takeOwner1(ThorsAnvil::UP<int> x)
{}
void takeOwner2(ThorsAnvil::UP<int> const& x)
{}
void takeOwner3(ThorsAnvil::UP<int>&& x)
{}
int main()
{
    int*   data = new int(7);

    takeOwner1(data);
    takeOwner2(data);
    takeOwner3(data);
}
```
Though none of the functions in the example take an `int pointer` as a parameter; the compiler sees that it can convert an `int*` into an object of type `ThorsAnvil::UP<int>` via the single argument constructor and builds temporary objects to facilitate the calling of the function.

In the case of smart pointers, that take ownership of the object passed in the constructor, this can be a problem because the lifetime of a temporary object is the containing statement (with a few exceptions that we will cover in another article). As a simple rule of thumb you can think of the lifespan of a temporary ending at the `';'`.

Temporary Object
```c
takeOwner1(data);

// You can think of this as functionally equivalent to:

{
    ThorsAnvil::UP<int> tmp(data);
    takeOwner1(tmp);
}
```
The problem here is that when `tmp` goes out of scope its destructor will call delete on the pointer. Thus `data` is now pointing at memory that has been destroyed (and thus no longer belongs to the application). Any further use of `data` is going to potentially cause problems (and I am being generous using the word potentially).

This feature can be quite useful (when you want this conversion to happen easily, see std::string). But you should definitely be aware of it and think carefully about creating single argument constructors.
### Problem 3: Null de-referencing
I think it is obvious that `operator*` has an issue with de-referencing a Null pointer here:

operator&ast;()
```c
T& operator*()  {return *data;}
```
But it is not quite as obvious that `operator->` is also going to cause dereferencing of the pointer here:

operator->()
```c
T* operator->() {return data;}
```
There are a couple of solutions to this problem. You can check `data` and throw an exception if it is a Null pointer, or alternatively you can make it a pre-condition on the usage of the smart pointer (ie it is the responsibility of the user to either know or check the state of the smart pointer before using these methods).

The standard has chosen to go with a pre-condition (a very common C++ practice: do not impose an overhead on all your users (to spare problems for the beginner), but rather provide a mechanism to check the state for those that need to do so; so they can choose to pay the overhead when they need to and not every time). We can do the same here but we have not provided any mechanism for the user to check the state of the smart pointer.
### Problem 4: Const Correctness
When accessing the owned object via a smart pointer we are not affecting the state of our smart pointer so any member that basically returns the object (without changing the state of the smart pointer) should be marked const.

Not const
```c
T* operator->() {return data;}
T& operator*()  {return *data;}
```
So these two methods should really be declared as:

Const Correct
```c
T* operator->() const {return data;}
T& operator*()  const {return *data;}
```
### Problem 5: Bool conversion to easy
The current `operator bool()` works as required in bool expressions.

Check for value
```c
ThorsAnvil::UP<int>    value(new int(4));

if (value) {
    std::cout << "Not empty\n";
}
```
But the compiler will also use the conversion operators when it is trying to coerce objects that nearly match. For example you can now test two `UP` with `operator==` even though there does not exists an actual `operator==` for the `UP<>` class. This is because the compiler can convert both `UP<>` objects to bool and these can be compared.

Auto conversion is bad (mostly)
```c
ThorsAnvil::UP<int>    value1(new int(8));
ThorsAnvil::UP<int>    value2(new int(9));

if (value1 == value2) {
    // unfortunately this will print "They match".
    // Because both values are converted to bool (in this case true).
    // Then the test is done.
    std::cout << "They match\n";
}
```
In C++03 there was a nasty work around using pointers to members. But in C++11 there was added new functionality to make the conversion operator only fire in a boolean context otherwise it must be explicitly called.

explicit converter
```c
explicit operator bool() {return data;}
...
ThorsAnvil::UP<int>    value1(new int(8));
ThorsAnvil::UP<int>    value2(new int(9));

if (value1) { // This is expecting a boolean expression.
    std::cout << "Not nullptr\n";
}

if (static_cast<bool>(value1) == static_cast<bool>(value2)) { // Need to be explicit
    std::cout << "Both are either nullptr or not\n";
}
```
## Fixed First Try
So given the problems described above we can update our implementation to compensate for these issues:

horsAnvil::UP Version 2
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*   data;
        public:
            // Explicit constructor
            explicit UP(T* data)
                : data(data)
            {}
            ~UP()
            {
                delete data;
            }
            // Remove compiler generated methods.
            UP(UP const&)            = delete;
            UP& operator=(UP const&) = delete;

            // Const correct access owned object
            T* operator->() const {return data;}
            T& operator*()  const {return *data;}

            // Access to smart pointer state
            T* get()                 const {return data;}
            explicit operator bool() const {return data;}

            // Modify object state
            T* release()
            {
                T* result = nullptr;
                std::swap(result, data);
                return result;
            }
    };
}
```
If you are thinking this is not enough you are correct. We still have some more work to do. But lets leave it at that for version one.
## Summary
So in this initial post we have looked at a typical first attempt at a smart pointer and summarized the common problems I often see in these home grown smart pointer implementations.


C++ By Example. Part 1 Unique Pointer. It seems that it is a write of passage to implement your own version of a smart pointer. This article examines some of the common mistakes made by developers developing their own smart pointers.

C++ By Example

Smart-Pointer - Unique Pointer

So in [the previous article](https://lokiastari.com/posts/Smart-Pointer-UniquePointer) I covered a basic `unique` pointer where the smart pointer retained sole ownership of the pointer. The other common smart pointer we encounter is the `shared` pointer (SP). In this case the ownership of the pointer is shared across multiple instances of SP and the pointer is only released (deleted) when all SP instances have been destroyed.

So not only do we have to store the pointer but we need a mechanism for keeping track of all the SP instances that are sharing ownership of the pointer. When the last SP instance is destroyed it also deletes the pointer (The last owner cleans up. A similar principle to the last one to leave the room turns out the lights).

Shared Pointer contextual destructor
```c
namespace ThorsAnvil
{
    template<typename T>
    class SP
    {
        T*  data;
        public:
            ~SP()
            {
                if (amITheLastOwner())
                {
                    delete data;
                }
            }
    };
}
```
There are two major techniques for tracking the shared owners of a pointer:

<ol>
  <li>Keep a count:</li>
  <ul>
    <li>When the count is 1 you are the last owner.</li>
    <li>This is a very simple and logical technique. You have a shared counter that is incremented/decrement as SP instances take/release ownership of the pointer. The disadvantages are that you need dynamically allocated memory that must be managed and in a threaded environment you need to serialize accesses to counter.</li>
  </ul>
  <li>Use a linked list of the owners:</li>
  <ul>
    <li>When you are the only member of the list you are the last owner.</li>
    <li>When a SP instance take/releases ownership of the pointer they are added/removed to/from the linked list. This is slightly more complex as you need to maintain a circular linked list (for O(1)). The advantage is that you do not need to manage any separate memory for the count (A SP instance simply points at the next SP instance in the chain) and in a threaded environment adding/removing a shared pointer need not always be serialized (though you will still need to lock your neighbors to enforce integrity).</li>
  </ul>
</ol>

## Shared Count
The easier of the two to implement correctly is the list version. There are no real gotchas (that I have seen). Though people do struggle with insertion and removal of a link from a circular list. I have another article planned for that at some point so I will cover it then.

The *Shared Count* is basically the technique used by the [`std::shared_ptr`](https://en.cppreference.com/w/cpp/memory/shared_ptr) (though they store slightly more than the count to try and improve efficiency see [`std::make_shared`](https://en.cppreference.com/w/cpp/memory/shared_ptr/make_shared)).

The main mistake I see from beginners is not using dynamically allocated counter (i.e. they keep the counter in the SP object). You **must** dynamically allocate memory for the counter so that it can be shared by all SP instances (you can not tell how many there will be or the order in which they will be deleted).

You must also serialize access to this counter to make sure that in a threaded environment the count is correctly maintained. In the first version for simplicity I will only consider single threaded environments and thus synchronization is not required.

First Try
```c
namespace ThorsAnvil
{
    template<typename T>
    class SP
    {
        T*      data;
        int*    count;
        public:
            // Remember from ThorsAnvil::UP that the constructor
            // needs to be explicit to prevent the compiler creating
            // temporary objects on the fly.
            explicit SP(T* data)
                : data(data)
                , count(new int(1))
            {}
            ~SP()
            {
                --(*count);
                if (*count == 0)
                {
                    delete data;
                }
            }
            // Remember from ThorsAnvil::UP that we need to make sure we
            // obey the rule of three. So we will implement the copy
            // constructor and assignment operator.
            SP(SP const& copy)
                : data(copy.data)
                , count(copy.count)
            {
                ++(*count);
            }
            SP& operator=(SP const& rhs)
            {
                // Keep a copy of the old data
                T*   oldData  = data;
                int* oldCount = count;

                // now we do an exception safe transfer;
                data  = rhs.data;
                count = rhs.count;

                // Update the counters
                ++(*count);
                --(*oldCount);

                // Finally delete the old pointer if required.
                if (*oldCount == 0)
                {
                    delete oldData;
                }
            }
            // Const correct access owned object
            T* operator->() const {return data;}
            T& operator*()  const {return *data;}

            // Access to smart pointer state
            T* get()                 const {return data;}
            explicit operator bool() const {return data;}
    };
}
```
### Problem 1: Potential Constructor Failure
When a developer (attempts) to create a SP they are handing over ownership of the pointer to the SP instance. Once the constructor starts there is an expectation by the developer that no further checks are needed. But there is a problem with the code as written.

In C++ memory allocation through new does not fail (unlike C where `malloc()` can return a Null on failure). In C++ a failure to allocate memory via the standard new generates a `std::bad_alloc` exception. Additionally if we throw an exception out of a constructor the destructor will never be called (the destructor is only called on fully formed objects) when the instance's lifespan ends.

So if an exception is thrown during construction (and thus the destructor will not be called) we must assume responsibility for making sure that pointer is deleted before the exception escapes the constructor, otherwise there will be a resultant leak of the pointer.

Constructor takes responsibility for pointer
```c
namespace ThorsAnvil
{
     .....
             explicit SP(T* data)
                : data(data)
                , count(new (std::nothorw) int(1)) // use the no throw version of new.
            {
                // Check if the pointer correctly allocated
                if (count == nullptr)
                {
                    // If we failed then delete the pointer
                    // and manually throw the exception.
                    delete data;
                    throw std::bad_alloc();
                }
            }
            // or
     .....
            explicit SP(T* data)
            // The rarely used try/catch for exceptions in argument lists.
            try
                : data(data)
                , count(new int(1))
            {}
            catch(...)
            {
                // If we failed because of an exception
                // delete the pointer and rethrow the exception.
                delete data;
                throw;
            }
}
```
### Problem 2: DRY up the Assignment
Currently the assignment operator is exception safe and conforms to the strong exception guarantee so there is no real problem here. **But** there seems to be a lot of duplicated code in the class.

Closer look at assignment
```c
namespace ThorsAnvil
{
     .....
            SP& operator=(SP const& rhs)
            {
                T*   oldData  = data;
                int* oldCount = count;

                data  = rhs.data;
                count = rhs.count;
                ++(*count);

                --(*oldCount);
                if (*oldCount == 0)
                {
                    delete oldData;
                }
            }
}
```
Two portions of this look like other code pieces of code that have already been written:

```c
    // This looks like the SP copy constructor.
                    data  = rhs.data;
                    count = rhs.count;
                    ++(*count);

    // This looks like the SP destructor.
                    --(*oldCount);
                    if (*oldCount == 0)
                    {
                        delete oldData;
                    }
```
This observation is commonly referred to as the **[Copy and Swap Idiom](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom)**. I will not go through all the details of the transformation here. But we can re-write the assignment operator as:

Copy and Swap Idiom
```c
SP& operator=(SP const& rhs)
{
    // constructor of tmp handles increment.
    SP tmp(rhs);

    std::swap(data,  tmp.data);
    std::swap(count, tmp.count);
    return *this;
}   // the destructor of tmp is executed here.
    // this handles the decrement and release of the pointer

// This is usually simplified further into
SP& operator=(SP rhs) // Note implicit copy because of pass by value.
{
    rhs.swap(*this);  // swaps moved to swap method.
    return *this;
}
```

## Fixed First Try
So given the problems described above we can update our implementation to compensate for these issues:

Fixed First Try
```c
namespace ThorsAnvil
{
    template<typename T>
    class SP
    {
        T*      data;
        int*    count;
        public:
            // Explicit constructor
            explicit SP(T* data)
            try
                : data(data)
                , count(new int(1))
            {}
            catch(...)
            {
                // If we failed because of an exception
                // delete the pointer and rethrow the exception.
                delete data;
                throw;
            }
            ~SP()
            {
                --(*count);
                if (*count == 0)
                {
                    delete data;
                }
            }
            SP(SP const& copy)
                : data(copy.data)
                , count(copy.count)
            {
                ++(*count);
            }
            // Use the copy and swap idiom
            // It works perfectly for this situation.
            SP& operator=(SP rhs)
            {
                rhs.swap(*this);
                return *this;
            }
            SP& operator=(T* newData)
            {
                SP tmp(newData);
                tmp.swap(*this);
                return *this;
            }
            // Always good to have a swap function
            // Make sure it is noexcept
            void swap(SP& other) noexcept
            {
                std::swap(data,  other.data);
                std::swap(count, other.count);
            }
            // Const correct access owned object
            T* operator->() const {return data;}
            T& operator*()  const {return *data;}

            // Access to smart pointer state
            T* get()                 const {return data;}
            explicit operator bool() const {return data;}
        };
}
```
## Summary
So in this second post we have looked SP and mentioned the two main implementation techniques commonly used. We specifically looked in detail at some common problems usually overlooked in the counted implementation of SP. In the next article I want to look at a couple of other issues common to both types of smart pointers.


C++ By Example. Part 2 Shared Pointer. In this article we cover some of the common implementation techniques used for a smart pointer that provides shared ownership of a resource.

Smart-Pointer - Shared Pointer

In this article we examine constructors that are often missed or overlooked. This article looks at the use cases for these constructors and explains why the added functionality provides a meaningful addition in relation to smart pointers.

## Default Constructor
Most people remember the default constructor (a zero argument constructor), but every now and then it gets missed.

The default constructor is useful when the type is used in a context where objects of the type need to be instantiated dynamically by another library (an example is a container resized; when a container is made larger by a resize, new members will need to be constructed, it is the default constructor that will provide these extra instances).

The default constructor is usually very trivial and thus worth the investment.

Smart Pointer Default Constructor
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*      data;
        public:
            UP()
                : data(nullptr)
            {}
            .....
    };
}
```
## The nullptr
In C++11 the `nullptr` was introduced to replace the old broken `NULL` and/or the even more broken `0` for use in contexts where you want a pointer that points at nothing. The `nullptr` is automatically convert to any pointer type or a boolean; but fixed the previous bug (or bad feature) and will not convert to a numeric type.

nullptr Usage Example
```c
#include <string>
int main()
{
    char*           tmp = nullptr;   // converts the nullptr (type std::nullptr_t) to char*
    std::string*    str = nullptr;   // hopefully you never do that! but it works.

    bool            tst = nullptr;   // False. Yes I know it does not look that useful.
                                     //        But when you consider all the funny things
                                     //        that can happen with templates this can
                                     //        be very useful.

    int             val = nullptr;   // Fails to compile.
    int             val = NULL;      // Pointer assigned to integer value.
                                     // Works just fine. But very rarely was this a useful
                                     // feature (more usually an over-site that was not
                                     // reported by the compiler).
}
```
The `nullptr` provides some opportunities to make the code shorter/cleaner when initializing smart pointers to be empty. Because we are using explicit one argument constructors the compiler can not convert a `nullptr` into a smart pointer automatically, it must be done explicitly by the developer.

nullptr failing on Smart Pointer
```c
void workWithSP(ThorsAnvil::UP<int>&& sp)
{ /* STUFF*/ }

int main()
{
    // This fails to compile.
    workWithSP(nullptr);

    // Need to be explicit with smart pointers
    workWithSP(ThorsAnvil::UP<int>(nullptr));
}
```
This is overly verbose, there is no danger involved in forming a smart pointer around a `nullptr` automatically. Because `nullptr` has its own type `std::nullptr_t` we can add a constructor to explicitly simplify this case, which makes it easier to read.

Smart Pointer with std::nullptr_t constructor
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        public:
            UP(std::nullptr_t)
                : data(nullptr)
            {}
	....
    };
}
// Now we can simplify our use case
void workWithSP(ThorsAnvil::UP<int>&& sp)
{ /* STUFF*/ }

int main()
{
    workWithSP(nullptr);

    // Note this also allows:
    ThorsAnvil::UP<int>   data  = nullptr;
    // And
    data = nullptr;       // Note here we have we convert nullptr to
                          // smart pointer using the one argument
                          // constructor that binds `nullptr` then
                          // call the assignment operator.
                          //
                          // That seems like a lot extra work. So we
                          // may as well define the assignment operator
                          // to specifically user `nullptr`.
}
```
## Move Semantics
Move semantics were introduced with C++ 11. So though we can not copy the `ThorsAnvil::UP` object it can be moved. The compiler will generate a default move constructor for a class under certain situations; but because we have defined a destructor for `ThorsAnvil::UP` we must manually define the move constructor.

Move semantics say that the source object may be left in an undefined (but must be valid) state. So the easiest way to implement this is simply to swap the state of the current object with the source object (we know our state is valid so just swap it with the incoming object state (its destructor will then take care of destroying the pointer we are holding)).

Smart Pointer Move Semantics
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*      data;
        public:
            // Swap should always be `noexcept` operation
            void swap(UP& src) noexcept
            {
                std::swap(data, src.data);
            }
            // It is a good idea to make your move constructor `noexcept`
            // In this case it actually makes no difference (because there
            // no copy constructor) but to maintain good practice I still
            // think it is a good idea to mark it with `noexcept`.
            UP(UP&& moving) noexcept
            {
                moving.swap(*this);
            }
            UP& operator=(UP&& moving) noexcept
            {
                moving.swap(*this);
                return *this;
            }
            .....
    };
    template<typename T>
    void swap(UP<T>& lhs, UP<T>& rhs)
    {
        lhs.swap(rhs);
    }
}
```
## Derived Type Assignment.
Assigning derived class pointers to a base class pointer object is quite common feature in C++.

Derived Example
```c
class Base
{
    public:
        virtual ~Base() {}
        virtual void doAction() = 0;
};
class Derived1: public Base
{
    public:
        virtual void doAction() override;
};
class Derived2: public Base
{
    public:
        virtual void doAction() override;
};
int main(int argc, char* argv[])
{
    Derived1*   action1 = new Derived1;
    Derived2*   action2 = new Derived2;

    Base*       action   = (argc == 2) ? action1 : action2;
    action->doAction();
}
```
If we try the same code with the constructors we currently have we will get compile errors.

Derived Example with Smart Pointers
```c
int main(int argc, char* argv[])
{
    ThorsAnvil::UP<Derived1>    action1 = new Derived1;
    ThorsAnvil::UP<Derived2>    action2 = new Derived2;

    ThorsAnvil::UP<Base>        action   = std::move((argc == 2) ? action1 : action2);
    action->doAction();
}
```
This is because C++ considers `ThorsAnvil::UP<Derived1>`, `ThorsAnvil::UP<Derived2>` and `ThorsAnvil::UP<Base>` are three distinct classes that are unrelated. As this kind of pointer usage is rather inherent in how C++ is used the smart pointer needs to be designed for this use case.

To solve this we need to allow different types of smart pointer be constructed from other types of smart pointer, but only where the inclosed types are related.

Derived Smart Pointer transfer
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*      data;
        public:
            // Release ownership of the pointer.
            // Returning the pointer to the caller.
            T*  release()
            {
                T* tmp = nullptr;
                std::swap(tmp, data);
                return tmp;
            }
            // Note: If you try calling this with a U that is not derived from
            //       a T then the compiler will generate a compilation error as
            //       the pointer assignments will not match correctly.
            template<typename U>
            UP(UP<U>&& moving)
            {
                // We can not use swap directly.
                // Even though U is derived from T, the reverse is not true.
                // So we have put it in a temporary locally first.

                // Note: this is still exception safe.
                //       The normal constructor will call delete even if it does
                //       not finish constructing. So if release completes even
                //       starting the call to the constructor guarantees its safety.
                UP<T>   tmp(moving.release());
                tmp.swap(*this);
            }
            template<typename U>
            UP& operator=(UP<U>&& moving)
            {
                UP<T>    tmp(moving.release());
                tmp.swap(*this);
                return *this;
            }
            .....
    };
}
```
## Updated Unique Pointer
Combine the constructor/assignment operators discussed in this article with the `ThorsAnvil::UP` that we defined in the first article in the series: [Unique Pointer](https://lokiastari.com/posts/Smart-Pointer-UniquePointer) we obtain the following:

ThorsAnvil::UP Version 3
```c
namespace ThorsAnvil
{
    template<typename T>
    class UP
    {
        T*   data;
        public:
            UP()
                : data(nullptr)
            {}
            // Explicit constructor
            explicit UP(T* data)
                : data(data)
            {}
            ~UP()
            {
                delete data;
            }

            // Constructor/Assignment that binds to nullptr
            // This makes usage with nullptr cleaner
            UP(std::nullptr_t)
                : data(nullptr)
            {}
            UP& operator=(std::nullptr_t)
            {
                reset();
                return *this;
            }

            // Constructor/Assignment that allows move semantics
            UP(UP&& moving) noexcept
            {
                moving.swap(*this);
            }
            UP& operator=(UP&& moving) noexcept
            {
                moving.swap(*this);
                return *this;
            }

            // Constructor/Assignment for use with types derived from T
            template<typename U>
            UP(UP<U>&& moving)
            {
                UP<T>   tmp(moving.release());
                tmp.swap(*this);
            }
            template<typename U>
            UP& operator=(UP<U>&& moving)
            {
                UP<T>    tmp(moving.release());
                tmp.swap(*this);
                return *this;
            }

            // Remove compiler generated copy semantics.
            UP(UP const&)            = delete;
            UP& operator=(UP const&) = delete;

            // Const correct access owned object
            T* operator->() const {return data;}
            T& operator*()  const {return *data;}

            // Access to smart pointer state
            T* get()                 const {return data;}
            explicit operator bool() const {return data;}

            // Modify object state
            T* release() noexcept
            {
                T* result = nullptr;
                std::swap(result, data);
                return result;
            }
            void swap(UP& src) noexcept
            {
                std::swap(data, src.data);
            }
            void reset()
            {
                T* tmp = releae();
                delete tmp;
            }
    };
    template<typename T>
    void swap(UP<T>& lhs, UP<T>& rhs)
    {
        lhs.swap(rhs);
    }
}
```
## Summary
In the last two articles ([Unique Pointer](https://lokiastari.com/posts/Smart-Pointer-UniquePointer) and [Shared Pointer](https://lokiastari.com/posts/Smart-Pointer-SharedPointer)) we covered some basic mistakes that I have often seen developers make when attempting to creating their own smart pointer. I also introduce four important C++ concepts:

 - [Rule of Three](https://stackoverflow.com/q/4172722/14065)
 - [Copy and Swap Idiom](https://stackoverflow.com/q/3279543/14065)
 - [Explicit One Argument Constructor](https://stackoverflow.com/a/121163/14065)
 - [Try/Catch on Initialization List](https://stackoverflow.com/q/12697625/14065)

This article I focused on a couple of constructors/assignment operators that can be overlooked overlooked.


C++ By Example. Part 3 Smart Pointer Constructors. In this article we examine constructors that are often missed or overlooked. This article looks at the use cases for these constructors and explains why the added functionality provides a meaningful addition in relation to smart pointers.

Smart-Pointer - Constructors


A lot of new developers to C++ attempt to build a `Vector` like container as a learning processes. Getting a simple version of this working for POD types (like int) is not that complicated. The next step in getting this working for arbitrary data types takes a significant leap forward in thinking in C++ especially when you start looking at efficiency and exception safety. This set of five articles looks at building an efficient `Vector` implementation. I show some of the common mistakes and explain why and how to resolve the problems:

Note: This is not meant to replace `std::vector<>` this is simply meant as a teaching process.

# Rule of Zero

You will notice that half the attempts below [Sources](#Sources) are Vector implementations the other half are for Matrix implementations. I mention both because I want to emphasize the [Separation of concerns](https://en.wikipedia.org/wiki/Separation_of_concerns). An object should be responsible for either business logic or resource management (not both). A lot of the Matrix implementations are trying to mix resource management (memory management) with the business logic of how matrices interact. So if you want to write a matrix class you should delegate resource management to a separate class (In a first pass `std::vector<int>` would be a good choice).

In C++ the compiler generates a couple of methods for free.

* Destructor
* Copy Constructor
* Copy Assignment Operator
* Move Constructor
* Move Assignment Operator

These methods usually work perfectly well; **unless** your class contains a pointer (or a pointer like resource object). But if your class is doing business logic then it should not contain a pointer. So classes that handle business logic therefore should not be defining any of these compiler generated methods (just let the compiler generated ones work for you). Occasionally you want to delete them, to prevent copying or movement, but it is very unusual for these to need specialized implementations.

Conversely, classes that do resource management usually contain a pointer (or pointer like resource object). These classes should define all the above methods to correctly handle the resource. This is where ownership semantics of the resource are defined. The owner of the resource is responsible for destroying the resource when its lifespan is over (in terms of pointers this means the owner is responsible for calling `delete` on the pointer, usually in the destructor). If you are not the owner of a resource you should not have access to the resource object directly, as it may be destroyed by the owner without other objects knowing.

# [Rule of three](https://stackoverflow.com/q/4172722/14065)

The rule of three comes from C++03 where we only had copy semantics.

## Version-1 Simple Resource Management
When creating a class to manage resources; the first version created by beginner usually looks like this:

Rule of three first pass
```c
template<typename T>
class Vector
{
    std::size_t     size;
    T*              buffer;
    Vector(int size = 100)
        : size(size)
        , buffer(new T[size])   // Allocate the resource
    {}
    ~Vector()
    {
        delete [] buffer;       // Clean up the resource
    }
};
```
The trouble here is that this version has a fundamental flaw because of the way the [compiler generated](https://stackoverflow.com/a/4044360/14065) copy constructor and copy assignment operator work with pointers (commonly referred to as the [shallow copy problem](https://stackoverflow.com/q/2344664/14065)).

Shallow copy problem.
```c
int main()
{
    Vector<int>   x;
    Vector<int>   y(x);     // Compiler generate copy constructure does
                            // an element wise shallow copy of each element.
                            // This means both `x` and `y` have a buffer
                            // member that points at the same area in memory.
                            //
                            // When the objects go out of scope both will
                            // try and call delete on the memory resulting
                            // in a double delete of the memory.

    Vector<int>   z;        // Same problem after an assignment.
    z=x;
}
```

## Version-2 Rule of Three
The rule of three simply stated is: If you define any of the methods Destructor/Copy Constructor/Copy Assignment Operator then you should define all three. When done correctly this resolves the shallow copy problem. `Vector` defines the destructor so we also need to define the copy constructor and copy assignment operator.

I see this as an initial attempt at defining the rule of three for vectors very often.

Rule of three second pass
```c
template<typename T>
class Vector
{
    std::size_t     size;
    T*              buffer;
    Vector(int size = 100)
        : size(size)
        , buffer(new T[size])
    {}
    ~Vector()
    {
        delete [] buffer;
    }
    Vector(Vector const& copy)
        : size(copy.size)
        , buffer(new T[size])
    {
        // Copy constructor is simple.
        // We create a new resource area of the required size.
        // Then we copy the data from the old buffer to the new buffer.
        std::copy(copy.buffer, copy.buffer + copy.size, buffer);
    }
    Vector& operator=(Vector const& copy)
    {
        // Copy Object
        // This is relatively easy. But I want to cover this in detail in a subsquent post.
        return *this;
    }
};
```

## Version-3 Lazy Construction of elements.

The problem with the previous version is that it forces initialization of all elements in the buffer immediately. This forces the requirement that members of the `Vector` (i.e. type `T`) must be default constructable. It also has two efficiency constraints imposed on the Vector:

* You can't pre-allocate space for future members.
    + So resizing (larger or smaller) becomes very expensive as each resize requires copy all the elements to the newly re-sized buffer.
    + Alternatively pre-creating all the elements you need can also be expensive especially if construction of `T` is expensive.
* The copy constructor is twice as expensive as it should be. Each element must be:
    + Default constructed (when the buffer is created).
    + Then copy constructed with the value from the source vector.


This attempt improves on that by allowing efficient pre-allocating of space (`capacity`) for the buffer. New members are then added by constructing in-place using [placement new](https://stackoverflow.com/questions/362953/what-are-uses-of-the-c-construct-placement-new).

Rule of three third pass
```c
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    Vector(int capacity)
        : capacity(capacity = 100)
        , length(0)
        // Allocates space but does not call the constructor
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        // Useful if the type T has an expensive constructor
        // We preallocate space without initializing it giving
        // room to grow and shrink the buffer without re-allocating.
    {}
    ~Vector()
    {
        // Because elements are constructed in-place using
        // placement new. Then we must manually call the destructor
        // on the elements.
        for(int loop = 0; loop < length; ++loop)
        {
            // Note we destroy the elements in reverse order.
            buffer[length - 1 - loop].~T();
        }
        ::operator delete(buffer);
    }
    Vector(Vector const& copy)
        : capacity(copy.length)
        , length(0)
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
    {
        // Copy constructor is simple.
        // We create a new resource area of the required length.
        // But these elements are not initialized so we use push_back to copy them
        // into the new object. This is an improvement because we
        // only construct the members of the vector once.
        for(int loop = 0; loop < copy.length; ++loop)
        {
            push_back(copy.buffer[loop]);
        }
    }
    Vector& operator=(Vector const& copy)
    {
        // Copy Object
        // This is relatively easy. But I want to cover this in detail in a subsquent post.
        return *this;
    }
    void push_back(T const& value)
    {
        // Use placement new to copy buffer into the new buffer
        new (buffer + length) T(value);
        ++length;

        // Note we will handle growing the capacity later.
    }
    void pop_back()
    {
        // When removing elements need to manually call the destructor
        // because we created them using placement new.
        --length;
        buffer[length].~T();
    }
};
```

# Rule of Five

In C++11 the language added the concept of "Move Semantics". Rather than having to copy an object (especially on return from a function) we could "move" an object. The concept here is that movement is supposed to be much cheaper than copying because you move the internal data structure of an object rather than all the elements. A good example is a std::vector. Before C++11 a return by value meant copying the object. The constructor of the new object allocates a new internal buffer and then copies all the elements from the original object's buffer to the new object's buffer. On the other hand a move simply gives the new object the internal buffer of the old object (we just move the pointer to the internal buffer). When an object is moved to another object the old object should be left in a valid state, but for efficiency the standard rarely specifies the state of an object after it has been the source of a move. Thus using an object after a move is a bad idea unless you are setting it to a specific state.

There are two new methods that allow us to specify move semantics on a class.

Vector Move Semantics.
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF

    // Move Constructor
    Vector(Vector&& move) noexcept;

    // Move Assignment Operator
    Vector& operator=(Vector&& move) noexcept;
};
```

Notice the `&&` operator. This donates an r-value reference and means that your object is the destination of a move operation. The parameter passed is the source object and the state you should use to define your new object's state. After the move the source object must be left in a valid (but can be undefined state). For a vector this means it must no longer be the owner of the internal buffer that you are now using in your buffer.

The simplest way to achieve this goal is to set up the object in a valid (but very cheap to achieve state) and then swap the current object with the destination object.

Vector Move Semantics Implementation
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF

    // Move Constructor
    Vector(Vector&& move) noexcept
        : capacity(0)
        , length(0)
        , buffer(nullptr)
    {
        // The source object now has a nullptr/
        // This object has taken the state of the source object.
        move.swap(*this);
    }

    // Move Assignment Operator
    Vector& operator=(Vector&& move) noexcept
    {
        // In this case simply swap the source object
        // and this object around.
        move.swap(*this);
        return *this;
    }
};
```

Note I marked both move operators `noexcept`. Assuming the operations are guaranteed not to throw you should mark them as `noexcept`. If we know that certain operations are exception safe, then we can optimize resize operations and maintain the strong exception guarantee. This and some other optimizations will be documented in a subsequent post.

# Final Version <a id="VectorVersion-1"></a>

Vector Final Version
```c
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Covered in Part 2
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            new (buffer + length) T(value);
            ++length;
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                // Covered in Part 2
            }
        }
};
```
# Summary
This article has shown how to handle the basic resource management required by a vector. It has covered several important principles for C++ programmers.

* Separation Of Concerns
* Rule of Zero
* Rule of Three
* Rule of Five
* Default compiler generated methods
* Shallow Copy Problem
* Placement New
* Exception Guarantees

# Sources  <a id="Sources"></a>
Looking at [CodeReview.stackexchange.com](https://CodeReview.stackexchange.com); reimplementing the vector class is a common goal for a first project.

* 2011/Nov/07 - [Mathematical Vector2 class implementation](https://codereview.stackexchange.com/q/5856/507)*
* 2012/May/21 - [C++ Vector2 Class Review](https://codereview.stackexchange.com/q/11934/507)*
* 2012/Aug/17 - [Templated Matrix class](https://codereview.stackexchange.com/q/14784/507)
* 2013/Jan/07 - [Vector implementation - simple replacement](https://codereview.stackexchange.com/q/20243/507)
* 2013/May/25 - [Review of 2d Vector class](https://codereview.stackexchange.com/q/26608/507)
* 2013/Jun/19 - [Simple matrix class](https://codereview.stackexchange.com/q/27573/507)
* 2013/Jun/21 - [Matrix and Vector4 classes](https://codereview.stackexchange.com/q/27625/507)*
* 2013/Jun/25 - [Simple matrix class - version 2](https://codereview.stackexchange.com/q/27752/507)*
* 2013/Aug/03 - [Template vector class](https://codereview.stackexchange.com/q/29331/507)*
* 2014/Feb/20 - [C++ vector implementation](https://codereview.stackexchange.com/q/42297/507)
* 2014/Mar/01 - [Reimplementation of C++ vector](https://codereview.stackexchange.com/q/43136/507)
* 2014/Mar/12 - [3D mathematical vector class](https://codereview.stackexchange.com/q/44167/507)
* 2014/May/17 - [Creating a custom Vector class](https://codereview.stackexchange.com/q/50975/507)
* 2014/Aug/19 - [STL vector implementation](https://codereview.stackexchange.com/q/60484/507)
* 2014/Sep/12 - [C++ 3D Vector Implementation](https://codereview.stackexchange.com/a/62774/507)
* 2014/Sep/26 - [Custom mathematical vector class](https://codereview.stackexchange.com/q/63970/507)
* 2014/Oct/19 - [Vector backed by memory pages](https://codereview.stackexchange.com/q/67209/507)
* 2014/Oct/31 - [Custom matrix class](https://codereview.stackexchange.com/q/68486/507)
* 2014/Nov/25 - [Vector/matrix class](https://codereview.stackexchange.com/q/70815/507)
* 2014/Dec/22 - [Vector implementation](https://codereview.stackexchange.com/q/74521/507)
* 2015/Feb/17 - [Mathematical matrices implementation](https://codereview.stackexchange.com/q/81751/507)
* 2015/Mar/01 - [C++ vector implementation errors](https://codereview.stackexchange.com/q/82906/507)
* 2015/Jun/20 - [Implementation of std::vector class](https://codereview.stackexchange.com/q/94211/507)
* 2015/Jul/08 - [Second implementation of std::vector](https://codereview.stackexchange.com/q/96253/507)
* 2015/Oct/17 - [Simple multi-dimensional Array class in C++11](https://codereview.stackexchange.com/q/107877/507)
* 2015/Oct/19 - [Creating n-dimensional mathematical vector classes through inheritance](https://codereview.stackexchange.com/q/108072/507)
* 2015/Oct/20 - [Implementation of Vector in C++](https://codereview.stackexchange.com/q/108140/507)
* 2015/Oct/23 - [Simple multi-dimensional Array class in C++11 - follow-up](https://codereview.stackexchange.com/q/108558/507)
* 2015/Nov/18 - [Custom vector that uses less memory than std::vector](https://codereview.stackexchange.com/q/111114/507)
* 2015/Nov/24 - [Attempt at templates by creating a class for N-dimensional mathematical vectors](https://codereview.stackexchange.com/q/111746/507)
* 2016/Jan/10 - [Vector Implementation C++](https://codereview.stackexchange.com/q/116377/507)


C++ By Example. The Vector - Part 1. A lot of new developers to C++ attempt to build a `Vector` like container as a learning processes. Getting a simple version of this working for POD types (like int) is not that complicated. The next step in getting this working for arbitrary data types takes a significant leap forward in thinking in C++ especially when you start looking at efficiency and exception safety. This set of five articles looks at building an efficient `Vector` implementation. I show some of the common mistakes and explain why and how to resolve the problems.

Vector - Resource Management Allocation


In the previous article I went over basic allocation for a `Vector` like class. In this article I want to put some detail around the copy assignment operator and resizing the underlying `Vector`. Unlike the other methods previously discussed these methods have to deal with both construction and destruction of elements and the potential of exceptions interrupting the processes. The goal is to provide exception safe methods that provide the strong exception guarantee for the object and do not leak resources.

# Copy Assignment
## First Try
This is a very common first attempt at a copy constructor.
It simply calls the destructor on all elements currently in the object. Then uses the existing `push_back()` method to copy member elements from the source object, thus allowing the object to automatically resize if required.

Copy Assignment (Try 1)
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // First we have to destroy all the current elements.
        for(int loop = 0; loop < length; ++loop)
        {
            // Destroy in reverse order
            buffer[length - 1 - loop].~T();
        }
        // Now the buffer is empty so reset size to zero.
        length = 0;

        // Now copy all the elements from the source into this object
        for(int loop = 0; loop < copy.length; ++loop)
        {
            push_back(copy.buffer[loop]);
        }
        return *this;
    }
};
```

## Strong Exception Guarantee
The obvious problems about efficiency when a resize is required is a minor issue here. The real problem is that this does not provide the strong exception guarantee. If any of the constructors/destructor throw then the object will be left in an inconsistent state with no way to restore the original state. The strong exception guarantee basically means that the operation works or does not change the state of the object. The easiest technique to achieve this is to create a copy in a new temporary buffer that can be thrown away if things go wrong (leaving the current object untouched). If the copy succeeds then we use it and throw away the original data.

Copy Assignment (Try 2)
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // Part-1 Create a copy of the src object.
        std::size_t tmpCap    = copy.length;
        std::size_t tmpSize   = 0;
        T*          tmpBuffer = static_cast<T*>(::operator new(sizeof(T) * tmpCap));

        // Now copy all the elements from the source into the temporary object
        for(int loop = 0; loop < copy.length; ++loop)
        {
            new (tmpBuffer + tmpSize) T(copy.buffer[loop]);
            ++tmpSize;
        }

        // Part-2 Swap the state
        // We have successfully created the new version of this object
        // So swap the temporary and object states.
        std::swap(tmpCap,    capacity);
        std::swap(tmpSize,   length);
        std::swap(tmpBuffer, buffer);

        // Part-3 Destroy the old state.
        // Now we have to delete the old state.
        // If this fails it does not matter the state of the object is consistent
        for(int loop = 0; loop < tmpSize; ++loop)
        {
            tmpBuffer[tmpSize - 1 - loop].~T();
        }
        ::operator delete(tmpBuffer);
        return *this;
    }
};
```

## Copy and Swap
This second attempt is a better attempt. But it still leaks if an exception is throw. But before we add exception handling, let us take a closer look at the three sections of the assignment operator.

Part-1 looks exactly like the copy constructor of Vector.

Copy Assignment Part 1
```c
        std::size_t tmpCap    = copy.length;
        std::size_t tmpSize   = 0;
        T*          tmpBuffer = static_cast<T*>(::operator new(sizeof(T) * tmpCap));

        // Now copy all the elements from the source into the temporary object
        for(int loop = 0; loop < copy.length; ++loop)
        {
            // This looks exactly like push_back()
            new (tmpBuffer + tmpSize) T(copy.buffer[loop]);
            ++tmpSize;
        }
```

Part-3 looks exactly like destructor of Vector.

Copy Assignment Part 3
```c
        // Now we have to delete the old state.
        for(int loop = 0; loop < tmpSize; ++loop)
        {
            tmpBuffer[tmpSize - 1 - loop].~T();
        }
        ::operator delete(tmpBuffer);
```

Using these two observations we have a rewrite of the copy assignment operator.

Copy Assignment (Try 3)
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // Part-1 Create a copy
        Vector  tmp(copy);

        // Part-2 Swap the state
        std::swap(tmp.capacity, capacity);
        std::swap(tmp.length,   length);
        std::swap(tmp.buffer,   buffer);

        return *this;
        // Part-3 Destructor called at end of scope.
        // No actual code required here.
    }
};
```
## [Copy And Swap Idiom](https://stackoverflow.com/q/3279543/14065)

The copy and swap idiom is about dealing with replacing an object state from another object. It is very commonly used in the copy assignment operator but has application whenever state is being changed and the [strong exception guarantee](https://en.wikipedia.org/wiki/Exception_safety) is required.

The above code works perfectly. But in Part-2 the swap looks like a normal swap operation so let's use that rather than doing it manually. Also self assignment now works without the need for a test (because we are copying into a temporary). So we can remove the check for self assignment. Yes this does make the performance for self assignment worse, but it makes the normal operation even more efficient. Since the occurrence of self assignment is extremely rare I would not prematurely optimize for it but rather make the most common case the best optimized. So one final re-factor of the copy constructor leaves us with this.

Copy Assignment (Try 4)
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        Vector  tmp(copy);
        tmp.swap(*this);
        return *this;
    }
    void swap(Vector& other) noexcept
    {
        std::swap(other.capacity, capacity);
        std::swap(other.length,   length);
        std::swap(other.buffer,   buffer);
    }
};
```

# Resizing Underlying buffer

When pushing data into the array we need to verify that capacity has not been exceeded. If it has then we need to allocate more capacity then copy the current content into the new buffer and destroy the old buffer after calling the destructor on all elements.

## Using Copy and Swap
This operation is exceedingly similar to the description of the copy assignment operator. As a result the best solution looks very similar and uses the Copy and Swap idiom.

Vector Reallocating Buffer
```c
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    void resizeIfRequire()
    {
        if (length == capacity)
        {
            // Create a temporary object with a larger capacity.
            std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
            Vector<T>  tmpBuffer(newCapacity);

            // Copy the state of this object into the new object.
            std::for_each(buffer, buffer + length, [&tmpBuffer](T const& item){tmpBuffer.push_back(item);});

            // All the work has been successfully done. So swap
            // the state of the temporary and the current object.
            tmpBuffer.swap(*this);

            // The temporary object goes out of scope here and
            // tidies up the state that is no longer needed.
        }
    }
};
```

# Final Version <a id="VectorVersion-2"></a>

Vector Final Version
```c
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);
            std::for_each(buffer, buffer + length, [&tmpBuffer](T const& v){tmpBuffer.pushBackInternal(v);});

            tmpBuffer.swap(*this);
        }
};
```

# Summary
This article has gone over the design of the Copy and Swap idiom and shown how it is used in the Copy Assignment Operator and the resize operation.

* Separation Of Concerns
* Copy and Swap Idiom
* Exception Gurantees


C++ By Example. The Vector Part 2. In the previous article I went over basic allocation for a `Vector` like class. In this article I want to put some detail around the copy assignment operator and resizing the underlying `Vector`. Unlike the other methods previously discussed these methods have to deal with both construction and destruction of elements and the potential of exceptions interrupting the processes. The goal is to provide exception safe methods that provide the strong exception guarantee for the object and do not leak resources.

Vector - Resource Management Copy Swap

Because resizing a vector is expensive; the `std::vector` class uses exponential growth to minimize the number of times that the vector is resized: a technique we replicate in this version. But every now and then you still need to resize the internal buffer.

In the [current version](#VectorVersion-1), resizing the vector requires allocating a new buffer and copying all the members into it. Basically we are using the copy and swap idiom to provide the strong exception guarantee (If an exception is thrown all resources are cleaned up and the object remains unchanged).

Vector Resize with Copy

```c
    void pushBackInternal(T const& value)
    {
        new (buffer + length) T(value);
        ++length;
    }

    void reserveCapacity(std::size_t newCapacity)
    {
        Vector<T>  tmpBuffer(newCapacity);
        std::for_each(buffer, buffer + length,
                      [&tmpBuffer](T const& v){tmpBuffer.pushBackInternal(v);}
                     );

        tmpBuffer.swap(*this);
    }
```


# Resize With Move Construction
Thus resizing a `Vector` can be a very expensive operation because of all the copying that can happen.

Using the move constructor rather than the copy constructor during a resize operation could potentially be much more efficient. But the move constructor mutates the original object and thus if there is a problem we need to undo the mutations to maintain the strong exception guarantee.

The first attempt at this is:

Vector Resize with Move With Exceptions
```c
void moveBackInternal(T&& value)
{
    new (buffer + length) T(std::move(value));
    ++length;
}

void reserveCapacity(std::size_t newCapacity)
{
    Vector<T>  tmpBuffer(newCapacity);
    try
    {
        std::for_each(buffer, buffer + length,
                      [&tmpBuffer](T& v){tmpBuffer.moveBackInternal(std::move(v));}
                     );
    }
    catch(...)
    {
        // If an exception is thrown you need to move the objects back
        // from the temporary buffer back to this object.
        for(int loop=0; loop < tmpBuffer.length; ++loop)
        {
            // The problem is here:
            // If the initial move can throw,
            // then trying to move any of the objects back can also throw.
            // which would leave the object in an inconsistent state.
            buffer[loop] = std::move(tmpBuffer[loop]);
        }

        // Then remember to rethrow the exception after we have fixed the state.
        throw;
    }

    tmpBuffer.swap(*this);
}
```
# Resize With NoThrow Move Construction
As the above code shows; if the type `T` can throw during its move constructor then you can't guarantee that the object gets returned to the original state (as moving the already moved elements back may cause another exception). So we cannot use the move constructor to resize the vector if the type `T` can throw during move construction.

But not all types throw when being moved. In fact it is recommended that move constructors never throw. If we can guarantee that the move constructor does not throw then we can simplify the above code considerably and still provide the strong exception guarantee.

Vector Resize with Move
```c
void reserveCapacity(std::size_t newCapacity)
{
    Vector<T>  tmpBuffer(newCapacity);
    std::for_each(buffer, buffer + length,
                  [&tmpBuffer](T& v){tmpBuffer.moveBackInternal(std::move(v));}
                 );

    tmpBuffer.swap(*this);
}
void moveBackInternal(T&& value)
{
    new (buffer + length) T(std::move(value));
    ++length;
}
```
# Resize Template Specialization
So now we have to write the code that decides at compile time which version we should use. The simplest way to do this is to use template specialization of a class using the standard class `std::is_nothrow_move_constructible<T>` to help differentiate types that have a non-throwing move constructor. This is simple enough:

Template class Specialization
```c
template<typename T, bool = std::is_nothrow_move_constructible<T>::value>
struct SimpleCopy
{
    // Define two different versions of this class.
    // The object is to copy all the elements from src to dst Vector
    // using pushBackInternal or moveBackInternal
    //
    // SimpleCopy<T, false>:        Defines a version that use pushBackInternal (copy constructor)
    //                              This is always safe to use.
    // SimpleCopy<T, true>:         Defines a version that uses moveBackInternal (move constructor)
    //                              Safe when move construction does not throw.
    //
    void operator()(Vector<T>& src, Vector<T>& dst) const;
};
template<typename T>
class Vector
{
    public:
        .....
    private:
        // We are using private methods for effeciency.
        // So these classes need to be friends.
        friend struct SimpleCopy<T, true>;
        friend struct SimpleCopy<T, false>;

        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            // Create the copier object base on the type T.
            // Note: The second parameter is automatically generated based
            //       on if the type T is move constructable with no exception.
            SimpleCopy<T>   copier;
            copier(*this, tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }
}
// Define the two different types of copier
template<typename T>
struct SimpleCopy<T, false> // false: does not have nothrow move constructor
{
    void operator()(Vector<T>& src, Vector<T>& dst) const
    {
        std::for_each(buffer, buffer + length,
                      [&dst](T const& v){dst.pushBackInternal(v);}
                     );
    }
};
template<typename T>
struct SimpleCopy<T, true> // true: has a nothrow move constructor
{
    void operator()(Vector<T>& src, Vector<T>& dst) const
    {
        std::for_each(buffer, buffer + length,
                      [&dst](T& v){dst.moveBackInternal(std::move(v));}
                     );
    }
};
```
# Resize With NoThrow SFINAE
The above technique has a couple of issues.

The type `SimpleClass` is publicly available and is a friend of `Vector<T>`. This makes it susceptible to accidentally being used (even if not explicitly documented). Unfortunately it can't be included as a member class and also be specialized.

Additionally it looks awful!!

But we can also use [SFINAE](https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error) and method overloading.

SFINAE allows us to define several versions of a method with exactly the same arguments, as long as only one of them is valid at compile time. So in the example below we define two versions of the method `SimpleCopy(Vector<T>& src, Vector<T>& dst)` but then use `std::enable_if` to make sure only one version of the function is valid at compile time.

SFINAE method overload

```c
template<typename T>
class Vector
{
    public:
        .....
    private:
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            SimpleCopy<T>(*this, tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        // Note: this defines the return type of the function.
        //       But only one has a valid member `type` thus only
        //       one of the following functions is actually valid.
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& src, Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy()(Vector<T>& src, Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }
}
```

# Final Version <a id="VectorVersion-3"></a>

Vector Final Version
```c
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }
};
```

# Summary
This article has gone over the design of resizing the internal buffer. We have covered a couple of techniques on the way:

* Move Constructor Concepts
* Template Class Specialization
* SFINAE
* std::is_nothrow_move_constructible&lt;&gt;
* std::enable_if&lt;&gt;


C++ By Example. The Vector Part 3. Because resizing a vector is expensive; the standard vector class uses exponential growth to minimize the number of times that the vector is resized; a technique we replicate in this version. But every now and then you still need to resize the internal buffer.

Vector - Resize


So now that we have used `std::is_nothrow_move_constructible` we can also look at a couple of other types available in the template utility library.

# Optimized Destruction

Since we have to manually call the destructor on all objects in the container (because we are using placement new) we can look to see if we can optimize that. The type `std::is_trivially_destructible` detects if the type is **Trivially** destructible. This basically means that there will be no side effects from the destructor (See: Section 12.4 Paragraph 5 of the standard). For types we don't need to call the destructor of the object. For the `Vector` class this means we can eliminate the call to the destructor but more importantly the loop.

Destroying Elements
```c
~Vector()
{
    // STUFF..

    // Call the destructor on all the members in reverse order
    for(int loop = 0; loop < length; ++loop)
    {
        // Note we destroy the elements in reverse order.
        buffer[length - 1 - loop].~T();
    }
}
Vector(Vector const& copy)
    : capacity(copy.length)
    , length(0)
    , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
{
    try
    {
        // STUFF 1 ...
    }
    catch(...)
    {
        // STUFF 2 ...
        // If there was an exception then destroy everything
        // that was created to make it exception safe.
        for(int loop = 0; loop < length; ++loop)
        {
            buffer[length - 1 - loop].~T();
        }
        throw;
    }
}
```

We can use the same SFINAE technique that we used in the previous article to remove the loops when the contained type is trivially destructible.

```c
~Vector()
{
    // STUFF..
    clearElements<T>();
}
Vector(Vector const& copy)
    : capacity(copy.length)
    , length(0)
    , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
{
    try
    {
        // STUFF 1 ...
    }
    catch(...)
    {
        // STUFF 2 ...
        clearElements<T>();
        throw;
    }
}

template<typename X>
typename std::enable_if<std::std::is_trivially_destructible<X>::value == false>::type
clearElements()
{
    // Call the destructor on all the members in reverse order
    for(int loop = 0; loop < length; ++loop)
    {
        // Note we destroy the elements in reverse order.
        buffer[length - 1 - loop].~T();
    }
}

template<typename X>
typename std::enable_if<std::std::is_trivially_destructible<X>::value == true>::type
clearElements()
{
    // Trivially destructible objects can be re-used without using the destructor.
}
```

# Optimized Assignment Operator
The final optimization is because resource allocation is expensive. So if we can avoid the resource allocation completely and just reuse the space we currently have.

Copy Assignment
```c
Vector& operator=(Vector const& copy)
{
    // Copy and Swap idiom
    Vector<T>  tmp(copy);
    tmp.swap(*this);
    return *this;
}
```

The copy and swap idiom is perfect for providing the strong exception guarantee in the presence of exceptions. **But** if there are no exceptions during destruction or construction then we can potentially just reuse the available memory. So if we rewrote the assignment operator with the assumption that there were no exceptions it would look like the following (Note in the real code use SFINAE to do the optimization only when necessary).

Copy the easy way
```c
Vector& operator=(Vector const& copy)
{
    // Check for self assignment
    // As we are doing work anyway.
    if (this == &copy)
    {
        return *this;
    }

    // If the length of the `copy` object exceeds
    // the capacity of the current object then
    // we have to do resource management. It costs
    // nothing extra to use the copy and swap idiom
    if (copy.length > capacity)
    {
        // Copy and Swap idiom
        Vector<T>  tmp(copy);
        tmp.swap(*this);
        return *this;
    }

    // The optimization happens here.
    // We can reuse the buffer we already have.
    clearElements<T>();     // use clearElements() as it probably does very little.
    length = 0;

    // Now add the elements to this container as cheaply as possible.
    for(int loop = 0; loop < copy.length; ++loop)
    {
        pushBackInternal(copy[loop]);
    }
    return *this;
}
```

# Final Version <a id="VectorVersion-4"></a>

The final version

Vector Final Version
```c
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                clearElements<T>();

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be reused without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                clearElements<T>();
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Copy and Swap idiom
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }
        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};
```

# Summary


C++ By Example. The Vector Part 4. We look at a couple of other types available in the template utility library that allow optimization via SFINAE.

Vector - Simple Optimizations


So the C++ standard specifies a set of requirements for containers. Very few requirements are specified in terms of containers so adhering to these exactly is not required (unless you want to be considered for the standard). But they provide an insight into what can be done with them and if you support them will allow your container to be more easily used with some features of the language and standard library. I am not going to go over all of them here (that is left as an exercise for the reader), but I will go over the ones I would expect to see in a simple implementation (the kind you would see in a university project).

For details see the [latest copy of the C++ standard](https://stackoverflow.com/a/4653479/14065).

* 23.2.1  General container requirements [container.requirements.general]
* 23.2.3  Sequence containers [sequence.reqmts]


#### Internal Types
* value&#95;type
* reference
* const&#95;reference
* iterator
* const&#95;iterator
* difference&#95;type
* size&#95;type

It is worth specifying the internal types defined here. As this allows you to abstract the implementation details of the container. This will allow you to change the implementation details without users having to change their implementation; as long as the changes still provide the same interface but the interface to reference/pointers/iterators are relatively trivial and well defined.

#### Constructors

In C++11 the `std::initializer_list<T>` was introduced. This allows a better list initialization syntax to be used with user defined types. Since this is usually defined in terms of the range based construction we should probably add both of these constructors.

* Vector(std::initializer&#95;list&lt;T&gt; const& list)
* Vector(I begin, I end)

#### Iterators
* begin()
* rbegin()
* begin() const
* rbegin() const
* cbegin() const
* crbegin() const
* end()
* rend()
* end() const
* cend() const
* rend() const
* crend() const

The iterators are relatively easy to write. They also allow the container to be used with the new range based for that was added in C++14. So this becomes another easy add.

#### Member Access
* at(&lt;index&gt;)
* at(&lt;index&gt;) const
* operator&#91;&#93;(&lt;index&gt;)
* operator&#91;&#93;(&lt;index&gt;) const
* front()
* back()
* front() const
* back() const

Member access to a vector should be very efficient. As a result normally range checks are not performed on member access, i.e. the user is expected to make sure that the method preconditions have been met before calling the method. This results in very efficient access to the members of a `Vector`. This is not normally a problem because index ranges are normally checked as part of a loop range as long as these are validated against the size of the array it does not need to be validated again.

For Loop Vector Access
```c
Vector<T>   d = getData();
for(int loop = 0; loop < d.size(); ++loop)
{
    std::cout << d[loop];   // No need for antoher range
                            // check here as we know that loop is inside the
                            // bounds of the vector d.
}
```

There is also the `at()` method which does validate the index provided before accessing the element (throwing an exception if the index is out of range).


#### Non-Mutating Member Functions
* size() const
* bool() const

To allow us to check the preconditions on the element access methods we need some functions that check the state of the object. These are provided here.

#### Mutating Member Functions
* push&#95;back(&lt;object-ref&gt;)
* push&#95;back(&lt;object-rvalue-ref&gt;)
* emplace&#95;back(&lt;args...&gt;)
* pop&#95;back()

The following members are standard easy to implement methods of `std::vector` (O(1)) that I would expect to see in every implementation.

The other mutating member functions are less trivial as they require elements to be moved around. They are not that hard but you must put some thought into the most efficient techniques to move elements (i.e. move or copy) and make sure that capacity is not exceeded by multiple inserts. As a result I would expect to see these methods only on an as needed basis.

#### Comparators
* operator== const
* operator!= const

Easy comparison operators.
Optionally you can provide the other comparison operators.


# Final
**No idea why Jackal is adding all the blank lines to my source**

Vector
```c
#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>

template<typename T>
class Vector
{
    public:
        using value_type        = T;
        using reference         = T&;
        using const_reference   = T const&;
        using pointer           = T*;
        using const_pointer     = T const*;
        using iterator          = T*;
        using const_iterator    = T const*;
        using riterator         = std::reverse_iterator<iterator>;
        using const_riterator   = std::reverse_iterator<const_iterator>;
        using difference_type   = std::ptrdiff_t;
        using size_type         = std::size_t;

    private:
        size_type       capacity;
        size_type       length;
        T*              buffer;

        struct Deleter
        {
            void operator()(T* buffer) const
            {
                ::operator delete(buffer);
            }
        };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        template<typename I>
        Vector(I begin, I end)
            : capacity(std::distance(begin, end))
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            for(auto loop = begin;loop != end; ++loop)
            {
                pushBackInternal(*loop);
            }
        }
        Vector(std::initializer_list<T> const& list)
            : Vector(std::begin(list), std::end(list))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                clearElements<T>();

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }

        // Non-Mutating functions
        size_type           size() const                        {return length;}
        bool                empty() const                       {return length == 0;}

        // Validated element access
        reference           at(size_type index)                 {validateIndex(index);return buffer[index];}
        const_reference     at(size_type index) const           {validateIndex(index);return buffer[index];}

        // Non-Validated element access
        reference           operator[](size_type index)         {return buffer[index];}
        const_reference     operator[](size_type index) const   {return buffer[index];}
        reference           front()                             {return buffer[0];}
        const_reference     front() const                       {return buffer[0];}
        reference           back()                              {return buffer[length - 1];}
        const_reference     back() const                        {return buffer[length - 1];}

        // Iterators
        iterator            begin()                             {return buffer;}
        riterator           rbegin()                            {return riterator(end());}
        const_iterator      begin() const                       {return buffer;}
        const_riterator     rbegin() const                      {return const_riterator(end());}

        iterator            end()                               {return buffer + length;}
        riterator           rend()                              {return riterator(begin());}
        const_iterator      end() const                         {return buffer + length;}
        const_riterator     rend() const                        {return const_riterator(begin());}

        const_iterator      cbegin() const                      {return begin();}
        const_riterator     crbegin() const                     {return rbegin();}
        const_iterator      cend() const                        {return end();}
        const_riterator     crend() const                       {return rend();}

        // Comparison
        bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
        bool operator==(Vector const& rhs) const
        {
            return  (size() == rhs.size())
                &&  std::equal(begin(), end(), rhs.begin());
        }

        // Mutating functions
        void push_back(value_type const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void push_back(value_type&& value)
        {
            resizeIfRequire();
            moveBackInternal(std::move(value));
        }
        template<typename... Args>
        void emplace_back(Args&&... args)
        {
            resizeIfRequire();
            emplaceBackInternal(std::move(args)...);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(size_type capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void validateIndex(size_type index) const
        {
            if (index >= length)
            {
                throw std::out_of_range("Out of Range");
            }
        }

        void resizeIfRequire()
        {
            if (length == capacity)
            {
                size_type     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(size_type newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }

        // Add new element to the end using placement new
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }
        template<typename... Args>
        void emplaceBackInternal(Args&&... args)
        {
            new (buffer + length) T(std::move(args)...);
            ++length;
        }

        // Optimizations that use SFINAE to only instantiate one
        // of two versions of a function.
        //      simpleCopy()        Moves when no exceptions are guaranteed, otherwise copies.
        //      clearElements()     When no destructor remove loop.
        //      copyAssign()        Avoid resource allocation when no exceptions guaranteed.
        //                          ie. When copying integers reuse the buffer if we can
        //                          to avoid expensive resource allocation.

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }
        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }


        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be reused without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                            &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            // This function is only used if there is no chance of an exception being
            // thrown during destruction or copy construction of the type T.


            // Quick return for self assignment.
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                // If we have enough space to copy then reuse the space we currently
                // have to avoid the need to perform an expensive resource allocation.

                clearElements<T>();     // Potentially does nothing (see above)
                                        // But if required will call the destructor of
                                        // all elements.

                // buffer now ready to get a copy of the data.
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Fallback to copy and swap if we need to more space anyway
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};
```


C++ By Example. The Vector Part 5. So the C++ standard specifies a set of requirements for containers. Very few requirements are specified in terms of containers so adhering to these exactly is not required (unless you want to be considered for the standard). But they provide an insight into what can be done with them and if you support them will allow your container to be more easily used with some features of the language and standard library. I am not going to go over all of them here (that is left as an exercise for the reader), but I will go over the ones I would expect to see in a simple implementation (the kind you would see in a university project).

Vector - The Other Stuff


So I never really considered why the resize of vector used a constant expansion of 1.5 or 2 (in some popular implementations). That was until I did my previous article Xseries ["Vector"]({{config.site}}/blog/2016/02/27/vector/) where I concentrated a lot on resource management and did a section on [resizing the vector]({{config.site}}/blog/2016/03/12/vector-resize/). Originally in the code I tried to be clever, a mistake. I used a resize value of 1.62 (an approximation of `Phi`), because I vaguely remembered reading an article that this was the optimum resize factor. When I put this out for code review it was pointed out to me that this value was too large, the optimum value must be less than or equal to `Phi` (1.6180339887) and that exceeding this limit actually made things a lot worse.

So I had to know why....

So the theory goes: You have a memory resource of size `B`. If you resize this resource by a constant factor `r` by re-allocating a new block then releasing the old block. Then if the value of `r` is smaller than or equal to `Phi` you will eventually be able to reuse memory that has previously been released; otherwise the new block of memory being allocated will always be larger than the previously released memory.

So I thought lets try that:
Test one `r > Phi`:

```
    B=10
    r=2.0

                Sum Memory      Memory      Memory Needed       Difference
                 Released     Allocated     Next Iteration
    Start            0            10              20                 20
    Resize 1        10            20              40                 30
    Resize 2        30            40              80                 50
    Resize 3        70            80             160                 90
    Resize 4       150           160             320                170
```

OK. That seems to be holding (at least in the short term). Lo lets try a smaller value.
Test two `r < Phi`:

```
    B=10
    r=1.5

                Sum Memory      Memory      Memory Needed       Difference
                 Released     Allocated     Next Iteration
    Start            0            10              15                 15
    Resize 1        10            15              22                 12
    Resize 2        25            22              33                  8
    Resize 3        47            33              48                  1
    Resize 4        80            48              72                 -8 // Reuse released memory next iteration
```

OK. That also seems to be holding. But can we show that holds for all values of B? Also this is a bit anecdotal can we actually show this relationship actually hold? Time to break out some maths (not math as my American cousins seem to insist on for the shortening of mathematics).


So the size `S` of any block after `n` resize operations will be:

<MathJaxContext>
<ThorMath content="S   = Br^n" />

Thus the size of `Released Memory` can be expressed as:

<ThorMath content="\sum_&#123;k=0&#125;^&#123;n-1&#125;\ Br^k" />

Also the size of the next block will be:

<ThorMath content="Br^&#123;n+1&#125;" />

So if the amount of `Released Memory` >= the amount required for the next block, then we can reuse the `Released Memory`.

<ThorMath content="\sum_&#123;k=0&#125;^&#123;n-1&#125;\ Br^k &gt;= Br^&#123;n+1&#125;" />

<ThorMath content="B \sum_&#123;k=0&#125;^&#123;n-1&#125;\ r^k &gt;= Br^&#123;n+1&#125;" />

<ThorMath content="\sum_&#123;k=0&#125;^&#123;n-1&#125;\ r^k &gt;= r^&#123;n+1&#125;" />

<ThorMath content="&#123;1-r^&#123;(n-1)+1&#125;\over1-r&#125; &gt;= r^&#123;n+1&#125;" />

<ThorMath content="&#123;1-r^n\over1-r&#125; &gt;= r^&#123;n+1&#125;" />

<ThorMath content="1-r^n &gt;= r^&#123;n+1&#125; (1-r)" />

<ThorMath content="1-r^n &gt;= r^&#123;n+1&#125; - r^&#123;n+2&#125;" />

<ThorMath content="1 + r^&#123;n+2&#125; - r^&#123;n+1&#125; - r^n &gt;= 0" />

<ThorMath content="1 + r^n (r^2 - r - 1) &gt;= 0" />

This is were my maths broke down. So after talking to some smart people. They noticed that:

<ThorMath content="\sqrt&#123;(r^2 - r - 1)&#125; . when . r = \Phi" />

We find that the first root of the equation is 1. The second root of the equation depends on `n`, as `n` tends to `infinity` the other root tends towards `Phi`. From this we can infer the following:

<ThorMath content="1 < r < = \Phi" />
</MathJaxContext>

Thus if `r` remains in the above range then the above theory holds.



So why is the constant resize factor of the array 1.5 or 2?

Memory Resizing


Building a simple client/server application is the common first internet based applications developers attempt. These applications are built on top of the socket communication library, but socket programming in C++ is not obvious as there are no standard libraries and thus you have to fall back to the C API. The closest "standardish" sort of thing we have is [Boost.asio](https://www.boost.org/doc/libs/1_60_0/doc/html/boost_asio/overview.html) which is at the other end of the spectrum in terms of API and involves a cognitive leap to understand what is happening underneath (or you can just trust the library maintainers). The other alternative is [libcurl](https://curl.haxx.se/libcurl/c/); the "easy curl" layer is an abstraction of the `socket()` API, while the "multi curl" layer is an abstraction of the `pselect()` API that allows multiple sockets to be handled in a single thread.

I am writing a series of articles that start with a basic C++ client/server application and walk through building a C++ communication library. During this processes I will be using examples from [codereview.stackexchange.com](https://codereview.stackexchange.com) to illustrate common mistakes and try to show how to write the code correctly (This will also be a learning exercise for me so please let me know if you spot a mistake).

Currently the plan is to write the following articles:

{/* Server listening for program sockets */}
* Client/Server C
* Client/Server C Read/Write
* Client/Server C++ Wrapper
* Mult-Threaded Server
* Non-Blocking Socket
* Co-Routines


## Client/Server C++ Basic Version

The minimum example of a working Client/Server application in C++:
The full working version is [here](https://github.com/Loki-Astari/Examples/tree/master/Version1)

[C Server](https://github.com/Loki-Astari/Examples/blob/master/Version1/server.cpp)
```c
#include <netinet/in.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define SERVER_BUFFER_SIZE      1024

int main()
{
    int socketId = socket(PF_INET, SOCK_STREAM, 0);

    struct sockaddr_in serverAddr;
    bzero((char*)&serverAddr, sizeof(serverAddr));
    serverAddr.sin_family       = AF_INET;
    serverAddr.sin_port         = htons(8080);
    serverAddr.sin_addr.s_addr  = INADDR_ANY;
    bind(socketId, (struct sockaddr *) &serverAddr, sizeof(serverAddr));

    listen(socketId, 5);

    int                         finished    = 0;
    while(!finished)
    {
        struct  sockaddr_storage    serverStorage;
        socklen_t                   addr_size   = sizeof serverStorage;
        int newSocket = accept(socketId, (struct sockaddr*)&serverStorage, &addr_size);

        char        buffer[SERVER_BUFFER_SIZE];
        int         get = read(newSocket, buffer, SERVER_BUFFER_SIZE - 1);

        buffer[get] = '\0';
        fprintf(stdout, "%s\n", buffer);

        write(newSocket, "OK", 2);

        fprintf(stdout, "Message Complete\n");

        close(newSocket);
    }
    close(socketId);
}
```

[C Client](https://github.com/Loki-Astari/Examples/blob/master/Version1/client.cpp)
```c
#include <arpa/inet.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define CLIENT_BUFFER_SIZE     1024

int main(int argc, char* argv[])
{
    if (argc != 3)
    {
        fprintf(stderr, "Usage: client <host> <Message>\n");
        exit(1);
    }

    int socketId = socket(PF_INET, SOCK_STREAM, 0);

    struct sockaddr_in serverAddr;
    socklen_t addrSize = sizeof(serverAddr);
    bzero((char*)&serverAddr, sizeof(serverAddr));
    serverAddr.sin_family       = AF_INET;
    serverAddr.sin_port         = htons(8080);
    serverAddr.sin_addr.s_addr  = inet_addr(argv[1]);
    connect(socketId, (struct sockaddr*)&serverAddr, addrSize);

    write(socketId, argv[2], strlen(argv[2]));

    shutdown(socketId, SHUT_WR);

    char    buffer[CLIENT_BUFFER_SIZE];
    size_t  get = read(socketId, buffer, CLIENT_BUFFER_SIZE - 1);

    buffer[get] = '\0';
    fprintf(stdout, "%s %s\n", "Response from server", buffer);

    close(socketId);
}
```

This version of the Client/Server actually works (a lot of the time) but obviously has a couple of major issues.

## Checking Error Codes
If the calls to `socket()`, `bind()`, `listen()` or `connect()` fail then we have a catastrophic error any further actions will also fail. A few of the error codes generated by these functions can potentially be recovered from but most are programming error or permission failure as a result a human readable message with application termination is an acceptable solution (at this point).

Note: When these functions don't succeed they set the global variable `errno` which can be translated into a human readable string with `strerror()`. So the simplest solution is to generate an appropriate error message for the user and terminate the application.

Socket Validation
```c
int socketId = socket(PF_INET, SOCK_STREAM, 0);
if (socketId == -1)
{
    fprintf(stderr, "Failed: socket()\n%s\n", strerror());
    exit(1);
}
```

Bind Validation
```c
if (bind(socketId, (struct sockaddr *) &serverAddr, sizeof(serverAddr)) == -1)
{
    fprintf(stderr, "Failed: bind()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}
```

Listen Validation
```c
if (listen(socketId, 5) == -1)
{
    fprintf(stderr, "Failed: connect()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}
```

Connect Validation
```c
if (connect(socketId, (struct sockaddr*)&serverAddr, addrSize) == -1)
{
    fprintf(stderr, "Failed: connect()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}
```

# Summary

The basic socket programs are relatively trivial. But this version 1 has some obvious flaws the major one being checking error states (which a lot of beginners forget in their first version). The next article will look into some more details about read and write operations on the socket.

# Inspiration for Article

* 2012-Jul-09 [Two-way communication in TCP: server-client implementation](https://codereview.stackexchange.com/q/13461/507)
* 2012-Jul-23 [Stupidly simple TCP client/server](https://codereview.stackexchange.com/q/13933/507)
* 2013-May-28 [How is this for a “Hello World” of socket programming?](https://codereview.stackexchange.com/q/26683/507)
* 2013-Sep-06 [Extract location from HTTP socket](https://codereview.stackexchange.com/q/30852/507)
* 2014-Mar-10 [Client/server implementation in C (sending data/files)](https://codereview.stackexchange.com/q/43914/507)



Socket Programming in C


## Checking read/write success

The `read()` and `write()` command can fail in a couple of ways but can also succeed without reading/writing all the data, a common mistake is not to check the amount of data read/written from/to a stream. Interestingly not all error condition are fatal and reading/writing can potentially be resumed after an error.

## Read
To understand if you have read all the information that is available on a stream you need to define a communication protocol (like HTTP). For the first version of this server the protocol is very simple. Messages are passed as strings (not null terminated) and the end of the message is marked by closing the write stream. Thus a client can send one message and receive one reply with each connection it makes.

getMessage()
```c
/*
 * Returns:     0   EOM reached.
 *                  The message is complete. There is no more data to be read.
 *              >0  Message data has been read (and a null terminator added).
 *                  The value is the number of bytes read from the stream
 *                  You should call getMessage() again to get the next section of the message.
 *                  Note: the message is terminated when 0 is returned.
 *              -1  An error occured.
 */
int getMessage(int socketId, char* buffer, std::ssize_t size)
{
    std::ssize_t     dataRead = 0;
    std::ssize_t     dataMax  = size - 1;

    while(dataRead < dataMax)
    {
        ssize_t get = read(socketId, buffer + dataRead, size - dataRead);
        if (get == -1)
        {
            return -1;
        }
        if (get == 0)
        {
            break;
        }
        dataRead += get;
    }
    buffer[dataRead] = '\0';
    return dataRead;
}
```

### Read Errors
This initial version treats all `read()` errors as unrecoverable and `getMessage()` return an error state. But not all error codes need to result in a failure. So in this section I will go through some of the error codes and give some potentially actions. In a subsequent articles I may revise these actions as we cover more complex ways of interacting with sockets.


The following errors are the result of programming bugs and should not happen in production.

    [EBADF]            fildes is not a valid file or socket descriptor open for reading.
    [EFAULT]           Buf points outside the allocated address space.
    [EINVAL]           The pointer associated with fildes was negative.
    [ENXIO]            A requested action cannot be performed by the device.

If they do happen in production there is no way to correct for them pragmatically because the error has happened in another part of the code unassociated with this function.

One could argue that because these should never happen the application can abort, but for now we will settle for the read operation aborting with an error code. If we wrap this in a C++ class to control the state of the socket then exceptions may be more appropriate and we will look into that approach in a subsequent article.

The following errors are potentially recoverable from.
{/* https://stackoverflow.com/questions/8471577/linux-tcp-connect-failure-with-etimedout */}

    [EIO]              An I/O error occurred while reading from the file system.
    [ENOBUFS]          An attempt to allocate a memory buffer fails.
    [ENOMEM]           Insufficient memory is available.
    [ETIMEDOUT]        A transmission timeout occurs during a read attempt on a socket.

But in reality recovering from them within the context of a read operation is not practical (you need to recover from these operations at a point were resource are controlled or user interaction is possible). So for now we will abort the read operation with an error code (we will revisit this in a later article).

The following error codes means that no more data will be available because the connection has been interrupted.
{/* https://stackoverflow.com/questions/2974021/what-does-econnreset-mean-in-the-context-of-an-af-local-socket */}
{/* https://stackoverflow.com/questions/900042/what-causes-the-enotconn-error */}

    [ECONNRESET]       The connection is closed by the peer during a read attempt on a socket.
    [ENOTCONN]         A read is attempted on an unconnected socket.

How the application reacts to a broken connection depends on the communication protocol. For the simple protocol defined above we can return any data that has been retrieved from the socket and then indicating to the calling code that we have reached the end of the message (we will revisit this in a later article). This is probably the most iffy decision in handling error codes and returning an error code could be more appropriate but I want to illustrate that we can potentially continue depending on the situation.

The following error codes are recoverable from.

    [EAGAIN]           The file was marked for non-blocking I/O, and no data were ready to be read.

These error codes are generated when you have a non-blocking stream. In a future article we will discuss how to take advantage of non-blocking streams.

    [EINTR]            A read from a slow device was interrupted before any data arrived by the delivery of a signal.

The exact action that you take will depend on your application (like doing some useful work) but for our simple application simply re-trying the read operation will be the standard action. Again we will come back to this, but taking advantage of timeouts will require a slightly more sophisticated approach rather than using the sockets API directly.

> **EINTR:**
> An important note about signals. There are a lot of signals that are non lethal and will result in this EINTR error code. But one should note that lethal signals like SIGINT by default will kill the application and thus will not cause this error code (as the call to read() will never return).
>
>But you can override the SIGINT signal handler and a allow your application to continue and at this point your read operation will receive this error. How your code interacts with signals like SIGINT is beyond the scope of this article and it will be discussed just like other signals.

getMessage() Improved
```c
/*
 * Returns:     0   EOM reached.
 *                  There is no data in the buffer.
 *              >0  Message data has been read.
 *                  If the buffer is full then it is not null terminated.
 *                  If the buffer is partially full then it is null terminated
 *                  and the next call to get getMessage() will return 0.
 *              <0  An error occured.
 */
int getMessage(int socketId, char* buffer, std::ssize_t size)
{
    std::ssize_t     dataRead = 0;
    std::ssize_t     dataMax  = size - 1;

    while(dataRead < dataMax)
    {
        ssize_t get = read(socketId, buffer + dataRead, size - dataRead);
        if (get == -1)
        {
            switch(errno)
            {
                case EBADF:
                case EFAULT:
                case EINVAL:
                case ENXIO:
                    // Fatal error. Programming bug
                    return -3;
                case EIO:
                case ENOBUFS:
                case ENOMEM:
                    // Resource aquisition failure or device error
                    // Can't recover from here so indicate failure
                    // and exit
                    return -2;
                case ETIMEDOUT:
                case EAGAIN:
                case EINTR:
                    // Temporrary error.
                    // Simply retry the read.
                    continue;
                case ECONNRESET:
                case ENOTCONN:
                    // Connection broken.
                    // Return the data we have available and exit
                    // as if the connection was closed correctly.
                    get = 0;
                    break;
                default:
                    return -1;
            }
        }
        if (get == 0)
        {
            break;
        }
        dataRead += get;
    }
    buffer[dataRead] = '\0';
    return dataRead;
}
```

## Write
The `write()` has exactly the same scenario as `read()`.

The following errors are the reuls of programming bugs and should not happen in production.

     [EINVAL]           The pointer associated with fildes is negative.
     [EBADF]            fildes is not a valid file descriptor open for writing.
     [ECONNRESET]       A write is attempted on a socket that is not connected.
     [ENXIO]            A request is made of a nonexistent device, or the request is outside the capabilities of the device.
     [EPIPE]            An attempt is made to write to a socket of type SOCK_STREAM that is not connected to a peer socket.

The following errors are potentially recoverable bugs. Though recovering from them requires some form of awarness of the context that is not provided at the read level. So we must generate an error to stop reading and allow the caller to sort out the problem.

     [EDQUOT]           The user's quota of disk blocks on the file system containing the file is exhausted.
     [EFBIG]            An attempt is made to write a file that exceeds the process's file size limit or the maximum file size.
     [EIO]              An I/O error occurs while reading from or writing to the file system.
     [ENETDOWN]         A write is attempted on a socket and the local network interface used to reach the destination is down.
     [ENETUNREACH]      A write is attempted on a socket and no route to the network is present.
     [ENOSPC]           There is no free space remaining on the file system containing the file.


The following error codes are recoverable from and we covered them above in the section on `read()`.

     [EAGAIN]           The file is marked for non-blocking I/O, and no data could be written immediately.
     [EINTR]            A signal interrupts the write before it could be completed.

The resulting put function then looks like this.

putMessage() Improved
```c
/*
 * Returns:
 *              >0  Indicates success and the number of bytes written.
 *              <0  Indicates failure.
 */
int putMessage(int socketId, char* buffer, ssize_t size)
{
    ssize_t     dataWritten = 0;

    while(dataWritten < size)
    {
        ssize_t put = write(socketId, buffer + dataWritten, size - dataWritten);
        if (put == -1)
        {
            switch(errno)
            {
                case EINVAL:
                case EBADF:
                case ECONNRESET:
                case ENXIO:
                case EPIPE:
                    // Fatal error. Programming bug
                    return -3;
                case EDQUOT:
                case EFBIG:
                case EIO:
                case ENETDOWN:
                case ENETUNREACH:
                case ENOSPC:
                    // Resource aquisition failure or device error
                    // Can't recover from here so indicate failure
                    // and exit
                    return -2;
                case EAGAIN:
                case EINTR:
                    // Temporrary error.
                    // Simply retry the read.
                    continue;
                default:
                    return -1;
            }
        }
        dataWritten += put;
    }
    return dataWritten;
}
```

# Summary

This article has shown the most important error that people skip over when reading and writing to a socket: **Not all the data was transported at the same time**. The read and write command may only read/write a portion of the data that you wanted to send/receive and thus you must check the amount that actually was sent/received.

The next most important point is that not all error codes are fatal (most people actually check these) **but** an interrupt (EINTR) can be relatively common and you can continue reading after it has happened.
# Inspiration

* 2015-Jun-25 [Impromptu TCP sender/receiver](https://codereview.stackexchange.com/q/94608/507)
* 2015-Jul-03 [Raw Text TCP Client v3](https://codereview.stackexchange.com/q/95638/507)
* 2015-Dec-20 [Server / client desynchronisation of messages ](https://codereview.stackexchange.com/q/114551/507)




Socket Read/Write

The last two articles examined the "C Socket" interface that is provided by OS. In this article I wrap this functionality in a very simple C++ class to provide guaranteed closing and apply a consistent exception strategy. The first step is to rewrite the client/server code with all the low level socket code removed. This will help identify the interface that the wrapper class needs to implement.

The client code becomes really trivial. Create a `ConnectSocket` specifying host and a port. Then use the `putMessage()` and `getMessage()` to communicate with the server. Note: I am continuing to use the trivial protocol that was defined in the last article: `putMessage()` writes a string to the socket then closes the connection; `getMessage()` reads a socket until it is closed by the other end (I will cover more sophisticated protocols in a subsequent article).

[client.cpp](https://github.com/Loki-Astari/Examples/blob/master/Version2/client.cpp)
```c
ConnectSocket    connect("localhost", 8080);          // Connect to a server
ProtocolSimple   connectSimple(connect);              // Knows how to send/recv a message over a socket
connectSimple.sendMessage("", "A test message going to the server");

std::string message;
connectSimple.recvMessage(message);
std::cout << message << "\n";
```


For the server end this nearly as trivial as the client. Create a `ServerSocket` and wait for incoming connections from clients. When we get a connection we return a `SocketData` object. The reason for returning a new Socket like object is that this mimics the behavior of the underlying `::accept()` call which opens a new port for the client to interact with the server on. The additional benefit of separating this from the `ServerSocket` is that a subsequent version may allow multiple connections and we want to be able to interact with each connection independently without sharing state, potentially across threads, so modelling it with an object makes sense in an OO world.

[server.cpp](https://github.com/Loki-Astari/Examples/blob/master/Version2/server.cpp)
```c
ServerSocket   server(8080);                          // Create a lisening connection
while(true)
{
    DataSocket      accept  = server.accept();            // Wait for a clinet to connect
    ProtocolSimple  acceptSimple(accept);                 // Knows how to send/recv a message over a socket

    std::string message;
    acceptSimple.recvMessage(message);
    std::cout << message << "\n";

    acceptSimple.sendMessage("", "OK");
}
```

Surprisingly this actually gives us three types of socket interface (not the two most people expect).

* The ServerSocket class has no ability to read/write just accept connections
* The ConnectSocket class connects and can be used to read/write
* The DataSocket class is an already connected socket that can be used to read/write

Since a socket is a resource that we don't want duplicated. So this is a resource that can be moved but not copied.

This lets me to define a very simple interface like this:

[Socket.h](https://github.com/Loki-Astari/Examples/blob/master/Version2/Socket.h)
```c
// An RAII base class for handling sockets.
// Socket is movable but not copyable.
class BaseSocket
{
    int     socketId;
    protected:
        // Designed to be a base class not used used directly.
        BaseSocket(int socketId);
        int getSocketId() const {return socketId;}
    public:
        ~BaseSocket();

        // Moveable but not Copyable
        BaseSocket(BaseSocket&& move)               noexcept;
        BaseSocket& operator=(BaseSocket&& move)    noexcept;
        void swap(BaseSocket& other)                noexcept;
        BaseSocket(BaseSocket const&)               = delete;
        BaseSocket& operator=(BaseSocket const&)    = delete;

        // User can manually call close
        void close();
};

// A class that can read/write to a socket
class DataSocket: public BaseSocket
{
    public:
        DataSocket(int socketId);

        bool getMessage(std::string& message);
        void putMessage(std::string const& message);
        void putMessageClose();
};

// A class the conects to a remote machine
// Allows read/write accesses to the remote machine
class ConnectSocket: public DataSocket
{
    public:
        ConnectSocket(std::string const& host, int port);
};

// A server socket that listens on a port for a connection
class ServerSocket: public BaseSocket
{
    public:
        ServerSocket(int port);

        // An accepts waits for a connection and returns a socket
        // object that can be used by the client for communication
        DataSocket accept();
};
```
Taking the existing code and wrapping this interface around it becomes trivial. The code full code is provided [here](https://github.com/Loki-Astari/Examples/tree/master/Version2).

In the previous article I talked about the different types of errors that could be generated by read/write. In the following code I take this a step further. Since the code is wrapped inside a class and thus can control the socket resources more cleanly it feels more natural to use exceptions rather than error codes, consequentially error codes are not leaked across any public API boundary.

1. domain_error
    * This is caused by an error that theoretically can not happen (since we have full control of the class). If this type of error occurs there is a bug in the socket code or there has been massive data corruption. Consequently you should not be trying to catch these type of exception as there is a fundamental bug in the code. It is better to let the application exit as it is likely there is substantial corruption of any data.
1. logic_error
    * This is caused by an error that theoretically can not happen if the class is used correctly. This means that calling code has some form of logic error. It is caused by calling any method on a socket object that was previously closed or moved. Again this type of error should not be caught (but can be). You should try and remove all potential for this type of error by good unit tests.
1. runtime_error:
    * This is caused by an unlikely situation that can not be handled by the Socket code. This type of error requires a broader context to be resolved. As result the socket code will throw an exception that the user can catch and potentially correct from.




C++ Wrapper for Socket


In the previous articles I have used a very simplistic protocol. In real world situations this simple protocol is not sufficient. To provide a more robust connection between client and server a communications protocol is required so that we can validate messages are sent correctly and generate appropriate responses that can also be validated.

Designing a communication protocol is a non trivial task and personally I would look for an existing protocol that matches your use case rather than trying to create protocol from scratch.

#### Example Protocols
* HTTP&#x003A; &nbsp;https://tools.ietf.org/html/rfc2616.txt
* IRC&#x003A; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;https://tools.ietf.org/html/rfc1490.txt

Rather than go through all the different protocols I am simply going to pick the HTTP(S) protocol and use that for further discussion. HTTP(S) is relatively well known; It is simple to implement the basics; There are well known server implementations that support it; There are well known client libraries that can be used in application development.

#### Example HTTP(S) servers
* [Apache](https://httpd.apache.org/)
* [nginx](https://nginx.org/en/)
* [Node.js](https://nodejs.org/en/about/)

#### Client Side HTTP Libraries
* [LibCurl](https://curl.haxx.se/libcurl/c/)
* [Libwww](https://www.w3.org/Library/User/Using/)
* [HttpFetch](https://http-fetcher.sourceforge.net/API/index.html)


## HTTP(S)
Basically HTTP(S) defines two object. A request object is sent from the client to the server and response object is sent back as a result of a request. The only difference between the two is the start-line. Both HTTP objects can be broken down into three pieces.

1. Start-Line
2. Header-Section
3. Body

### Start-Line

For a request object this is:
<table><tbody>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Method:</td><td>HEAD/GET/PUT/POST/DELETE</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Space:</td><td>One Space character</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>URL:</td><td>Identification of the object/service needed</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Space:</td><td>One Space character</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>HTTP-Version:</td><td>Usually HTTP/1.1</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>CR/LF:</td><td>Literally '\r\n'</td></tr>
</tbody></table>

#### Example:
```
GET https://google.com/maps?id=456 HTTP/1.1\r\n
```

For a response object this is:
<table><tbody>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>HTTP-Version:</td><td>Usually HTTP/1.1</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Space:</td><td>One Space character</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Response Code:</td><td><a href="https://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html">100->599</a></td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Space:</td><td>One Space character</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Human Readable Response:</td><td>Human readable explanation of the response code</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>CR/LF:</td><td>Literally '\r\n'</td></tr>
</tbody></table>

#### Example:
```
HTTP/1.1 200 OK\r\n
```

### Header-Section

This is a set of key/value pairs one per line separated by a colon. Each Line is terminated by CR/LF and the end of the header section is marked by an empty line.

<table><tbody>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Key:</td><td>A text string representing the keys.</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Colon:</td><td>A single colon (note: some implementations are lax and insert a space before the colon).</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Space:</td><td>One Space character (note: some implementations are lax and more then one space may be present)</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>Value:</td><td>A set of characters that does not include CR or LF.</td></tr>
<tr><td>&#8226;&nbsp;</td><td style={{width:'300px'}}>CR/LF:</td><td>Literally '\r\n'</td></tr>
</tbody></table>

#### Example
```
Content-Length: 42\r\n
Content-Type: text/text\r\n
\r\n
```

### Body

The payload of the object should be in the body. Its size is defined by the headers defined in [rfc-2616 section 4.4 Message Length](https://tools.ietf.org/html/rfc2616#section-4.4).

### Required Headers

According to the rfc(s) [7230](https://tools.ietf.org/html/rfc7230), [7231](https://tools.ietf.org/html/rfc7231), [7232](https://tools.ietf.org/html/rfc7232), [7233](https://tools.ietf.org/html/rfc7233), [7234](https://tools.ietf.org/html/rfc7234) or [7235](https://tools.ietf.org/html/rfc7235) there are no header fields there are actually required header fields.

#### Request Object
But real world implementations need some headers to work efficiently, so you probably should send the following headers when making a request to a server:

* [Content-Type](https://tools.ietf.org/html/rfc7231#section-3.1.1.5):
* [Content-Length](https://tools.ietf.org/html/rfc7230#section-3.3.2):   // Or use one of the other techniques to specify length
* [Host](https://tools.ietf.org/html/rfc7230#section-5.4):

It is also polite to send the following.

* [User-Agent](https://tools.ietf.org/html/rfc7231#section-5.5.3):
* [Accept](https://tools.ietf.org/html/rfc7231#section-5.3.2):

#### Response Object
A server implementation "Must" send a `Date:` header field if it is a reasonable approximation of UTC. But that means servers may not supply the `Date:` field so you can't say it is a requirement of the standard. But you will usually see the following headers returned from a server:

* [Date](https://tools.ietf.org/html/rfc7231#section-7.1.1.2):
* [Server](https://tools.ietf.org/html/rfc7231#section-7.4.2):
* [Content-Length](https://tools.ietf.org/html/rfc7230#section-3.3.2):
* [Content-Type](https://tools.ietf.org/html/rfc7231#section-3.1.1.5):

## Implementation

Given this very basic protocol; it seems like the implementation of these requirements should be quite trivial. To be honest the implementation of creating the objects to send is relatively trivial, the hard part is reading objects from the stream in an efficiently and correctly validated manner. You can find my attempt [here](https://github.com/Loki-Astari/Examples/tree/master/Version3): It works but its 500 lines long and only covers the most basics parts of the protocol and does not do any of the hard parts (like authentication or HTTPS).

To use this protocol correctly you really need to use one of the existing libraries. Here I have re-implemented the client using libcurl.

[Client uses libcurl wrapper](https://github.com/Loki-Astari/Examples/blob/master/Version4/client.cpp)
```c
int main(int argc, char* argv[])
{
    namespace Sock = ThorsAnvil::Socket;
    if (argc != 3)
    {
        std::cerr << "Usage: client <host> <Message>\n";
        std::exit(1);
    }

    Sock::CurlGlobal    curlInit;
    Sock::CurlPost      connect(argv[1], 8080);

    connect.sendMessage("/message", argv[2]);

    std::string message;
    connect.recvMessage(message);
    std::cout << message << "\n";
}
```


[libCurl simple wrapper](https://github.com/Loki-Astari/Examples/blob/master/Version4/client.cpp)
```c
#include "Utility.h"
#include <curl/curl.h>
#include <sstream>
#include <iostream>
#include <cstdlib>

namespace ThorsAnvil
{
    namespace Socket
    {

class CurlGlobal
{
    public:
        CurlGlobal()
        {
            if (curl_global_init(CURL_GLOBAL_ALL) != 0)
            {
                throw std::runtime_error(buildErrorMessage("CurlGlobal::", __func__, ": curl_global_init: fail"));
            }
        }
        ~CurlGlobal()
        {
            curl_global_cleanup();
        }
};

extern "C" size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata);

enum RequestType {Get, Head, Put, Post, Delete};
class CurlConnector
{
    CURL*       curl;
    std::string host;
    int         port;
    std::string response;

    friend size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata);
    std::size_t getData(char *ptr, size_t size)
    {
        response.append(ptr, size);
        return size;
    }
    template<typename Param, typename... Args>
    void curlSetOptionWrapper(CURLoption option, Param parameter, Args... errorMessage)
    {
        CURLcode res;
        if ((res = curl_easy_setopt(curl, option, parameter)) != CURLE_OK)
        {
            throw std::runtime_error(buildErrorMessage(errorMessage..., curl_easy_strerror(res)));
        }
    }

    public:
        CurlConnector(std::string const& host, int port)
            : curl(curl_easy_init( ))
            , host(host)
            , port(port)
        {
            if (curl == NULL)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_init: fail"));
            }
        }
        ~CurlConnector()
        {
            curl_easy_cleanup(curl);
        }
        CurlConnector(CurlConnector&)               = delete;
        CurlConnector& operator=(CurlConnector&)    = delete;
        CurlConnector(CurlConnector&& rhs) noexcept
            : curl(nullptr)
        {
            rhs.swap(*this);
        }
        CurlConnector& operator=(CurlConnector&& rhs) noexcept
        {
            rhs.swap(*this);
            return *this;
        }
        void swap(CurlConnector& other) noexcept
        {
            using std::swap;
            swap(curl, other.curl);
            swap(host, other.host);
            swap(port, other.port);
            swap(response, other.response);
        }

        virtual RequestType getRequestType() const = 0;

        void sendMessage(std::string const& urlPath, std::string const& message)
        {
            std::stringstream url;
            response.clear();
            url << "https://" << host;
            if (port != 80)
            {
                url << ":" << port;
            }
            url << urlPath;

            CURLcode res;
            auto sListDeleter = [](struct curl_slist* headers){curl_slist_free_all(headers);};
            std::unique_ptr<struct curl_slist, decltype(sListDeleter)> headers(nullptr, sListDeleter);
            headers = std::unique_ptr<struct curl_slist, decltype(sListDeleter)>(curl_slist_append(headers.get(), "Content-Type: text/text"), sListDeleter);

            curlSetOptionWrapper(CURLOPT_HTTPHEADER,        headers.get(),          "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_HTTPHEADER:");
            curlSetOptionWrapper(CURLOPT_ACCEPT_ENCODING,   "*/*",                  "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_ACCEPT_ENCODING:");
            curlSetOptionWrapper(CURLOPT_USERAGENT,         "ThorsCurl-Client/0.1", "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_USERAGENT:");
            curlSetOptionWrapper(CURLOPT_URL,               url.str().c_str(),      "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_URL:");
            curlSetOptionWrapper(CURLOPT_POSTFIELDSIZE,     message.size(),         "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_POSTFIELDSIZE:");
            curlSetOptionWrapper(CURLOPT_COPYPOSTFIELDS,    message.data(),         "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_COPYPOSTFIELDS:");
            curlSetOptionWrapper(CURLOPT_WRITEFUNCTION,     curlConnectorGetData,   "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_WRITEFUNCTION:");
            curlSetOptionWrapper(CURLOPT_WRITEDATA,         this,                   "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_WRITEDATA:");

            switch(getRequestType())
            {
                case Get:       res = CURLE_OK; /* The default is GET. So do nothing.*/         break;
                case Head:      res = curl_easy_setopt(curl, CURLOPT_CUSTOMREQUEST, "HEAD");    break;
                case Put:       res = curl_easy_setopt(curl, CURLOPT_PUT, 1);                   break;
                case Post:      res = curl_easy_setopt(curl, CURLOPT_POST, 1);                  break;
                case Delete:    res = curl_easy_setopt(curl, CURLOPT_CUSTOMREQUEST, "DELETE");  break;
                default:
                    throw std::domain_error(buildErrorMessage("CurlConnector::", __func__, ": invalid method: ", static_cast<int>(getRequestType())));
            }
            if (res != CURLE_OK)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_setopt CURL_METHOD:", curl_easy_strerror(res)));
            }
            if ((res = curl_easy_perform(curl)) != CURLE_OK)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_perform:", curl_easy_strerror(res)));
            }
        }
        void recvMessage(std::string& message)
        {
            message = std::move(response);
        }
};

class CurlPost: public CurlConnector
{
    public:
        using CurlConnector::CurlConnector;
        virtual RequestType getRequestType() const {return Post;}

};

size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata)
{
    CurlConnector*  self = reinterpret_cast<CurlConnector*>(userdata);
    return self->getData(ptr, size * nmemb);
}

    }
}
```



A very cursory look at protocols and why they are needed

Socket Protocols


# [Nisse](https://github.com/Loki-Astari/Nisse)

[Nisse](https://github.com/Loki-Astari/Nisse) is a C++ library that simplifies the creation of C++ web-based [applications](https://github.com/Loki-Astari/Nisse/tree/master/src/Examples). Nisse provides a framework for handling incoming requests and executing user-defined code asynchronously. To achieve this, Nisse creates managed socket connections that can be utilized by user code and will automatically suspend execution of user code and *RE-USES* the thread if the user code would block during a read/write operation on a connection, thus offering easily accessible asynchronous functionality.

The concept is to make it simple for beginner engineers to write normal synchronous-looking C++ code that is easy to reason about but automatically provides asynchronous processing that is inherently needed for web-based applications to function efficiently.

## Why

I admire the Javascript/NodeJS model that makes it (relatively) easy for beginners to quickly and intuitively build simple working web-based applications. The ability to quickly create and deploy simple web apps is a great teaching platform that has allowed easy experimentation by beginners and thus provides them with a platform to learn new skills that are easy to demonstrate to friends (The “Look what I have built” word of the month).

In comparison, building even simple web-based apps in C++ is nontrivial and not suitable for teaching. I doubt it will ever be as simple to create production web apps in C++, but I hope that Nisse can help beginners quickly throw together a rapid prototype of a web-based application and shout out to their friends, "Look what I have built; come check it out …".

## How

Nisse is built on some standard libraries ([libEvent](https://libevent.org/), [Boost CoRoutine2](https://www.boost.org/doc/libs/1_86_0/libs/coroutine2/doc/html/index.html)) that do the heavy lifting. Nisse wires them together in a simple-to-use framework. Boost-CoRoutines provide cooperative multitasking, allowing user code to be suspended when a core/thread is blocked waiting on IO, and libEvent provides the dispatch loop that is keyed on IO operations, allowing user code to be rescheduled when the operation can be resumed.

## Plan

I will create a series of posts explaining how Nisse works while providing a mini tutorial on C++ coding and web applications as I go. Once this initial series is complete, I will use Nisse as a platform to build little applications that demonstrate C++ coding and provide lessons in modern C++ techniques that are fun and easy to understand for beginners.

* [Nisse V1](https://lokiastari.com/posts/NisseV1): A Web Server: A very basic C++ Web Server
* [Nisse V2](https://lokiastari.com/posts/NisseV2): C++ Sockets:  A C++ wrapper around C Sockets and SSL.
* [Nisse V3](https://lokiastari.com/posts/NisseV3): SSL Certificates: What is a certificate and where do I get one.
* [Nisse V4](https://lokiastari.com/posts/NisseV4): Multi Threading: Handling multiple request asynchronously.


Nisse. The step by step creation of a C++ Server architecture.

Nisse - Origins of a Server Library


# [Nisse](https://github.com/Loki-Astari/Nisse)

Describing all aspects of Nisse in a single article would be complex and overwhelming. I want to start with a beginner’s perspective and address a real-world problem that many beginners attempt. I will identify some of the issues and introduce solutions one at a time, ultimately leading to the final library, which is Nisse.

The simplest web application I can build is a web server. A web server maintains no state between calls, and the interface is straightforward. The client sends an [HTTP message](https://developer.mozilla.org/en-US/docs/Web/HTTP/Messages#http_requests) and, in return, receives an [HTTP response](https://developer.mozilla.org/en-US/docs/Web/HTTP/Messages#http_responses).

Even better, we already have applications (browsers) that handle all the difficult aspects of interacting with a web server, so we don’t need to write a client-side application.

## NisseV1

All the code for this article is in the directory [V1](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V1). It uses only the standard libraries, so it should be easy for anybody to build. A “Makefile” is provided as an example.

### Build & Run

```bash
  > git clone https://github.com/Loki-Astari/NisseBlogCode.git
  > cd NisseBlogCode/V1
  > make
  > ./NisseV1 8080 /Directory/You/Want/To/Server/On/Port/8080
```

I will go over a couple of things in the file that I believe are worth explicitly pointing out:

###  [HTTPStuff.cpp](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V1/HTTPStuff.cpp)

The code in this file is just enough to parse an HTTP Get request and provide a file in the HTTP Response object. It is provided here solely so that all examples can be compiled. Note: this is not part of Nisse, I will come back and address the code in a subsequent article on HTTP and expand this to be more comprehensive.

### [Stream.h](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V1/Stream.h)

This is the interface between the server code and the HTTPStuff. For these articles, I wanted to keep the interface as simple as possible, and again, this is not part of Nissa.

### [NisseV1.cpp](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V1/NisseV1.cpp)
 
```C++
int main(int argc, char* argv[])
{
    if (argc != 3)
    {
        std::cerr << "Usage: NisseV1 <port> <documentPath>" << "\n";
        return 1;
    }
    
    try
    {
        static const int port = std::stoi(argv[1]);
        static const std::filesystem::path  contentDir  = std::filesystem::canonical(argv[2]);
    
        std::cout << "Nisse Proto 1\n";
        WebServer   server(port, contentDir);
        server.run();
    }
    catch(std::exception const& e)
    {
        std::cerr << "Exception: " << e.what() << "\n";
        throw;
    }
    catch(...)
    {
        std::cerr << "Exception: UNKNOWN\n";
        throw;
    }
}
```

The `main()` function obtains and validates user input to initialize the server. If everything is in order, it creates a `WebServer` object and starts the application dispatch loop by calling `run()`.

Here are two main points to note:
1. Unlike most beginner tutorials, web applications are event-driven. They operate with a "dispatch loop" that executes user code when events occur rather than following a sequential list of commands. In this example, the `run()` function represents the dispatch loop and manages all the underlying details. Typically, frameworks allow you to register user code for specific events, but since this is a simple application, it simply handles an HTTP request.

2. I use exceptions to handle critical errors. Many engineers believe exceptions are problematic because they obscure control flow (I partially agree). However, I prefer using exceptions, judiciously, as they reduce the amount of explicit error-handling code required for serious issues that necessitate application shutdown. When shutting down a C++ application, it is essential to unwind the stack correctly and ensure all relevant destructors are called to release resources; therefore, `abort()`, `terminate()`, and `exit()` are usually inappropriate (unless there is corruption) in C++ applications (unlike in C). You **MUST** catch exceptions in `main(),` as it is implementation-defined whether the stack unwinds if an exception escapes the `main()` function. By catching the exception in `main()`, you ensure the stack unwinds correctly, and all destructors are called. Then, you can generate appropriate messages and logs before re-throwing the exceptions. Re-throwing allows the OS to take necessary actions when the application exits abnormally.

### Socket Code

A minor call out. The socket code is all C code (and thus in the global namespace). You will see in my code that all C code is prefixed by `::` to make sure I explicitly call the C version of these functions. For example, when creating a server-end socket, I call `::socket(),` `::bind(),` `::listen()`, and `::accept()`. This ensures that I do not accidentally call similarly named methods.
 
A lot of the code in this example is simply creating and handling sockets and doing a rudimentary job of checking and handling basic errors that these functions could generate; class [Server](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V1/NisseV1.cpp#L140-L190) is 50 lines and class [Socket](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V1/NisseV1.cpp#L192-L391) is another 200 lines and represents more than half the code.

### Errors

The C socket code has a simple interface and returns `-1` when there is an error. An error when creating sockets usually means programming issues, but in all these cases, the error is unrecoverable, so we simply throw an exception to exit the application (and clean up any connections).

```C++
Server::Server(int port)
{
    fd = ::socket(AF_INET, SOCK_STREAM, 0);
    if (fd == -1) {
        throw std::runtime_error{Message{} << "Failed to create socket: " << errno << " " << strerror(errno)};
    }
    
    struct ::sockaddr_in        serverAddr{};
    serverAddr.sin_family       = AF_INET;
    serverAddr.sin_port         = htons(port);
    serverAddr.sin_addr.s_addr  = INADDR_ANY;
    
    int bindStatus = ::bind(fd, reinterpret_cast<struct ::sockaddr*>(&serverAddr), sizeof(serverAddr));
    if (bindStatus == -1) {
        throw std::runtime_error{Message{} << "Failed to bind socket: " << errno << " " << strerror(errno)};
    }
    
    int listenStatus = ::listen(fd, backlog);
    if (listenStatus == -1) {
        throw std::runtime_error{Message{} << "Failed to listen socket: " << errno << " " << strerror(errno)};
    }
}
```

During read/write operations, the return value is either -1 on failure or the number of bytes received/sent. We need to address two issues: an error is not always fatal, and success does not always indicate that the operation has been completed as requested. Therefore, code must be explicitly added to check for all scenarios. This typically means that read/write operations are performed in a loop until either a critical failure occurs or you decide that enough data has been retrieved/sent.


```C++
void Socket::readMoreData(std::size_t maxSize, bool required)
{
    // This function read "MoreData" onto the end of buffer.
    // Note: There may be data already in buffer so this appends it.
    //       We will read no more than "maxSize" more data into buffer.
    // The required flag indicates if we must read "maxSize" if true
    // the loop will continue until we get all the data otherwise the
    // function returns after any data is received.
    std::size_t     currentSize = std::size(buffer);
    std::size_t     amountRead  = 0;
    buffer.resize(currentSize + maxSize);
    
    while (readAvail && amountRead != maxSize)
    {
        int nextChunk = ::read(fd, &buffer[0] + currentSize + amountRead, maxSize - amountRead);
        if (nextChunk == -1 && errno == EINTR) {
            continue;           // An interrupt can be ignored. Simply try again.
        }
        if (nextChunk == -1 && errno == ECONNRESET) {
            readAvail = false;  // The client dropped the connection. Not a problem
            break;              // But no more data can be read from the socket.
        }
        if (nextChunk == -1) {
            buffer.resize(currentSize + amountRead);
            throw std::runtime_error(Message{} << "Catastrophic read failure: " << errno << " " << strerror(errno));
        }
        if (nextChunk == 0) {   // The connection was closed gracefully.
            readAvail = false;  // OS handled all the niceties.
        }
        amountRead += nextChunk;
        if (!required) {
            break;  // have some data. Lets exit and see if it is enough.
        }
    }
    // Make sure to set the buffer to the correct size.
    buffer.resize(currentSize + amountRead);
}
```

I want to emphasize that I have done the bare minimum in error checking here. This is adequate for a simple demo program but insufficient for production code. The problem is that error codes are not entirely consistent across ‘＊nix’ variants and differ significantly from Windows systems. I will discuss this in the next article. 

## Next Step

Address inconsistencies between ‘＊nix’ and `Windows` platforms.



Nisse

A Web Server


# [Nisse](https://github.com/Loki-Astari/Nisse)

In the previous article "A Web Server," I created the simplest web server possible.

This article covers the next stage by addressing the issues related to low-level socket programming. To be honest, we are going to take a shortcut. Dealing with ‘＊nix’ variants is complex enough, but adding Windows systems makes the process exceedingly complicated (and thus beyond the scope of this article). Here, we are going to introduce a C++ library to abstract the socket layer and provide a higher-level interface.

## NisseV2

All new code for this article is in the directory [V2](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V2). It re-uses HTTPStuff.cpp and Stream.h from [V1](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V1). It uses standard libraries and [thors-mongo](https://github.com/Loki-Astari/ThorsMongo). If you have a Unix-like environment, this should be easy to build; if you use Windows, you may need to do some extra work. A “Makefile” is provided just as an example.

### Build & Run

```bash
  > brew install thors-mongo              # A header-only version of thors-mongo can be alternatively installed.
  > git clone https://github.com/Loki-Astari/NisseBlogCode.git
  > cd NisseBlogCode/V2
  > make
  > ./NisseV2 8080 /Directory/You/Want/To/Server/On/Port/8080
```

## ThorsSocket

I am going to add [ThorsSocket](https://github.com/Loki-Astari/ThorsSocket), a C++ wrapper around 'File Descriptors' (FD), to simplify the web server. ThorsSocket provides a [`std::iostream`](https://en.cppreference.com/w/cpp/io/basic_iostream) interface for FD and is designed to work with the [Boost Co-Routine](https://www.boost.org/doc/libs/1_86_0/libs/coroutine2/doc/html/index.html) library to enable cooperative multitasking.

Because FDs are a very low-level OS resource, ThorsSocket provides a [`std::iostream`](https://en.cppreference.com/w/cpp/io/basic_iostream) interface to several important OS resources, such as pipes, files, sockets, and SSL sockets (ssockets). Note that the standard library already provides access to files through [`std::fstream`](https://en.cppreference.com/w/cpp/io/basic_fstream) but only allows blocking read/write access; in contrast, ThorsSocket provides non-blocking read/write access, allowing the executing thread to cooperatively switch to another task when an I/O operation would block and transparently resuming the I/O operation when the FD becomes available.

Another advantage of ThorsSocket is that it wraps both the C socket and Open SSL libraries, allowing the use of the secure socket layer as if it were a normal [`std::iostream`](https://en.cppreference.com/w/cpp/io/basic_iostream) object. Apart from the initial creation of the socket, its usage is entirely transparent and no different from using a normal socket (or even a file).

### [NisseV2.cpp](https://github.com/Loki-Astari/NisseBlogCode/blob/master/V2/NisseV2.cpp)

ThorsSocket provides the class `ThorsAnvil::ThorsSocket::SocketStream` that wraps a FD and implements the `std::iostream` interface. But the HTTPStuff interface uses a `Stream` interface as defined in the file `Stream.h`. So we must provide a simple wrapper.

```C++
class Socket: public Stream
{
    ThorsAnvil::ThorsSocket::SocketStream    stream;
    public:
        Socket(ThorsAnvil::ThorsSocket::SocketStream&& stream)
            : stream(std::move(stream))
        {}

        virtual std::string_view    getNextLine()               override
        {
            static std::string line;
            std::getline(stream, line);
            return line;
        }
        virtual void ignore(std::size_t size)                   override {stream.ignore(size);}
        virtual void sendMessage(std::string const& message)    override {stream << message;}
        virtual void sync()                                     override {stream.sync();}
        virtual bool hasData()  const                           override {return static_cast<bool>(stream);}
        virtual void close()                                    override {stream.close();}
};
```

The previous `Server` class in V1 is simply replaced by the class `ThorsAnvil::ThorsSocket::Server`.

Replacing these two classes has removed the majority of the complexity of the server code. Note: I am using a library I am very familiar with (and the author of), but there are several C++ libraries that would provide similar functionality and could be used in a similar way. My point (I think) is that the C interface to FD, though very flexible, is on the complex side, and this, complexity can be abstracted by using an appropriate C++ library.

### Next Steps

Thus far, we have only used simple sockets. But for modern servers, we also need to handle SSL connections. In the next article, I will explain what is needed to set up a server to accept an correctly authenticate an SSL connection.



C++ Sockets


# [Nisse](https://github.com/Loki-Astari/Nisse)

In the previous article, "C++ Sockets," I mentioned that thors-mongo had built-in support for SLL connections but glossed over the details. In this article, we will go over the additions needed. From the server side, you need an SSL certificate. But what is an SSL certificate, and how do you obtain one?

## SSL Certificates

The SSL certificate has two main purposes.

1. Securely encrypt all traffic between the client and server.
2. Provides trust that you are talking to a server on the requested domain.

### The Basics

SSL certificates are issued by trusted certificate authorities and contain information that validates the certificate cryptographically. When a browser connects to a website, the server returns the certificate, which includes crucial information such as the issuing company. Before establishing a secure connection, the browser validates the certificate against the issuing company’s SSL certificate to ensure it is not forged. If the issuing company is a subsidiary, it recursively looks up the parent company that issued the certificate and validates their certificates until it reaches a root certificate. This process creates a chain of trust leading to a known trusted root certificate.

All modern browsers know how to find and validate root certificates. They also have information about compromised certificate authorities whose certificates should no longer be trusted. Therefore, it is important to download only trusted browsers and keep them up to date.

Once a certificate has been validated, the browser knows it is communicating with a server for a specific domain (as the domain information is included in the certificate). Modern browsers indicate a secure connection, usually with a green padlock next to the URL. The browser can then use the public key in the certificate to establish a secure connection with the domain you are connecting to.

### Where can you get a certificate

If you are a large company trusted by the Internet, you can create your own root certificate. While this is not difficult, it is of little value if no one trusts you. Therefore, the crucial step for a root certificate holder is becoming trusted by tools that validate certificates. Losing trust would mean having your root certificate removed from the list people use to validate certificates (i.e., the Chrome browser team would remove your certificate from the list of root certificates it trusts). This loss of trust would affect the root certificate authority and all downstream companies that hold certificates based on that root certificate; a browser would mark any sites using an untrusted root certificate as not being trusted.

Obtaining a certificate from a trusted root authority can be expensive and is typically only done by companies that issue certificates. However, you don't necessarily need a certificate from a root authority; you can get a certificate from a vendor that has a certificate issued by a root authority. Every trusted certificate authority has a process to validate that you own a domain, which allows them to create and deliver a signed certificate to you, but each authority's process is different. But for normal people (and small companies), you can get relatively cheap SSL certificates from most domain providers (like `GoDaddy`) that will create and manage your SSL Certificate for your domain.

### Free Certificates

You can get Free SSL Certificates from a company called [Let’s Encrypt](https://letsencrypt.org/).

## Code

All the code for this article is in the directory [V3](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V3) directory. It uses standard libraries and [thors-mongo](https://github.com/Loki-Astari/ThorsMongo). If you have a Unix-like environment, this should be easy to build; if you use Windows, you may need to do some extra work. A “Makefile” is provided just as an example.

### Build & Run

```bash
  > brew install thors-mongo              # A header-only version of thors-mongo can be alternatively installed.
  > git clone https://github.com/Loki-Astari/NisseBlogCode.git
  > cd NisseBlogCode/V3
  > make
  > ./NisseV3 8080 /Directory/You/Want/To/Server/On/Port/8080 /etc/letsencrypt/live/<MySite.com>/
```

## How to Use ThorsSocket With an SSL Certificate

In ThorsSocket a normal socket is created with the following code:

```C++
    ThorsAnvil::ThorsSocket::Server   server(ServerInit{port});
    
    ThorsAnvil::ThorsSocket::Socket   socket = server.accept();          // A normal bi-direconal socket.
```

To create a secure connection, specify the location of the SSL certificate file on the host file system. If you use [Let’s Encrypt](https://letsencrypt.org/), the default location for the SSL certificate is `/etc/letsencrypt/live/<domainName>/fullchain.pem`, and the private key is located at `/etc/letsencrypt/live/<domainName>/privkey.pem`. You can then create a secure SSL connection with:

```C++
    // The path where the certificates for “thorsanvil.dev” are stored.
    std::string   certPath = "/etc/letsencrypt/live/thorsanvil.dev”;
    
    // Create a certificate object that contains the SSL Certificate and private key.
    // Note: Some files require you to provide a password to access the certificate, please see the documentation
    // on how to add appropriate lambda’s to retrieve the password from secure storage (as they should not be in the code)
    ThorsAnvil::ThorsSocket::CertificateInfo     certificate{std::filesystem::canonical(std::filesystem::path(certPath) /= "fullchain.pem”,
                                                             std::filesystem::canonical(std::filesystem::path(certPath) /= "privkey.pem”
                                                            };
    ThorsAnvil::ThorsSocket::SSLctx              ctx{ThorsAnvil::ThorsSocket::SSLMethodType::Server, certificate};
    ThorsAnvil::ThorsSocket::Server              server(SServerInit{port, std::move(ctx)});
    
    ThorsAnvil::ThorsSocket::Socket   socket = server.accept();          // A secure bi-direconal SSL socket.
```

## How to handle SSL or normal connections

The `ThorsAnvil::ThorsSocket::Socket` class can be constructed with `ServerInit` or `SServerInit` object. To simplify this, the constructor also takes a `std::varient` (ServerInit) that can contain either of these objects. This allows us to write a function like this to initialize a server connection to initialize either type.

```C++
namespace TASock = ThorsAnvil::ThorsSocket;

// Always need a port to listen on.
// If we have an SSL certificate then pass its location in `certPath` (which may be empty)
TASock::ServerInit getServerInit(int port, std::optional<std::filesystem::path> certPath)
{
    // If there is only a port.
    // i.e. The user did not provide a certificate path return a `ServerInfo` object.
    // This will create a normal listening socket.
    if (!certPath.has_value()) {
        return TASock::ServerInfo{port};
    }
    
    // If we have a certificate path.
    // Use this to create a certificate object.
    // This assumes the standard names for these files as provided by "Let's encrypt".
    TASock::CertificateInfo     certificate{std::filesystem::canonical(std::filesystem::path(*certPath) /= "fullchain.pem"),
                                            std::filesystem::canonical(std::filesystem::path(*certPath) /= "privkey.pem")
                                           };
    TASock::SSLctx              ctx{TASock::SSLMethodType::Server, certificate};
    
    // Now that we have created the appropriate SSL objects needed.
    // We return an SServierInfo object.
    // Please Note: This is a different type to the ServerInfo returned above (one less S in the name).
    return TASock::SServerInfo{port, std::move(ctx)};
    
    // We can return these two two different types because
    // ServerInit is actually a std::variant<ServerInfo, SServerInfo>
}
```

To use this we just need to adjust `main()` slightly.

```C++
The only change in Nisse’s API from V1 is that it allows the user to provide a certificate and key file.

```C++
int main(int argc, char* argv[])
{
    if (argc != 4 && argc != 3)
    {
        std::cerr << "Usage: NisseV3 <port> <documentPath> [<SSL Certificate Path>]" << "\n";
        return 1;
    }
    ...
        std::optional<std::filesystem::path>    certDir;
        if (argc == 4) {
            certDir = std::filesystem::canonical(argv[3]);
        }
    ...
        WebServer   server(getServerInit(port, certDir), contentDir);
    ...
}
```

### What is the next step

We have a Web Server that can connect over SSL. But the server only handles request serially. So the next article looks at how to add some basic parallelism to support multiple simultaneous connections.



SSL Certificates


# [Nisse](https://github.com/Loki-Astari/Nisse)

In the first three articles, we created a very basic Web Server. A major issue with this simplistic server is that it can only handle connections serially. This article introduces a thread pool that will handle the actual requests. The main thread will accept new requests and create the work items to be handled by the thread pool.

## NisseV4

All the code for this article is in the directory [V4](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V4) directory. It uses standard libraries and [thors-mongo](https://github.com/Loki-Astari/ThorsMongo). If you have a Unix-like environment, this should be easy to build; if you use Windows, you may need to do some extra work. A “Makefile” is provided just as an example.

### Build & Run

```bash
  > brew install thors-mongo              # A header-only version of thors-mongo can be alternatively installed.
  > git clone https://github.com/Loki-Astari/NisseBlogCode.git
  > cd NisseBlogCode/V4
  > make
  > ./NisseV4 8080 /Directory/You/Want/To/Server/On/Port/8080 /etc/letsencrypt/live/<MySite.com>/
```

## Threading Potential concerns

In some previous code reviews I have done, I have seen beginners create a new thread for each new connection that is created. The thread will handle the request and complete (thread exiting and being killed). This is acceptable for a Web Server that handles a very low volume of calls and will keep the code simple, but it is a problematic design for high-volume or general servers.

Creating a thread is a resource-intensive process, so it's generally discouraged to create and destroy a large number of threads. Additionally, the CPU can typically handle only one thread per core at any time; therefore, making a vast number of threads may lead to [thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)#) as the scheduler attempts to allocate time slices for each thread to perform active work.

The best practice is generally to create a thread pool in which threads are assigned “Work Items” from a queue. Upon completion, they are reused to handle subsequent “Work Items” but suspended when no “Work Items” are available.

The C++ standard tried to indirectly address thread pools via the standard library `async()` function. This function abstracts the concept of threads and allows the implementation to provide its own internal thread pool. However, we are not going to use this feature in this project; in a subsequent article, I want to explore the concepts of cooperative multitasking using CoRoutines.

##  What has Changed

We have added a class [JobQueue](https://github.com/Loki-Astari/NisseBlogCode/tree/master/V4/JobQueue.h) that maintains a pool of worker threads and a queue of jobs (active connections) that need to be handled. Before delving into the details of JobQueue, I will describe the changes to the code presented in the previous article [C++ Sockets](https://lokiastari.com/posts/NisseV2).

### WebServer

```C++
class WebServer
{
    TASock::Server                      connection;
    bool                                finished;
    std::filesystem::path const&        contentDir;
    // State information that can be used by the threads.
    // Objects placed in a std::map are not moved once inserted so taking
    // a reference to them is safe and can be used by another thread.
    std::mutex                          openSocketMutex;
    std::map<int, Socket>               openSockets;
    // A JobQueue that holds a pool of threads to execute inserted jobs asynchronously.
    JobQueue                            jobQueue;
    public:
        WebServer(std::size_t workerCount, TASock::ServerInit&& serverInit, std::filesystem::path const& contentDir);

        void run();
};
```

The main code change is within the `run()` method. Previously, this method simply accepted a connection and called `handleConnection()` to process the incoming request. Thus, it blocked the main thread from accepting another connection until the current connection had been fully handled.

```C++
void WebServer::run()
{
    while (!finished)
    {
        ThorsAnvil::ThorsSocket::SocketStream socket = connection.accept();

        handleConnection(socket);
    }
}
```

The new version is similar. The main thread still accepts connections, but instead of handling them, it adds a “Work Item” to the job queue for the thread pool to process asynchronously. It is important to note that because the work is done in another thread, we must store the state (the `newSocket` object) in a way that prevents it from being destroyed until the connection has been handled. We have introduced the `openSockets` object to store these connections.

```C++
void WebServer::run()
{
    while (!finished)
    {
        // Main thread waits for a new connection.
        TASock::SocketStream socketStream = connection.accept();
        int fd = socketStream.getSocket().socketId();
        Socket newSocket(std::move(socketStream));

        // Add the “newSocket” into the std::map object “openSockets”
        std::unique_lock<std::mutex>    lock(openSocketMutex);
        auto [iter, ok] = openSockets.insert_or_assign(fd, std::move(newSocket));

        // Add a lambda to the JobQueue to handle the newly created socket.
        // Note: A copy of the “iter” is placed in the object “iterator” so we can use
        //       this to extract a reference to the socket object. This is thread safe
        //       as iterators to std::map are not invalidated by operations on the map
        //       (as long as the object is not deleted).
        jobQueue.addJob([&, iterator = iter](){
            // Get a reference to the socket.
            auto& socket = iterator->second;
            // Handle the reference as before.
            handleConnection(socket, contentDir);
            // Once processing is complete remove the storage for Socket
            // and cleanup any associated storage.
            std::unique_lock<std::mutex>    lock(openSocketMutex);
            openSockets.erase(iterator);
        });
    }
}
```

### JobQueue

In C++20 the standard library added a new thread type, `std::jthread`. Quote: [indi](https://codereview.stackexchange.com/users/170106/indi) `std::jthread is what std::thread should have been. It is superior in every way, with no drawbacks`.

Unfortunately, my platform does not currently support `std::jthread` in its implementation of the C++20 standard library. Therefore, the following code must navigate some extra hoops to ensure that `std::thread` behaves correctly in all corner cases. One major difference is that with `std::thread`, you must explicitly `join()` the thread of execution before the `std::thread` object is destroyed. In contrast, the `std::jthread` destructor will automatically `join()` the thread of execution if not already done.

#### Construction

```C++
JobQueue::JobQueue(std::size_t workerCount)
    : finished{false}
{
    try
    {
        for (std::size_t loop = 0; loop < workerCount; ++loop) {
            workers.emplace_back(&JobQueue::processWork, this);
        }
    }
    catch (...)
    {
        // because `std::thread` may potentially throw during construction.
        // We must ensure we correctly clean up any constructed `std::thread` objects
        // otherwise the thread of execution will not be correctly joined, and the application
        // terminated. 
        stop();

        // Once we know the threads have been correctly cleaned up, we can re-throw the exception.
        throw;
    }
}

JobQueue::~JobQueue()
{
    // Wait for all threads of execution to be correctly joined.
    stop();
}
```

The `stop()` method is actually relatively simple to implement.

```C++
void JobQueue::markFinished()
{
    std::unique_lock    lock(workMutex);
    finished = true;
}

void JobQueue::stop()
{
    // Setting the finished variable prevents threads from picking up new work in the
    // `getNextJob() method and cause them to exit a loop in the `processWork()` method
    // thus completing.
    markFinished();

    // Some threads may be waiting on a condition variable; this will release them to go check for the next job.
    workCV.notify_all();

    // Wait for all threads of execution to complete by execution `join()` on them.
    for (auto& w: workers) {
        w.join();
    }

    // Once all threads of execution have completed:
    // Destroy the thread objects.
    workers.clear();
}
```

#### Adding Work

Finally, we can look at the methods run by the threads.

If you are new to threading, the only challenging concept is the `std::condition_variable`. This type allows you to suspend a thread's execution until a specific condition is met. While a thread is suspended, it consumes no resources, which makes it an effective way to ensure that the CPU isn’t used when there is no work for the thread to perform. You suspend a thread by calling `wait()` on the condition variable. Another thread can wake up suspended threads by calling `notify_one()` (which wakes up one suspended thread) or `notify_all()` (which wakes up all suspended threads).

Code typically follows this pattern:
```C++
    std::mutex               mutex;
    std::condition_variable  cv;

    ….


    // Code run by thread
    std::unique_lock    lock(mutex);
    while (!resourceIWantIsAvailable())  // Notice the ! at the beginning of the test.
    {
        cv.wait(lock);
        // The wait function will release the lock and then suspend the thread.
        // When a thread is woken up, it must first reacquire the lock before it returns from wait()
        // So when the wait() function exists, it still has the lock it established above.
    }

    // If the thread reaches here, we know the resource is available for the thread.
```

The first question most beginners ask is: `Why is the wait() function called inside a loop?`. This is because between the time a thread calls `notify_one()` to wake up a waiting thread and the point a waiting thread exists the wait() function, another thread may have already consumed the resource. Therefore, you need to validate that the resource is still available, and if not, go back into the wait().

This loop is essential, so the C++ `std::conditional_variable` actually builds it into the wait interface. You can pass a lambda to the test as a second parameter.

```C++
        cv.wait(lock, [&](){return resourceIWantIsAvailable();});
```

Now that we have covered the basics of a condition variable, the code used by the thread pool looks like this.


```C++
// Retrieve a job from the work queue.
// Suspend on condition variable if needed.
// Note 1: In a shutdown scenario, the `finished` variable is true. In this case return but with no work.
// Note 2: Because you can return without work, the return type is `std::optional`.
std::optional<Work> JobQueue::getNextJob()
{
    std::unique_lock    lock(workMutex);
    workCV.wait(lock, [&](){return !workQueue.empty() || finished;});

    // We are returning with no work.
    // So simply exit.
    if (workQueue.empty() || finished) {
        return {};
    }

    // If we reach here, we have a lock on `workMutex` so we can modify the
    // the state of the object. Extract the oldest “Work Item” from the queue
    // and return it.
    Work work = std::move(workQueue.front());
    workQueue.pop();
    return work;
}

void JobQueue::processWork()
{
    // While the server is running loop.
    while (!finished)
    {
        // Get a piece of work from the queue.
        std::optional<Work> work   = getNextJob();
        try
        {
            // We run work items inside a try block as “User Code” can not be trusted.
            if (work.has_value()) {
                (*work)();
            }
        }
        // If there is an exception, we log it, but DO NOT exit.
        // An exception in “User Code” should not affect the stability of the server itself.
        catch (std::exception const& e)
        {
            ThorsLogWarning("ThorsAnvil::Nissa::JobQueue", "processWork", "Work Exception: ",  e.what());
        }
        catch (...)
        {
            ThorsLogWarning("ThorsAnvil::Nissa::JobQueue", "processWork", "Work Exception: Unknown");
        }
    }
}
```

## Next Step

This article explains how we can use threads to potentially parallelize responses to multiple requests. Each thread sequentially runs only one request at a time and may be blocked while processing a request. In a subsequent article, I will detail how we can utilize cooperative multitasking to switch I/O-blocked threads to another request, improving parallelism without using additional resources.



All Posts