DEV Community: Dave Amiana

Introduction to CMake

Dave Amiana — Sun, 11 Sep 2022 19:16:16 +0000

For writing cross-platform applications

At some point in our C++ journey, we meet tools that improve our project's maintainability. Configuring build systems help us relieve the overhead of writing multiple makefiles for different platforms. This ensures that we can be able to build and deploy software across multiple platforms.

It's been only 3 months since I first integrated CMake into my C++ projects. And since then, I'm able to write my program without worrying about different compilers, and Operating Systems it will run on. It allowed me to focus more on the work. Indeed, it has added value both to my development experience and my projects. So I'm starting this series to document the things I learned from Dominik Berner, and Mustafa Kemal Gilor's (2022) book: CMake Best Practices.

In this article, I will briefly cover CMake and take you through an overview of its build process. And on the next part, we will look at CMake as a scripting language.

What is CMake?

CMake is an open-source project that serves as a tool for building, testing, packaging, and distributing cross-platform software
CMake is a scripting language written in C++
CMake is a de facto industry standard for building C++ projects
CMake is divided into 3 command-line tools:
- cmake: for generating compiler-independent build instruction
- ctest: for detecting and running tests
- cpack: for packing the software project into convenient installers

Benefits of using CMake

Provides an interface to configure a compiler-independent build
Separate the source code directory and the compiler outputs: enable building multiple builds from the same source tree
Supports cross-compilation
Enables CI/CD automation for testing and building the project*
Integrates well with package managers such as Conan
Improves the project's maintainability by providing a single point of definitions from build configuration, testing, and packaging specifications

Installing CMake

Download CMake from: https://cmake.org/download/
1. It is available as a pre-compiled binary or as a source code
Extract it into a folder and open the command line in that directory
Run the command ./configure make
To install CMake, run the command make install
To check if the installation is successful, run cmake --version. It should print out the version of CMake, like this:

C:\Users\[username]\[path]>cmake --version
cmake version 3.22.1

CMake suite is maintained and supported by Kitware (kitware.com/cmake).

`Hello, World!` in CMake

Before writing your C++ project, it is good practice to test out the build configuration first. This section briefly walks you through the minimal CMake configuration for hello, world! in C++.

Execute mkdir src to create the following directory.

  └───src

Write the main.cpp inside the src directory:

  #include <iostream>

  auto main() -> int {
    std::cout << "hello, world! \n";    
    return 0;
  }

Create CMakeLists.txt and add the following commands:

  cmake_minimum_required(VERSION 3.10)
  # set project name, version, description, and language specification 
  project(
    "HelloWorld"
    VERSION 1.0
    DESCRIPTION "Hello World in CMake"
    LANGUAGES CXX
  )
  # tells CMake to build an executable
  add_executable(${PROJECT_NAME})
  # tells CMake which location to look for the sources of the executable
  target_sources(${PROJECT_NAME} 
    PRIVATE src/main.cpp
  )

Go to the project directory and execute cmake -S . -B build to make the build directory.

$ cmake -S . -B build
-- The CXX compiler identification is GNU 10.3.0
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: [ProjectFolder]/build

Go to the build directory and run make to build the project.

$ cd build && make
Scanning dependencies of target HelloWorld
[ 50%] Building CXX object CMakeFiles/HelloWorld.dir/src/main.cpp.o
[100%] Linking CXX executable H

Execute the binary.

The Build Process

CMake build process is mainly broken down into two steps: configure and build.

Configure (triggered by the command cmake -S . -B build): CMake searches for any usable toolchain available and decides which configuration it outputs; The standard output is Unix Makefiles but in the event where Microsoft Visual Studio Compiler (MSVC) is detected *.sln file will be created instead.
- During this process, CMakeLists.txt is parsed and executed to configure the build files relative to the toolchains, architecture, and dependencies.
- CMake writes build files based on the generators; it can be changed using cmake . -G [generator] command.
Build (triggered by the command make): CMake will execute the build files to compile and link binaries, run tests, and pack artifacts.
- The build directory will contain the generated binaries, artifacts, build instructions, and cache
- Inside the build directory, CMakeCache.txt file will contain all the detected configurations

References

D. Berner & M.K. Gilor (2022). CMake Best Practices. Packt Publishing. ISBN 9781803239729.
CMake (2022). CMake Tutorial. https://cmake.org/cmake/help/latest/guide/tutorial/index.html
Wikipedia Contributors (2022). CMake. https://en.wikipedia.org/wiki/CMake
Cmake (2022). Why CMake? https://cmake.org/cmake/help/book/mastering-cmake/chapter/Why%20CMake.html

My Neovim Configuration

Dave Amiana — Thu, 01 Sep 2022 18:52:50 +0000

Setting up linters, syntax highlighter, NerdTrees, and more

Before we begin, let us motivate this topic with the relevance of Vim in 2022. I'll talk briefly about my personal experience learning Vim and the factors that got me into it. The second point of this discussion would be an instructional guide on how to configure your Neovim so you can turn it into a full-blown IDE.

Why do People use Vim in 2022?

There is a compelling reason why Vim has remained relevant to most developers for nearly half a century. Among developers, the functionality that Vim offers to edit multiple files with a few keystrokes is simply unmatched. Being able to progress on your deliverables and explore candidate solutions at the speed of thought is crucial among developers working in mid to large codebases. That is the reason I got into Vim. The learning curve is quite steep. It took me a week to get comfortable with the keystrokes, but it pays off quite well. (I found this cheat sheet helpful: https://vim.rtorr.com/.)

Watching more experienced developers like ThePrimeagen, George Hotz and Jason Turner move seamlessly on multiple files reimplementing their design and test their code made me want to incorporate Vim on my personal workflow. It allowed me to focus more on the code instead of spending too much time on popups in a GUI editor.

Although I don't write on Vim (and Neovim) every time, Text Editors and IDEs offer Vim keybindings. Minimizing the lags you spend clicking on the GUI. The point is, no matter where you go in your dev journey, you should give Vim a try.

Vim and Neovim

Neovim is a result of Vim Community's effort to support better scripting through Lua, modern plugins, and integration with modern GUIs (Wikipedia Contributors, 2022). The Neovim project started in 2014 with its main design focus dedicated to the extensibility and maintainability of Vim.

Most commands and Vim configurations work in Neovim by default as the Neovim project is a forked and more feature-rich version of Vim.

The title of this section naturally lends itself to the topic of which is better, but I leave that to your judgment to decide which works better for you. Personally, I find Neovim more friendly as code completion and static analyzers are simpler to configure.

Configuring Neovim

All configurations for Neovim are stored in the ~/.config/nvim directory. But unlike Vim which is available in most Linux distributions, you have to make sure that you have Neovim by running nvim -v. If it doesn't output the version, you have to install it using $ sudo apt install neovim. (I'm using Ubuntu, your distro may have a different package manager to install Neovim.)

Next, we have to install Git and Curl to set up Vim Plug which allows you to install Vim plugins. But first, let's make sure that we are up to date.



$ sudo apt update
$ sudo apt install git curl

To install Vim Plug, run the shell command for Linux:



sh -c 'curl -fLo "${XDG_DATA_HOME:-$HOME/.local/share}"/nvim/site/autoload/plug.vim --create-dirs \
       https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim'

Now, we navigate to ~/.config/nvim. If this directory is not available, make one using cd ~/ && mkdir .config/nvim. We put all our user-defined configurations in the ~/.config/nvim/init.vim file.

Don't panic if the blank screen opens. The first keys you should know to edit files in Vim are:

i for insert
[esc] + q for quit
[esc] + w for save
[esc] + wq for save and quit



:set number " show line numbers
:set relativenumber " show line number on the current line relative to other lines
:set autoindent " sets newline to inherit the indentation of prev lines
:set tabstop=4 " indents using 4 spaces
:set shiftwidth=4 " sets 4 spaces indents when shifting
:set smarttab " sets `tabstop` number of spaces when the tab is pressed
:set softtabstop=4 " sets 4 spaces when tab or backspace is pressed
:set mouse=a " enables the mouse for scrolling and resize

You may extend this initial configuration as you like, refer to: https://www.shortcutfoo.com/blog/top-50-vim-configuration-options/. If you're satisfied, save and exit.

Now for setting up the plugins. Your Vim plugins are declared between call plug#being() and call plug#end(). Inside we place a set of Plug [plugin URL] commands. And when we're satisfied, hit [esc] + :PlugInstall.

To enable the tagbar for my configuration, use:



$ sudo apt install exuberant-ctags

My personal Vim plugins are as follows:



call plug#begin('~/.config/nvim/plugged')

Plug 'http://github.com/tpope/vim-surround' " Surrounding ysw)
Plug 'https://github.com/preservim/nerdtree' " NerdTree
Plug 'https://github.com/tpope/vim-commentary' " For Commenting gcc & gc
Plug 'https://github.com/vim-airline/vim-airline' " Status bar
Plug 'https://github.com/ap/vim-css-color' " CSS Color Preview
Plug 'https://github.com/rafi/awesome-vim-colorschemes' " Retro Scheme
Plug 'https://github.com/ryanoasis/vim-devicons' " Developer Icons
Plug 'https://github.com/tc50cal/vim-terminal' " Vim Terminal
Plug 'https://github.com/preservim/tagbar' " Tagbar for code navigation
Plug 'https://github.com/terryma/vim-multiple-cursors' " CTRL + N for multiple cursors

call plug#end()

nnoremap <C-f> :NERDTreeFocus<CR>
nnoremap <C-n> :NERDTree<CR>
nnoremap <C-t> :NERDTreeToggle<CR>

nmap <F8> :TagbarToggle<CR>

let g:NERDTreeDirArrowExpandable="+"
let g:NERDTreeDirArrowCollapsible="~"

NerdTree provides a graphical view of your file tree:

For the language server, code completion, and static analysis tools, we use coc.vim plugin. This requires NodeJS version 14+ and its package manager NPM.



$ curl -sL https://deb.nodesource.com/setup_14.x | sudo -E bash -
$ sudo apt-get install -y nodejs && sudo apt install npm

Now that we have the prerequisite for coc.nvim, open init.vim and add the following



call plug#begin()
...
Plug 'https://github.com/neoclide/coc.nvim'  " Auto Completion
...
call plug#end()

nnoremap <C-l> :call CocActionAsync('jumpDefinition')<CR>

Head over ~/.config/nvim/plugged/coc.nvim directory and build yarn with the following commands:



$ sudo npm install -g yarn
$ yarn install 
$ yarn build

`CocInstall` example

To be able to configure the linters, we have to install different modules for different languages we're running on. For this example, we will set up Python3. (Make sure that Python3 and Pip3 are installed.)

Install static analysis tool for Python (Jedi is one example but there are also others):



pip3 install jedi

Inside our Python file type: [esc] + :CocInstall coc-python . And there we have it!

Thanks for getting this far and enjoy exploring tools in your terminal!

References

Wikipedia contributors. (2022, August 26). Vim (text editor). In Wikipedia, The Free Encyclopedia. Retrieved 14:12, September 1, 2022, from https://en.wikipedia.org/w/index.php?title=Vim_(text_editor)&oldid=1106761239
Choi, J. (2022). Vim-Plug. https://github.com/junegunn/vim-plug.

Guidelines on importing modules in Python

Dave Amiana — Sun, 06 Feb 2022 14:56:56 +0000

Library support extends our tools to create pieces of software. Because of this, we no longer need to write everything from scratch. To access this set of tools, we need to import modules from Python packages. A Python package is a collection of modules that contain a set of functionalities we may deem useful for our projects.

There are many ways to import a package in Python. I compiled some notes I gathered from The PEP Standard as Google Python Style Guide for pointers to import modules in Python.

Imports should usually be on separate lines.

  import os
  import sys
  # not `import os, sys`

from imports may declare multiple items at once:
```
from typing import Union, Optional
```
- Imports should be grouped in the following order:

Standard library imports.
Related third-party imports.
Local application/library-specific imports.

Imports are always declared at the top of the file.
Absolute imports are recommended.
- They are more readable and tend to be better behaved.
- Explicit relative import is an acceptable alternative to absolute imports, especially when dealing with complex package layouts where using absolute imports would be unnecessarily verbose.
Avoid wildcard imports.
- It clutters the namespace of your code and makes it unclear which names are intended to be present.
- It makes your code confusing and difficult to maintain.

# this will import the namespace of all items contained in the package
from [package/module] import *

# this will import a specified set of items contained in the package
from [package/module] import [item]

Use import statements for packages and modules only, not for individual classes or functions.
```
def function(x:list) -> float:
    import numpy as np
    ...
```

References:

Rossum, G.V., Warsaw, B & Coghlan, N. (2001). PEP 8 – Style Guide for Python Code. https://www.python.org/dev/peps/pep-0008/.
Nzomo, M. (2018). Absolute vs Relative Imports in Python. https://realpython.com/absolute-vs-relative-python-imports/.
Google (n.d.). Google Python Style Guide. https://google.github.io/styleguide/pyguide.html.

Photo by EJ Li on Unsplash

Design Principles of Data Structures Library

Dave Amiana — Wed, 01 Sep 2021 11:13:17 +0000

This article will cover the guiding principle for the design and implementation of our data structures library. Since we form our discussion around C++, most ideas we will talk about came from the design principles of Standard Template Library (STL). Modern libraries have been inspired by the main ideas in STL which was introduced by Alexander Stepanov; It is worth looking at the fundamental notions that guide the development of STL and discuss its design philosophy.

Most of the content of this article is from A. Stepanov's talk on STL Design and Its Principles in 2002. STL was an attempt to organize software in the same manner that we organize knowledge base. The starting point of STL revolves around the notion of generic programming which A. Stepanov and D. Musser (1986) introduced as a paradigm that revolves around the idea of abstracting, efficient concrete algorithms to obtain generic algorithms that can be combined with different data representations. Generic Programming is about abstracting and classifying algorithms and data structures (Stepanov, 1976).

Design Principles

A. Stepanov laid down the fundamental principles that drive the development of STL. We will briefly discuss these principles and translate them into phases of development that we can work with; note that our concern in this series is only limited to data structures and their abstract representation.

Organization of useful set of algorithms and data structures. Since STL is an attempt to organize software components, it took the foundational notion from Computer Science where programs are decomposable to a set of algorithms and data structures. Organizing software components involved finding useful algorithms, implementation of correct and efficient algorithms, and useable classification of algorithms.
Finding the most general representations of algorithms. This idea came from a realization that algorithms share a set of common properties. These properties are drawn from a theoretical field of math known as abstract algebra (Stepanov discusses these ideas in his book for the interested reader). Seeing the most abstract representation of algorithms requires formal specifications that outline its properties and type requirements.
Using whole-part value semantics for data structures. Whole-part semantics guide the semantics of data structures: when a data structure is copied, the whole part of the data structure is copied; when the whole is destroyed, all parts are destroyed. The interface of a data structure should provide access to all the necessary information that represents its meaning and preserves its properties.
Using abstractions of addresses as the interface between algorithms and data structures. A realization of this principle came in the form of an iterator: an abstract reference handle that binds data structures and algorithms.

The above set of principles gave birth to the ideas that revolve around STL: data structures, algorithms, and iterators. Since we concern ourselves with developing data structures, we can only apply the above principles insofar as data structures are concerned. In the implementation of STL, abstract data structures are known as Containers. In this series, I will maintain refer to it as data structures for the following reasons: (1) we are not trying to implement everything that the STL implementation has to offer, and (2) we want to keep the distinction of our implementation from that of STL. We are taking the good ideas behind STL in making our simple library for data structures.

The phases of our development are regarded as follows:

Implement a concrete version of a data structure.
Test implementation.
Specify the correct interface for abstraction.
Abstract the concrete model to represent the general case.

Each of our development phases is documented in this series.

References

Gray. A. (2016). Alexander Stepanov: STL and Its Design principles. https://youtu.be/1-CmNNp5eag.
Musser, D. R. & Stepanov, A. A (1989). Generic Programming. https://bityl.co/8UJW.
Stepanov, A. (1976). Short History of STL. http://stepanovpapers.com/history%20of%20STL.pdf.
Amiana, D. (2021). Iterators: The link between Data Structures and Algorithms. https://bityl.co/8UWP.

Photo by Alena Koval from Pexels

Understanding Abstract Data Types

Dave Amiana — Tue, 31 Aug 2021 10:59:47 +0000

This article introduces what we mean by Abstract Data Types (ADT) and its importance in developing our Data Structures Library. Abstraction is of the essence of a scalable software system. In designing systems, we want to work with higher orders of abstraction in the same way we think about concepts. Navigating ourselves in the space of concepts allows us to see the bigger picture and prevents the possibility of inscrutable code -- a result of unorganized ideas. Put it another way, ADT compels us to think more abstractly.

What is ADT?

In computer science, an ADT is a mathematical model for certain categories of data structure that have commonalities in their semantics of operations. In practical terms, an ADT serves as a blueprint that specifies the operations to be performed in a data structure. As a result, an ADT does not regard implementation details for it only contain a list of specification. For example, let $A$ be a category of data structures that has insert() and remove() operations. We can translate this into a list of specifications:

A:
 - insert(int x) - inserts x in a data structure
 - delete(int x) - deletes x in a data structure

Notice that an ADT describes the specification from the perspective of the user [1]. We can see that an ADT specifies how an insert(int x) and remove(int x) should behave. More formally, an ADT is a set of types, a designated type from that type set, a set of functions, and a set of axioms [1].

In OOP, we may create a representation that captures this idea in a form of a contract. Every data structure that belongs in category $A$ must implement the meaning of remove() and delete() in their respective contexts. That is, $A$ is an abstract concept that contains insert() and delete() operations.

We can understand this better by looking at an executable program.

struct A{
    A() = default;
    virtual ~A() = default;

    virtual void insert(int) = 0;
    virtual void remove(int) = 0;
};

struct B: public A{
    B() = default;
    ~B() = default;

    void insert(int x) override {
        std::cout << "implementation of insert in the context of B. \n"; 
    }
    void remove(int x) override {
        std::cout << "implementation of remove in the context of B. \n"; 
    }
};

struct C: public A{
    C() = default;
    ~C() = default;

    void insert(int x) override {
        std::cout << "implementation of insert in the context of C. \n"; 
    }

    void remove(int x) override {
        std::cout << "implementation of remove in the context of C. \n"; 
    }
};

The notion of context is well-pronounced in the OOP paradigm which justifies why we are using C++ in this series. The above snippet demonstrates how we may write a contract between classes. Note that structs and classes are the same except that struct is public by default while a class is private. Since the above code has no private members, I made use of struct for convenience.

How does ADT help us develop Data Structures?

ADT serves to be our guide in building more abstract concepts. This benefits us from not losing ourselves with the minute details of an ever-growing system of data structures. Mapping our ideas in the space of concepts compels a structure and our responsibility when we implement it is to maintain conceptual consistency.

Maintaining conceptual consistency means that the intention behind operations is deemed appropriate in the context of another data structure. When we remove a value in a list, it should do what we expect it would be: removing an element.

Summary

ADT helps us navigate in the space of concepts; this puts structure into how we may address problems and develop a category of data structures. ADT is devoid of implementation details, rather it talks about the specification of a data structure.

References

La Rocca, M. (2021). Advanced Algorithms and Data Structures. Manning Publications Co. 20 Baldwin Road.
cppreference.com (2021). Structs and Classes. https://en.cppreference.com/book/intro/classes.

Photo by Adrien Olichon from Pexels

Iterators: The link between Data Structures and Algorithms

Dave Amiana — Sun, 29 Aug 2021 03:11:09 +0000

This will introduce the need for implementing iterators in writing a maintainable and flexible data structure.

Before we start the series and actually implement data structures, it is important to motivate our high-level design goals. That said, we want to be able to interface our data structure consistently. The benefit we gain from this is to be able to abstract shared interfaces among categories of data structures. Consequently, algorithms that wish to operate on our data structures may do so with the help of this shared common interface known as Iterators.

Why iterators are important?

An iterator is a particular design pattern that allows one to traverse (or iterate) over a data structure. This pattern decouples algorithms and data structures that mediate their interaction. The inspiration for this can be drawn from the architecture of the C++ Standard Template Library that makes great use of iterators in communicating between algorithms and data structures.

Iterator decouples Data Structures and Algorithms.

We achieve flexible software systems because of iterators. Hold on, how many iterators are there?

The motivation behind crafting an iterator depends on how we want to orient the data structure to our algorithm. Our algorithms may operate as if our data structure is ordered backward with a reverse iterator, we may access elements randomly using random iterator, we may access data sequentially using forward iterator and the list does not end there.

Since we concern ourselves in C++, we make use of pointer semantics for consistently interfacing the data structure as if they were a pointer. Consequently, one may assert that iterators are generalizations of pointers but they have subtle differences in regards to the intent of use. Because iterators are expected to behave like pointers, their interface may guide the semantics of any kind of data structure. In contrast, traversing in a data structure with raw pointers hide the intent of use and often introduce an unnecessary amount of complexity.

Let us consider two cases: first with linear data structures and second with non-linear data structures. For the first case, let us take quick a look at an Array. Think about how we might communicate in an array with pointers and iterators.

std::array<int,3> array {1,2,3,4,5};
std::array<int,3>::pointer array_ptr = array.data();
for(size_t i = 0; i < array.size(); ++i)
    std::cout << array_ptr[i] << '\n';

The above snippet of code demonstrates how we may traverse through an array using a pointer. For a linear data structure, this is trivial. Now consider how this may be written with iterators. There are two ways of doing this, the first part is more explicit while the second part is terser.

std::array<int,3> array {1,2,3,4,5};
for(std::array<int,3>::iterator it = array.begin(); it != array.end(); ++it)
    std::cout << *it << '\n';

std::array<int,3> array {1,2,3,4,5};
for(int&i: array)
    std::cout << i << '\n';

Since all programs result in the same output, it seems that iterators are just a fancy thing that exactly does what we expect a pointer would have. Why do we bother writing iterators if a pointer can suffice its functionality? This question leads us to our second case: traversals in a non-linear data structure.

The above figure is a Binary Search Tree (BST). Since we have not formally introduced this yet, we will take a sneak peek at traversing BST. There are three ways we can do this, and each has a different form of ordering. But let us consider the simplest: in order traversal where we start from the left-most branch resulting to 1,2,3,4,5. Now, imagine using a pointer to walk in our tree.

 void inorder(Node *node) {
   if (node != nullptr) {
     traverse_inorder(node->left);
     std::cout << node->data << " ";
     traverse_inorder(node->right);
   }
 }

The above snippet is a piece of code that is very specific concerning the data structure. It assumes that you have an access to a Node which represents a wrapper on the data. In most cases, we cannot afford this. We want our algorithms to communicate with our data structure seamlessly, and we do this by not imposing the user to know the specifics of our data structure, in this case, BST. Consequently, through iterators, algorithms do not need to know about what data structures they will be performing operations on.

BST<int> bst {1,2,3,4,5};
for(int& i: bst) 
  std::cout << i << '\n';

Suffice to say that iterators behave like pointers in the manner on how they access and traverse a given data structure. But on some occasions, iterators work favorably in accessing more complicated data structures as it separates the internal mechanism and interface which makes using them more intuitive.

Through iterators, algorithms do not need to know about what data structures they will be performing operations on.

In STL, iterators can be accessed using the <iterator> header file (a summary is provided here), but to learn and appreciate iterators, we should know how to write and implement one. Besides, std::iterator has been deprecated since C++17.

Why do we consider writing iterators?

Writing an iterator is a separate skill from writing data structures. The reason why I want to include iterators in our data structure design requirement is twofold:

Iterators abstract the interface which therefore makes our data structure more flexible in welcoming algorithms as we can define the internal mechanisms on how traversals are supposed to work.
Iterator is a fundamental aspect of software design; it is a good practice to know about it.

What we will mostly cover are basic iterators for reading and accessing data.

Summary

Iterators serve to be the shared common interface between data structures. Iterators make our request on data structures more consistent which results in making it more flexible. Consequently, algorithms can communicate without knowing the specific implementation of a data structure because of iterators.

References

Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design Patterns: Elements of Reusable Object-Oriented Software.
cplusplus.com (2021). iterator. https://www.cplusplus.com/reference/iterator/.
cppreference.com (2021). std::reverse_iterator. https://en.cppreference.com/w/cpp/iterator/reverse_iterator.
Boccara, J. (2018). std::iterator is deprecated: Why, What It Was, and What to Use Instead. Fluent {C++}. https://www.fluentcpp.com/2018/05/08/std-iterator-deprecated/.

Photo by Alex Andrews from Pexels

If you enjoyed this content, follow me on my LinkedIn, or subscribe to my newsletter.

Preface: Data Structures

Dave Amiana — Sat, 28 Aug 2021 11:09:31 +0000

Introduction: Mostly about my Experience

I took this course during my sophomore year in Computer Science. I am in my Junior year and I'm currently hacking on languages which I plan to build a series on the design space of compilers someday (fingers crossed). Building a software system like compilers requires you to know a lot about Algorithms and Data Structures, just like anything we encounter in the sea of computation.

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” - Linus Torvalds

As a student of this course, I can remember the fascination and headaches I went through. But it gave me a proper introduction to programming and allowed me to analyze and reason with programs. Overall, it was worth it.

Our professor in this course welcomed us with enthusiasm. It was because of her dedication and compassion that we carry this knowledge. At the time of writing, she passed away. My understanding of this course is indebted to her and other professors that taught us at our University.

I made this series to share with you everything that I have learned throughout the course.

Importance

There are two elementary elements of a program: Data Structures and Algorithms. A data structure affects the functional and structural aspects of our program. Understanding the key properties of data structures and algorithms allows us to use them whenever they are appropriate. A program is a response to a particular problem. Algorithms are computational steps into solving a given problem, while data structures are the structural representation of a problem.

Outline of the series

In this series, we will discuss data structures by developing one. We will walk through the algorithmic steps into achieving a particular state that we want to maintain in a data structure without formally introducing the design space of algorithms for it deserves a separate discussion on its own.

This article will serve as the outline of the series. We follow a consistent format:

Introduction - This section will discuss the concepts behind a data structure and its key properties. This will motivate our design goals and implementation.
Design goals - In this section, we will flesh out the design requirements of our data structure which we shall satisfy in our implementation section.
Implementation - This section translates our design objectives into working code.
Testing - This section will translate our design goals into a series of assertions that we test for our working solution.
Tradeoffs - This section discusses the cost and benefits of a given data structure.
Summary - This section reviews what we had done.
Reference - Citation of references made in the article.

Throughout the series we will discuss the following data structures:

Array-Based - are linear data structures that can be indexed.
- Array
- Vector
- Stack
- Queue
- Deque
- Heap
List-Based - are linear data structures that can only be accessed sequentially.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Stack
- Queue
- Deque
- Circular Queue
Tree-Based - are non-linear data structures that impose ordering.
- BST
- AVL
- RBT
Hash-Based - are non-linear data structures that do not impose order.
- Hash Map
- Hash Set

Our Language

Ideally, this course is language-agnostic. Since I wanted to share with you a peek at implementing data structures, we shall put translate our design goals into an executable programming environment so we can interact with what we built. In this series, I will be using C++, but I have included on my GitHub repository on the implementation of data structures in other languages such as Dart, Java, C#, Swift, and Python.

Schedule

I plan to update this series once a week.

Photo by Jill Burrow from Pexels

Implementing Building Blocks of Reference Semantics: Weak Reference

Dave Amiana — Wed, 25 Aug 2021 10:21:39 +0000

In our last discussion, we talked about the semantics of sharing. We fleshed out the design goals of shared reference and met the minimum design requirements. Similarly, we do the same with our implementation of weak references.

If you followed along with the series, we now know that weak references solve the problem of reference cycles; that is, without weak references, shared reference may be misused, resulting in reference cycles, which results in suppressing resource clean-up.

Once again, let us demonstrate the problem of reference cycles with our shared_reference<T> class.

#include "shared_reference.h"
#include <iostream>

struct B;

struct A{
    shared_reference<B> ab;
    A(){ std::cout << "Resources of A are acquired. \n"; }
    ~A(){ std::cout << "Resources of A are cleaned up. \n"; }
};


struct B{
    shared_reference<A> ba;
    B(){ std::cout << "Resources of B are acquired. \n"; }
    ~B(){ std::cout << "Resources of B are cleaned up. \n"; }
};

int main(){
    shared_reference<A> sa (new A());
    shared_reference<B> sb (new B());

    sa->ab=sb;
    sb->ba=sa;
}

If we compile the above code on the IDE provided below, we encounter the following output.

Resources of A are acquired.
Resources of B are acquired.

It never released our resources at the time our objects went out of scope. This problem should be solved with a weak reference type.

Design goals

Our weak reference class is an extension of shared reference as it can access and modify the contents of our shared reference without imposing its presence on the shared_reference interface. Consequently, we have must satisfy the following requirements:

Must initialize only shared_reference<T> type
Must not take ownership of shared_reference<T> type
Pointer-like interface
Must provide a function of counting references

Implementation

Now that we defined our goals, let us work on them!

Requirement: Must initialize only `shared_reference<T>` type

I found this a little bit tricky to implement. We will find out why it is tricky when we implement a non-owning mechanism. But for now, let us try to partially fulfill our first requirement.

template<typename T> class weak_reference: public shared_reference<T>{
    public:
        explicit weak_reference(shared_reference<T>& i_ptr);
};

This may seem what we meant by an extension of shared reference. And by the looks of it, it may be a plausible assumption until we ran into the problem of calling destructors. Let us discuss the subtle design flaws on this matter in our attempt to suffice the second requirement.

Requirement: Must not take ownership of `shared_reference<T>` type

Before we proceed into anything, let us be clear by what we mean by taking ownership? In the context of shared reference, all entities share ownership with the resource it has; that is, for each time a shared_reference instance goes out of scope, it determines the state on whether calling the resource clean-up would be appropriate. Now, our weak reference should not take ownership of shared_reference's resource. We only need to be able to access and modify its content. In doing so, we need to communicate with the shared_reference class.

To establish communication between classes, we have to make dependencies. That is why our attempts jump back and forth with our shared_reference class. Let us consider our first attempt at establishing dependency with inheritance and discover its design flaws. Consider an adjacent example:

class SuperType{
public:
    SuperType() { std::cout << "SuperType resources are acquired. \n"; }
    virtual ~SuperType() { std::cout << "SuperType resources are released. \n"; }
};

class Subtype: public SuperType{
public:
    Subtype() { std::cout << "Subtype resources are acquired. " << '\n'; }
    ~Subtype() { std::cout << "Subtype resources are released. " << '\n'; }
};

int main() {
    Subtype s;
}

At the time s goes out of scope, it outputs the following:

SuperType resources are acquired. 
Subtype resources are acquired. 
Subtype resources are released. 
SuperType resources are released.

In the above example, we inevitably call the superclass destructor. And we must call its destructor if we want to establish dependency through inheritance, but what does it mean when we decided to extend share reference to weak reference by means for the inheritance? You guessed it! We alter the state of our reference counter and possibly preemptively release our resources because of it.

shared_reference<A> sh_ref(new A());
{
    weak_referene<A> wk_ref(sh_ref);
} // since it calls superclass destructor the clean-up happens here

Let us step back and consider another attempt of establishing dependency. Recall that our concern is to get access to shared_reference's private members. For this case, we can use a friend to access shared_reference's private members without inheriting them.

We declare a friend class inside our shared_reference as follows:

#include "weak_reference.h"

template<typename T> class shared_reference{
  template <typename> friend class weak_reference;
  static size_t m_counter;
  T* m_ptr;
.
.
.
};

Then we write a special constructor that accepts shared_reference and an internal representation of that reference inside our weak_reference class.

# include "shared_reference.h"

template <typename T> class weak_reference{
    T *m_ptr{nullptr};
    shared_reference<T> handle;

  public:
    explicit weak_reference(shared_reference<T>& i_ptr) : 
      m_ptr(i_ptr.get()), 
      handle(i_ptr) 
    {}

    weak_reference() = default;
.
.
.
};

Recall that for each time we call the reference constructor, we call the copy() function that increments the state of our reference counter. Since we do not want to alter the state of our reference counter, we have to counteract the consequences of calling the reference constructor. Inside our shared reference class, we declare a private function that is responsible for suppressing unintended incrementation by calling the reference constructor.

private:
    void suppress_increment(void) noexcept {m_counter -= 1; }
    void suppress_decrement(void) noexcept {m_coutner += 1; }

Since for each time, shared_reference destructor gets called we decrement our reference counter until it is set for clean-up, we need to make sure this will not happen in the context of weak_reference. So we write another private function for suppressing unintended decrementation.

In effect, our weak reference will not alter the state of the reference counter and we have got ourselves a representation of shared_reference which we shall exploit later.

Requirement: Pointer-like interface

We need an interface to communicate with the state of our unique reference. For consistency, it has to resemble the interface of a pointer.

Recall that a pointer can be dereferenced with * and -> operators. And we need & operator to inspect the location of our pointer in memory. These are the basic operators we need to overload for our unique reference. To do this, we write:

    T &operator*(void) { return *(this->m_ptr); }
    T *operator->(void) { return this->m_ptr; }
    T &operator&(weak_reference<T> &other) { return other.m_ptr; }

Let us walk through the three lines.

The first line returns a reference of *(this->m_ptr) which means that the content of m_ptr is accessed that which we can modify and read. The same idea goes with the arrow operator, we return a pointer to m_ptr's location in memory. The last operator is slightly different in that it returns the address of the pointer and not the referent. Recall that a pointer has its own location in memory separate from the entities it points to.

Let's go beyond our requirement list and add little features that return the current count of our references and their contents. We call these functions count(), is_expired(), and release(). The implementation is equally trivial.

Requirement: Must provide a function of counting references

Since we have an internal representation of shared reference, we can inspect the state of its reference counter and check if our resources have been released. Additionally, we may want our weak reference to release its handle on shared reference resources. These functionalities are handled by the following public functions:

    int count(void){ return handle.count(); }
    void release(void) noexcept { m_ptr = nullptr; }
    bool is_expired(void) noexcept { return m_ptr == nullptr; }

Putting it all together

# pragma once
# include "shared_reference.h"

template <typename T> class weak_reference{
    T *m_ptr{nullptr};
    shared_reference<T> handle;

  public:
    explicit weak_reference(shared_reference<T>& i_ptr) : 
      m_ptr(i_ptr.get()), 
      handle(i_ptr) 
    {i_ptr.suppress_increment();}

    weak_reference() = delete;
    weak_reference(const weak_reference<T> &) = delete;
    weak_reference(weak_reference<T> &&) = delete;
    ~weak_reference() { 
      m_ptr = nullptr;
      handle.suppress_decrement(); 
    }

    weak_reference &operator=(weak_reference<T> &&) = delete;
    weak_reference &operator=(const weak_reference<T> &Type) = delete;

    T &operator*(void) { return *(this->m_ptr); }
    T *operator->(void) { return this->m_ptr; }
    T &operator&(weak_reference<T> &other) { return other.m_ptr; } 

    T *get(void) { return (this->m_ptr); }
    int count(void){return handle.count();}

    void release(void) noexcept { m_ptr = nullptr; }
    bool is_expired(void) noexcept { return m_ptr == nullptr; }
};

Test cases

Time to see if we satisfied our design requirements:

In the executable program above, we noticed that weak references solve the reference cycle problem.

Summary

We fleshed out our design requirements and implemented our version of the weak reference to satisfy what we intend to do with it. We extended the capability of shared reference by extending its features with weak reference whereby we successfully solved the reference cycle problem.

Here ends the ownership semantics series! I hope you carry along with you the new things we learned regarding resource management.

As always, have fun hacking!

References

Wikipedia contributors. (2021, July 29). Reference counting. In Wikipedia, The Free Encyclopedia. Retrieved 08:48, August 25, 2021, from https://en.wikipedia.org/w/index.php?title=Reference_counting&oldid=1036113247
Amiana, D. (2021). Implementing Building Blocks of Reference Semantics: Shared Reference. https://dcode.hashnode.dev/implementing-building-blocks-of-reference-semantics-shared-reference
cppreference.com (2021). Friend. https://en.cppreference.com/w/cpp/language/friend.

Implementing Building Blocks of Reference Semantics: Shared Reference

Dave Amiana — Fri, 20 Aug 2021 12:23:55 +0000

In our previous discussion, we fleshed out the design requirements and took action into servicing them. In the same way, this article aims to flesh out the design requirement for shared reference.

Shared references make use of a reference counting mechanism that allows resources to be shared in different parts of the program. In some cases, this technique replaces the need for garbage collection as reference counting automatically cleans up the resources at the time it hits 0.

The implementation of shared references has a performance cost which led implementers of garbage collection (GC) algorithms to weigh their choices in implementing automatic resource management. Dynamic languages such as Java, C#, and Dart implement more sophisticated GC's to minimize the cost of developing applications. Some languages relied on reference counting techniques like C++ and Rust for system-level programming. And some languages like Python make use of both in combination. We can observe that the decision of choosing a resource management system depends on the intended use of the language. For instance, C++ supported smart pointers for automatic reference management while allowing manual resource management through raw pointers because the language is aimed at servicing problems that exist from the level of the silicon to the highest levels of abstraction -- that is why C++ provide resource-safe automation and manual resource management.

Before we implement our shared reference class, let first us discuss the advantages and disadvantages of implementing reference counting (RC).

Advantages

RC guarantees that resources are cleaned up as soon as their last reference is destroyed.
RC is deterministic through RAII.
RC is relatively simple to implement over more sophisticated GC algorithms.

Disadvantages

RC may leak resources in case of reference cycles.
RC has space overhead for reference counting.
RC is difficult to deal with in a multithreaded environment since it requires atomicity.

Note that the disadvantages vary in the sophistication of RC implementation. In our last discussion, we showed the problem of reference cycles and resolved this by std::weak_ptr<T>. We will review this problem and work through solving the problem of reference cycles by implementing a weak_reference class.

In the meantime, let us focus on implementing our simple model of shared reference.

Design Goals

Let us flesh out our design requirements. Our shared_reference class must satisfy the following:

Must accept any types
Automatic Resource Management
Reference counting
Pointer-like interface

Implementation

Now, we translate the design requirements into code. We will build up from it one by one.

Requirement: Must Accept any Type

This is trivial, but let us include it here. To put this into code, we simply make use of template parameters as follows:

template <typename T> class shared_reference;

Simple right? Let's keep going!

Requirement: Automatic Resource Management and Reference Counting

The idea is to make use of RAII -- a programming idiom that gives us guarantees with resource-safe management. We simply need to fill out the resource acquisition upon construction and resource clean-up upon destruction. RAII is achieved through constructor-destructor pairs which are triggered to keep track of the object's lifetime.

template<typename T> class shared_reference{
T* m_ptr{nullptr};
public:
  shared_reference() = default;

   ~shared_reference(){
      if(m_ptr != nullptr){
          m_ptr->~T();
        m_ptr = nullptr;
      }
    }
};

That seems, reasonable. We initialized m_ptr to null and we successfully cleaned up our resources at the time it went out of scope. But that is what we did with unique_reference, right? How is shared reference any different?

The answer lies with the reference counting mechanism. To extend the lifetime of our objects, we have to know when it is appropriate to perform our clean-up. As mentioned, we perform our clean-up in the case where our reference count is 0. Now that we get the idea, let us put this in code.

template<typename T> class shared_reference{
  size_t m_counter{1};
  T *m_ptr{nullptr};

public:
  shared_reference() = default; 

  ~shared_reference() {
    m_counter -= 1;
    if (m_counter == 0) {
      m_ptr->~T();
      m_ptr = nullptr;
    }
};

The idea is to count how many instances that refer to m_ptr are still active. With RAII, we can delegate this role to our constructor; that is, for each time it creates an instance of shared_reference it has to increment m_counter and for each time it goes out of scope, it has to decrement and check if it is time for clean-up. Let's write a copy constructor and a special constructor that takes in a T* parameter.

shared_reference() = default;
explicit shared_reference(T* i_ptr): m_ptr(i_ptr){}
explicit shared_reference(shared_reference<T>& rhs){
  rhs.m_ptr = m_ptr;
  rhs.m_counter = m_counter + 1;
}

We want to tell the compiler that it is not free to deduce the default constructor in the case where we need our class to initialize the user has to explicitly bind the content of its referent.

Our copy constructor is not technically a copy-constructor because at the time we pass shared_reference<T>& we only want it to share the contents of m_ptr and increment m_counter. What we want is to provide an interface for sharing references. To avoid confusion, I will refer to shared_reference(shared_reference<T>&) as a reference constructor.

But if we want to transfer the ownership to another entity and we don't want it to have shared access to it anymore? This is the responsibility of our move constructor.

shared_reference(shared_reference<T>&& rhs) noexcept {
  std::swap(m_ptr, rhs.m_ptr);
  rhs.m_counter = 1;
}

Notice that we initialized rhs.m_counter to 1 and not swapped the values of m_counter, this is because we want to re-initialize the counter when it is transferred.

That seems correct. But we ran into deep trouble when we decided to test this. Let us consider the following assertions:

shared_reference<AnyType>ptr_0(new AnyType());
{
shared_reference<AnyType>ptr_1(ptr_0);
  {
    shared_reference<AnyType>ptr_2(ptr_1);
  }
}

For each time we instantiate an object, we reserve a representation of our model and record the states of its instances. But we do not share the states of our instances. So each time we call our reference constructor, we are actually populating unrelated state changes with our instances.

That is a subtle bug, not a feature!

What we actually want is to have a common ground for communication that updates all the instances of shared_reference<T> each time it goes out of scope. So, it seems reasonable to use static members. Let's add the assignment overloads and debug!

template<typename T> class shared_reference{
  static size_t m_counter;
  T* m_ptr;

  public:
    shared_reference() = default;
    explicit shared_reference(T* i_ptr): m_ptr(i_ptr){}
    explicit shared_reference(shared_reference<T>& rhs) noexcept
      {rhs.copy(*this); }
    explicit shared_reference(shared_reference<T>&& rhs) noexcept 
      {rhs.swap(*this); }  

    ~shared_reference(){
      m_counter -= 1;
      if(m_counter == 0){
        m_ptr->~T();
      }
    }

    T &operator=(shared_reference<T>& rhs)noexcept {
        rhs.copy(*this);
        return *this; 
    }
    T &operator=(shared_reference<T>&& rhs) noexcept {
        rhs.swap(*this); 
        return *this;
    }

  private:
    void copy(shared_reference<T>& rhs) noexcept{
      m_counter += 1;
      rhs.m_ptr = m_ptr;
    }
    void swap(shared_reference<T>& rhs) noexcept {
      std::swap(m_ptr, rhs.m_ptr);
    }
};

template<typename T> 
size_t shared_reference<T>::m_counter = 1;

We did it! We hit two birds with one stone. Let's work on the pointer-like interface!

Requirement: Pointer-like Interface

We need an interface to communicate with the state of our unique reference. For consistency, it has to resemble the interface of a pointer.

  T &operator*(void) { return *(this->m_ptr); }
  T *operator->(void) { return this->m_ptr; }
  T &operator&(shared_reference<T> &other) { return other.m_ptr; }

Let us walk through the three lines.

Let's go beyond our requirement list and add little features that return the current count of our references and their contents. We call these functions count(), and get(). The implementation is equally trivial.

Putting it all together

template<typename T> class shared_reference{
  static size_t m_counter;
  T* m_ptr;

  public:
    shared_reference() = default;
    explicit shared_reference(T* i_ptr): m_ptr(i_ptr){}
    explicit shared_reference(shared_reference<T>& rhs) noexcept
      {rhs.copy(*this); }
    explicit shared_reference(shared_reference<T>&& rhs) noexcept 
      {rhs.swap(*this); }  

    ~shared_reference(){
      m_counter -= 1;
      if(m_counter == 0){
        m_ptr->~T();
      }
    }

    shared_reference<T> &operator=(shared_reference<T>& rhs)noexcept {
      rhs.copy(*this);
      return *this; 
    }

    shared_reference<T> &operator=(shared_reference<T>&& rhs) noexcept {
      rhs.swap(*this);
      return *this;  
    }

    T &operator*(void) { return *(this->m_ptr); }
    T *operator->(void) { return this->m_ptr; }
    T &operator&(shared_reference<T> &other) { return other.m_ptr; }
    T *get(void) { return this->m_ptr; } 
    size_t count() const { return m_counter; }

  private:

    void copy(shared_reference<T>& rhs) noexcept{
      m_counter += 1;
      rhs.m_ptr = m_ptr;
    }

    void swap(shared_reference<T>& rhs) noexcept {
      std::swap(m_ptr, rhs.m_ptr);
      rhs.m_counter = 1;
    }
};

template<typename T> 
size_t shared_reference<T>::m_counter = 1;

Test Cases

Time to see if we satisfied our design requirements:

Summary

We fleshed out our design requirements and implemented our version of the shared reference to satisfy what we intend to do with shared references. Upon testing, we found that it sufficiently did what we want it to do: we now have the second piece of our automatic resource management!

Since we implemented a simple shared resource management, think about how you can extend this to support indexing in an array structure.

Have fun hacking!

References

Wikipedia contributors. (2021, June 29). Garbage collection (computer science). https://en.wikipedia.org/w/index.php?title=Garbage_collection_(computer_science).
Oracle (n.d.). Java Garbage Collection Basics. https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html.
Microsoft Docs (2020). Background garbage collection. https://docs.microsoft.com/en-us/dotnet/standard/garbage-collection/background-gc.
Mrale.ph (n.d.). Introduction to Dart VM. https://mrale.ph/dartvm/.
Rust (n.d.). Module alloc::rc. https://doc.rust-lang.org/alloc/rc/.
cppreference.com (2021). std::shared_ptr. https://en.cppreference.com/w/cpp/memory/shared_ptr.
Debrie, A. (2021). Python Garbage Collection: What It Is and How it works? https://stackify.com/python-garbage-collection/.
Microsoft Docs (2020). Welcome back to C++ - Modern C++. https://bityl.co/8HD7.
cppreference.com (2021). static members. https://en.cppreference.com/w/cpp/language/static.

Implementing Building Blocks of Reference Semantics: Unique Reference

Dave Amiana — Tue, 17 Aug 2021 08:45:50 +0000

Our previous discussion explores the anatomy of pointer types in C and C++ on par with hinting nuances of reference semantics. We discussed the use cases of raw pointers and smart pointers in modern C++ and found that there are degrees of aptness in choosing between automatic resource management over manual resource management. More specifically, we introduced std::unique_ptr<T> and demonstrated some of its functionalities.

This article discusses the design goals and implementation of std::unique_ptr<T>. However, instead of discussing the intricacies of the STL implementation in different C++ compiler distributions, we simplify this to express the design goals of a unique reference.

At the end of this article, we develop another layer of understanding with the functionalities of unique reference and implement our version of it.

Design goals of unique reference

Let us list down the requirements we must satisfy for implementing our version of the unique reference. Our implementation must satisfy the following.

Must accept any type
Automatic resource management
Maintain the property of uniqueness
Pointer-like interface

Our simple version of the std::unique_ptr<T> requires to be explicitly initialized with the object it refers to.

Implementation

Let us build up our implementation by fulfilling our design requirements one by one.

Requirement: Must Accept any Type

We begin with the simplest requirement It must take any type. We simply have to add a template parameter to our type (class) for this requirement to suffice this.

template<typename T> class unique_reference;

That's it! We satisfied our first requirement.

Requirement: Automatic Resource Management

This is the elegant solution of the C++ abstraction mechanism that comes in: the answer is Resource Acquisition Is Initialization or RAII.

RAII provides guarantees regarding the state of our class. Resource management is tied with class invariance the lifetime of an object. This is achieved by object constructors and destructors which are responsible for initialization and clean-up of resources.

template<typename T> class unique_reference{
T* m_ptr{nullptr};
public:
  unique_reference() = default;

  ~unique_reference() {
    delete m_ptr; // seems right, but dangerous!
    m_ptr = nullptr;
  }
};

The constructor is triggered when an instance of unique_reference is initialized -- that is why in other languages like Python, and Swift, these are known as initializers. Meanwhile, destructors are triggered when an instance of unique_reference goes out of scope. Together, they serve our need for automatic resource management that gives us deterministic behavior which guarantees resource management. The deterministic behavior of our reference management gives superior property over implementing garbage collectors which may or may not clean up a piece of resource at the time an object went out of scope.

It seems that we managed our resources well. We initialized our pointer to nullptr upon construction and de-initialized it by deleting the contents of m_ptr. However, there is a subtle element of trouble that we still might leak our resources, even after setting m_ptr = nullptr. The compiler will not warn you with this, but you are shooting yourself in the foot.

To resolve this, we need to re-think our mental model of unique reference. At the time our object goes out of scope we want to destroy the object, not necessarily delete them abruptly. So we call the object's destructor ~T().

Note that types that do not have user-provided destructors such as primitives are marked as * trivial destructors *, which is why ~T() is valid for primitives.

template<typename T> class unique_reference{
T* m_ptr{nullptr};
public:
  unique_reference() = default;

    ~unique_reference(){
      if(m_ptr != nullptr){
        m_ptr->~T();
        m_ptr = nullptr;
      }
    }
};

We're doing great. Let's keep going!

Requirement: Maintain Property of Uniqueness

For this, we want our unique reference to be able to transfer its ownership inside a function or a class when need be. By implementing the mechanism of transference, we need to maintain the property of uniqueness. We do so by incorporating move semantics. There are two parts for enabling moveable ownership, our unique reference has to be: move constructible, and move assignable.

Let us work with our moveable constructors first.

  explicit unique_reference(unique_reference<T> &&other) noexcept {
    std::swap(other.m_ptr, m_ptr);
  }

Let us walk through what we are actually saying with the above snippet of code. First, we need to mark our constructors as explicit to avoid unexpected implicit conversions. Then we make use of * rvalue reference * for our parameter which marks our class as move constructible. But before we handle move construction, we have to guarantee that upon construction we will not throw exceptions so we mark our noexcept specifier.

The body of our function is very trivial to implement. We want to take all the resources of our moved-from reference (other), and swap it with our moved-in object (this). That said, the second requirement (move assignable) is equally trivial to implement. We simply need to overload the assignment operator.

  unique_reference &operator=(unique_reference<T> &&other) noexcept {
    std::swap(other.m_ptr, m_ptr);
    return *this;  
  }

We are essentially repeating the body of our assignment and constructor, so for consistency, let us implement a little helper function we declare in private which shall be responsible for swapping the objects.

private:
  void swap(unique_reference<T> &other) noexcept {
    std::swap(m_ptr, other.m_ptr);
  }

Effectively, this results to:

  explicit unique_reference(unique_reference<T> &&other) noexcept {
    other.swap(*this);
  }
  / ... /
  unique_reference& operator=(unique_reference<T> &&other) noexcept {
    other.swap(*this);
    return *this;
  }

Since we are discussing the constructors and assignment operators it is a good point to note about how to suppress them and why. The reason we want to suppress constructors are two folds: we want to explicitly mention that we do not intend this to happen, and we want the compiler to check if users try to access such modalities.

To do this, we simply write:

  explicit unique_reference(const unique_reference<T> &Type) = delete;
  unique_reference& operator=(const unique_reference<T> &other) = delete;

Here, we suppressed copy-assignment and copy-construction since copying will defy the meaning of being unique.

Requirement: Pointer-like Interface

We need an interface to communicate with the state of our unique reference. For consistency, it has to resemble the interface of a pointer.

  T &operator*(void) { return *(this->m_ptr); }
  T *operator->(void) { return this->m_ptr; }
  T &operator&(unique_reference<T> &other) { return other.m_ptr; }

Let us walk through the three lines.

Putting it all together:

template <typename T> class unique_reference {

public:
  T *m_ptr{nullptr};
  explicit unique_reference() = default;
  explicit unique_reference(const unique_reference<T> &Type) = delete;

  explicit unique_reference(T *Type) : m_ptr(Type) {}
  explicit unique_reference(unique_reference<T> &&other) noexcept {
    other.swap(*this);
  }

  unique_reference &operator=(const unique_reference<T> &other) = delete;
  unique_reference &operator=(unique_reference<T> &&other) noexcept {
    other.swap(*this);
    return *this;
  }

  ~unique_reference() {
    if (m_ptr != nullptr) {
      m_ptr->~T();
      m_ptr = nullptr;
    }
  }

  T &operator*(void) { return *(this->m_ptr); }
  T *operator->(void) { return this->m_ptr; }
  T &operator&(unique_reference<T> &other) { return other.m_ptr; }

private:
  void swap(unique_reference<T> &other) noexcept {
    std::swap(m_ptr, other.m_ptr);
  }
};

Test Cases

Time to see if we satisfied our design requirements:

Summary

We fleshed out our design requirements and implemented our version of the unique reference to satisfy what we intend to do with unique references. Upon testing, we found that it sufficiently did what we want it to do: we now have the first piece of our automatic resource management!

Since that we implemented a simple unique reference class, try to think about how we can extend this for an array-like interface as your homework. Doing this part on your own gives you room to re-think what we did with our unique_reference.

Have fun hacking!

References

Wikipedia contributors. (2021, May 21). Resource acquisition is initialization. In Wikipedia, The Free Encyclopedia. Retrieved 07:06, August 17, 2021, from https://en.wikipedia.org/w/index.php?title=Resource_acquisition_is_initialization&oldid=1024395395.
Python (2021). Python Initialization Configuration Reference Manual. https://docs.python.org/3/c-api/init_config.html.
Swift (2021). Swift Language Guide. https://docs.swift.org/swift-book/LanguageGuide/Initialization.html.
cppreference.com (2021). Destructors. https://en.cppreference.com/w/cpp/language/destructor.
cppreference.com (2021). Fundamental types. https://en.cppreference.com/w/cpp/language/types.
StackOverflow (2010). What is move semantics? https://stackoverflow.com/questions/3106110/what-is-move-semantics.
StackOverflow (2009). What does the explicit keyword mean? https://stackoverflow.com/questions/121162/what-does-the-explicit-keyword-mean.
Triangles (2019). C++ rvalue references and move semantics for beginners. https://www.internalpointers.com/post/c-rvalue-references-and-move-semantics-beginners.
Amiana, D. (2021). Pointers and References: Design Goals and Use Cases. https://dcode.hashnode.dev/pointers-and-references-design-goals-and-use-cases.

On Pointer Types: Peeking at Reference Semantics

Dave Amiana — Thu, 12 Aug 2021 03:17:40 +0000

In this article, I aim to introduce the concept and motivation behind using pointers. There are breeds of C++ developers that only use smart pointers for safety reasons, others that only use raw pointers for performance benefits, and some that use both whenever they provide the utmost benefits. In this article, I aim to highlight the use-cases of pointers so you can decide when to use one.

Conceptually, a pointer is a kind of reference. That is, a pointer refers to a certain block of memory of which acts as an entry point. To access the contents or modify the value of a pointer, we dereference it. Many languages have pointer-like features. Our concern revolves around the context of C and C++. Note that all C functions are valid in C++ but the opposite is not true. For this reason, our section on smart pointers is only applicable to C++.

Pointers are the basic structure to achieve reference semantics. Pointers are handy for naming another entity to be attributed by the contents of the referent entity. A pointer may access and manipulate the contents of the entity that it is pointed to, consider:

int x = 5;
int *y = &x;
*y = 10;

Pointers are introduced in C for the following reasons:

Inexpensive parameter passing.
Allocate memory for new objects on the heap.
Passing a function reference to a function.
Iterate over data structures.

The same thing is true in C++. In fact, iterators (a component for iterating over C++ Containers) resemble the interface of a pointer. But C++ has more to offer with a different set of modalities one can express reference semantics. We will focus on the set of reference modalities known as smart pointers. But before that, let us present a compelling reason for using smart pointers by enumerating the problems of raw pointers.

Raw Pointers

Raw pointers are low-level types that pertain to a certain block of memory. As mentioned, pointers are entry points to access a value or modify it in a specific location in memory.

Some languages have restrictions on pointer types to a varying degree. For example, Ada initializes a default value of their pointer types to null and makes a restriction for type conversions involving pointers mostly for type safety. While languages like Java have banned the use of low-level pointer types to reduce programming error.

Therein creeps in the subtle shades of pointers. Now we ask what is the scene of pointer types in C?

In languages like C and C++, pointer types are very much used for low-level programming. Type conversion of pointer types has a varying degree of restrictions. In C, void * types are considered as raw pointer types which can be morphed into any type by an operation called typecasting.

void* function(int& i){return &i; }

int main(){
    int i = 10;
    std::cout << *((int*)function(i));
}

The above snippet demonstrates that a void * type can be cast into an int *, or any type in that regard. Albeit not apparent with the above example, this is useful for abstraction which is a matter that we will not talk about here.

Raw pointers are concrete implementation of the more abstract concept of reference. Unlike Ada, raw pointers in C/C++ are not initialized in a null value, although they can refer to null which is a safer way of using raw pointers: if not initialized with the address of a referent, initialize it with nullptr (in C++) and NULL (in C). The reason behind this is to achieve well-defined behavior and avoid bugs that can be very difficult to fix, let alone find.

Raw pointers will not impose anything so misusing or abusing it are very easy to commit.

The Dangling Problem:

Let us consider an instance that we are likely to encounter the dangling pointer problem. Let's take a look at allocating and deallocating resources using new and delete function in C++ and malloc (calloc) or free in C.

int main(){
    // (int*)malloc(sizeof(int)) or (int*)calloc(1, sizeof(int)) in C
    int* i = new int(100); 
    std::cout <<"contends of i: "<<  *i << '\n';
    std::cout <<"address of i: " << &i << '\n';
    // free(i) in C
    delete i;
    std::cout <<"contents of i: " <<*i << '\n';
    std::cout <<"address of i: " << &i << '\n';
}

Note that delete or free functions only removes the contents of an entity, in this case, i. That is, dereferencing i still returns the memory location of i before it was deleted. This is problematic for it may introduce undefined behavior: dereferencing to an already freed memory is dangerous. To resolve this, we have to make sure that the i references to a well-defined location in memory hence we put i = nullptr (in C++) and i = NULL (in C) after deleting the contents of i to avoid critical mistakes.

int main(){
    int* i = new int(100);
    std::cout <<"contends of i: "<<  *i << '\n';
    std::cout <<"address of i: " << &i << '\n';
    delete i;
    i = nullptr;
    std::cout <<"contents of i: " <<*i << '\n';
    std::cout <<"address of i: " << &i << '\n';
}

Another problem comes with determining the owning pointer which can result in serious issues from resource leaks, undefined behaviors to security vulnerabilities. Which pointer is responsible for which entity? It is difficult to keep track of multiple references and make sure that at the end of the scope such references are correctly managed. There has to be a clear expression to determine the owning pointer. Because of this, C++ introduced a reference management system that revolves around the idea of RAII.

Smart Pointers

From the C++ Standard :

Enforcing the lifetime safety profile eliminates leaks. When combined with resource safety provided by RAII, it eliminates the need for “garbage collection” (by generating no garbage). Combine this with enforcement of the type and bounds profiles and you get complete type- and resource-safety, guaranteed by tools.

C++ introduced a set of classes for automatic resource management with very minimal to zero-cost performance penalties. Using these set of pointers has the following set of benefits:

clarity of expressing ownership
guarantees that resources will not leak

When appropriate, we should be using smart pointers for clearly expressing our intent with the kind of ownership we want to establish between the pointer and the entity it refers to. We have three smart pointers: std::unique_ptr<T>, std::shared_ptr<T>, and std::weak_ptr<T>. We can access these modalities in the <memory> header file.

Let us walk through and discover what these reference modalities have to offer. For our demonstration let us consider a class named Entity defined as:

class Entity{
    const char* str = "message from Entity. \n";
    public:
        Entity(){ std::cout << "Resources of Entity are acquired. \n"; }
        ~Entity(){ std::cout << "Resources of Entity is cleaned up. \n"; }

        const char* function(void){ return str; }
};

Unique Pointer

Unique pointer maintains that there is only one pointer responsible for a given resource in memory. The owning pointer is responsible for the clean-up and resource management.

Let us define an instance of Entity.

std::unique_ptr<E> e (new Entity());

Now, let us consider passing the pointer by reference and with move constructors to see its effect on where Entity is destroyed. Passing the unique pointer by reference means that the unique pointer is extended to a function, hence the clean-up happens after the unique pointer goes out of scope from the main function where it has been declared.

void f(std::unique_ptr<Entity>& entity){
    std::cout << entity->function();
}

int main(){
    std::unique_ptr<Entity> e(new Entity());
    f(e);
    std::cout << "... \n";
}

Resources of Entity are acquired.
message from Entity.
...
Resources of Entity is cleaned up.

Passing the unique pointer with move constructors is transferring ownership to the unique pointer defined in function f(). We can notice the behavior has we run the following snippet:

void f(std::unique_ptr<Entity> entity){
    std::cout << entity->function();
}

int main(){
    std::unique_ptr<Entity> e(new Entity());
    f(std::move(e));
    std::cout << "... \n";
}

Resources of Entity are acquired.
message from Entity.
Resources of Entity is cleaned up.
...

Since we transferred the ownership of e to entity, the clean-up happened as soon as the entity exits the function.

Shared Pointer

The shared pointer has an additional mechanism called reference counting where it keeps track of pointers that request for sharing resources. Each time another pointer asks for shared resources, the reference counter adds one and for every time it goes out of scope it removes one. At the time where the reference count is 0, it calls for the clean-up. We can observe this mechanism with the following code snippet:

void f(std::shared_ptr<Entity> entity){
    std::cout<<"ref count: " << entity.use_count() << '\n';
    std::cout << entity->function();
}

int main(){
    std::shared_ptr<Entity> e(new Entity());
    std::cout<<"ref count: " << e.use_count() << '\n';
    f(e);
    std::cout << "f went out of scope. \n";
    std::cout <<"ref count: " <<e.use_count() << '\n';
    std::cout << "... \n";
}

Resources of Entity are acquired.
ref count: 1
ref count: 2
message from Entity.
f went out of scope.
ref count: 1
...
Resources of Entity is cleaned up.

When I first encountered this, I thought that is all I need, unique pointers and shared pointers are all there is to it. Until I encountered this problem called circular references where the troubles of shared references kick in. It is possible to break the guarantees of the shared pointer by forming a loop of circular references which results in resource leaks.

The Circular Reference Problem

A circular reference has the form $\to B, B\to A$ . Let us put this into code.

struct B;

struct A{
    std::shared_ptr<B> ab;
    A(){ std::cout << "Resources of A are acquired. \n"; }
    ~A(){ std::cout << "Resources of A are cleaned up. \n"; }
};


struct B{
    std::shared_ptr<A> ba;
    B(){ std::cout << "Resources of B are acquired. \n"; }
    ~B(){ std::cout << "Resources of B are cleaned up. \n"; }
};

int main(){
    std::shared_ptr<A> sa (new A());
    std::shared_ptr<B> sb (new B());

    sa->ab=sb;
    sb->ba=sa;
}

Resources of A are acquired.
Resources of B are acquired.

Since $\to B$ and $\to A$ , the reference count will never resolve to zero -- the condition which std::shared_ptr<T> does its clean-up. We can observe the reference counts by theuse_count() function. Let is modify the main function:

int main(){
    std::shared_ptr<A> sa (new A());
    std::shared_ptr<B> sb (new B());

    sa->ab=sb;
    std::cout << "count of ab: " << sa->ab.use_count() << '\n';
    sb->ba=sa;
    std::cout << "count of ba: " << sb->ba.use_count() << '\n';
}

Resources of A are acquired.
Resources of B are acquired.
count of ab: 2
count of ba: 2

How do we break the curse? Introducing Weak Pointers.

Weak Pointer

A weak pointer is a special type of pointer in conjunction with shared pointers. With weak pointers, you can access the contents of the shared pointer without increasing the reference count. This is useful for observing the contents of a shared resource and most notably resolving the problem of circular reference.

Let us solve the problem of circular reference through weak pointers. This can be achieved by modifying either A::ab or B::ba pointers.

struct A{
    std::shared_ptr<B> ab;
    A(){ std::cout << "Resources of A are acquired. \n"; }
    ~A(){ std::cout << "Resources of A are cleaned up. \n"; }

};


struct B{
    std::weak_ptr<A> ba;
    B(){ std::cout << "Resources of B are acquired. \n"; }
    ~B(){ std::cout << "Resources of B are cleaned up. \n"; }
};

int main(){
    std::shared_ptr<A> sa (new A());
    std::shared_ptr<B> sb (new B());

    sa->ab=sb;
    std::cout << "count of ab: " << sa->ab.use_count() << '\n';
    sb->ba=sa;
    std::cout << "count of ba: " << sb->ba.use_count() << '\n';
}

Resources of A are acquired.
Resources of B are acquired.
count of ab: 2
count of ba: 1
Resources of A are cleaned up.
Resources of B are cleaned up.

Summary

C++ does not use automatic reference management by default following their design philosophy of the zero-overhead principle. One can enable automatic reference management in C++ by making use of smart pointers defined in the standard library. It gives you resource guarantees and safety. Other languages such as Swift and Rust have adhered to the same concept instead of making sophisticated garbage collectors, they do not produce any garbage at all. This memory management model makes a very compelling case of using smart pointers. But raw pointers still have their brightest moments up to date.

Prefer using pointers for performance-critical loops or when the scope is clear enough to determine which is the owning pointer for a given resource. Raw pointers give you few performance benefits, but it comes with the cost of manually keeping track of your pointers, resource safety becomes your responsibility.

Prefer using smart pointers for expressing ownership clearly. Smart pointers give you resource guarantees which get rid of your task to make sure that there will be no leaks.

The standard recommends the following:

Look at pointers: Classify them into non-owners (the default) and owners. Where feasible, replace owners with standard-library resource handles (as in the example above). Alternatively, mark an owner as such using owner from the GSL.
Look for naked new and delete
Look for known resource allocating functions returning raw pointers (such as fopen, malloc, and strdup)

References

Barnes, J. (2005). Safe Pointers. AdaCore. Retrieved from: https://www.adacore.com/uploads_gems/03_safe_secure_ada_2005_safe_pointers.pdf.
Computerphile (2017). Why C is so Influential? Retrieved from: https://www.youtube.com/watch?v=ci1PJexnfNE.
Microsoft Docs (2020). Raw Pointers (C++).
Microsoft Docs (2020). Smart Pointers (Modern C++).
Microsoft Docs (2019). Object lifetime and resource management (RAII).
Stroustrup, B. & Sutter, H. (2021). C++ Core Guidelines. Retrieved from: http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#???
Stroustrup, B. (2013). The C++ programming language. Pearson Education.

Pointers and References: Design Goals and Use Cases

Dave Amiana — Wed, 04 Aug 2021 08:23:36 +0000

At first, it seems that C++ makes things more complicated by introducing yet another layer of abstraction. References seem to encapsulate the same set of functionalities as pointers. Both of these constructs are used to refer to another entity as they provide access points into manipulating the contents of the referent entity; they are both allocated on the heap.

With this, we are faced with the following questions:

Are pointers and references the same thing?
Are there any techniques that pointers can only do and vice-versa?
When do we favor pointers over references and vice-versa?

By the end of this article, I hope to disentangle these two concepts and aim to give a reason why references deserve their own right for building more robust higher-order concepts.

Pointers

Pointers are introduced in C. Pointers store the memory address of an entity of type T (where T is a template parameter that can be resolved to any types), as mentioned, it provides an access point for changing the values of the entity it points to. Consider the following snippet:

#include <iostream>

int main(){
    int x  = 10; // sets the content of x to 10.
    int *y = &x; // sets the pointer to the address of x
    *y = 5; // changes the content of &x to 5.

    std::cout <<  x  <<  '\n'; // outputs to content of x that is 5.
    std::cout << y << '\n'; // outputs the memory address of x.
    std::cout << &x << '\n'; // outputs the memory address of x.
}

Pointers are great for making use of indirections that manipulate the contents within a certain block of memory. Let us modify the above code to demonstrate a series of indirection as follows:

#include <iostream>

int main(){
    int x = 10;
    int *y = &x;
    int *z = y; // takes the address of y i.e. &x.
    *z = 6;  // changes the content of &x. 

    std::cout << x << '\n';
    std::cout << &x << '\n';
    std::cout << y << '\n';
    std::cout << z << '\n';
}

We can extend this by nesting them together:

#include <iostream>

int main(){
    int x = 10;
    int *y = &x;
    int **z = &y; // declares a double pointer that is pointed to the address of y.
    **z = 6; // dereferencing of a double pointer to change the content of x.

    std::cout << x << '\n';
    std::cout << &x << '\n'; // outputs the address of x.
    std::cout << &y << '\n'; // outputs the address of y.
    std::cout << z << '\n'; // outputs the address of y.
}

As we notice, the address of pointers is not the same as the address of its reference. This observation is because pointers have their own identity. Consequently, pointers can be reassigned to another variable more so they can tolerate null values: NULL and nullptr (prefer using nullptr if you are using pointers). That is, int *x = nullptr is valid and will compile.

More so, pointers can iterate over arrays with pre- and post-increment operators, pre- and post-decrement operators, and subscript operators.

#include <iostream>

void iterate(int* a_ptr, size_t a_size){
    for(size_t i = 0; i < a_size; ++i){
        std::cout << a_ptr[i] << " ";
    }

    std::cout << '\n' << *(++a_ptr); // 2
    std::cout << '\n' << *(--a_ptr); // 1 
    std::cout << '\n' << *(a_ptr++); // 1
    std::cout << '\n' << *(a_ptr--); // 2
}

int main(){
    int array[5]{1,2,3,4,5};
    int *ptr_arr = array;
    iterate(ptr_arr, 5);
}

As mentioned, pointers can be used for allocating values on the heap as well as writing in that location. Let's consider allocating memory for an array block with size 3:

#include <iostream>

void output(int* a_ptr, size_t a_size){
    std::cout << '\n';
    for(size_t i = 0; i < a_size; ++i)
        std::cout << a_ptr[i] << " ";
}

int main(){
    int *array = new int[3];
    // printing uninitialized array
    output(array, 3);
    // writing values on array block
    for(size_t i = 0; i < 3; ++i)
        array[i] = i+1;

    output(array, 3);

    // deallocates the memory
    delete [] array; 
}

Reminders for using Pointers

Pointers can be difficult to manage as they can be nested and combined without restrictions, this can result in a complicated piece of code that is hard to maintain.
Pointers may leak resources if not properly managed:
- ensure clean-ups when pointer types are no longer needed
- remember to deallocate resources allocated on the heap when they are no longer relevant to your code.
Prefer using smart pointers: std::unique_ptr<T> u_ptr, std::shared_ptr<T> s_ptr, and std::weak_ptr<T> w_ptr over raw pointers when performance is secondary to safety or finer grain of control are unnecessary. Smart pointers allow you to automate clean-up through RAII with a minimal performance cost, in the case of u_ptr there is zero performance overhead.
For pointer objects ptr_obj or user-defined types, members can be accessed through arrow operator e.g. ptr_obj-> function().

References

References make things more convenient to express, it provides the necessary set of constraints for expressing ownership semantics -- a topic that is beyond our concern, for now. C++ follows the design principle that solutions that adhere to the standards should be easier than the alternatives.

Now that we know about pointers, how do we contrast this with references?

References can be thought of as a constant pointer T const* c_ptr = &obj and should not be confused with const T* ref = &obj: The former allows the contents of the object to be modified but restricts the address to refer to obj, the latter reverses the effect and only restricts the obj to be modified.

    int x = 5, y = 6;
    int *const ptr = &x;
    ptr = &y; // error

To modify the content of x and set it to y we say:

    int x = 5, y = 6;
    int *const ptr = &x;
    *ptr = y;

The same effect is achieved with references. As a result, references bind to the location of the entity in memory. It allows the contents of an entity to be modified, but it cannot be reassigned and must be bound at initialization. Therefore, the reference of an entity assumes the entity of the original variable.

As mentioned, references can also allocate memory for a single entity on the heap.

    int &ref = *(new int(0));
    std::cout << ref <<'\n';
    ref = 3;
    std::cout << ref;

Reminders for using References

References cannot be assigned to nullptr.
References cannot iterate over arrays.
Returning references over local variables may cause undefined behavior (dangling references).
References must be bound to an existing entity.
References only allow for one level of indirection.
References express the intention clearly and concisely.
Since C++11 standards, references have been used more often as the elements for move semantics are built from the notion of references (lvalue and rvalue references).

Summary

Are pointers and references the same thing? No.
Are there any techniques that pointers can only do and vice-versa? Pointers are more flexible than references which can make your code complicated if not managed well. T const* ref achieves the same behavior of references, except for array referencing which gives us more reason for choosing references over pointer (when appropriate) as its semantics restrict iterating over array-like structures:

    int const *r = &*(new int[3]{1,3,4});
    std::cout << r[2] <<'\n';

Whereas array indexing with references will result to compiler error:

    int &r = *(new int[3]{1,3,4};
    std::cout << r[2] <<'\n';

When do we favor pointers over references and vice-versa? Pointer types are generally useful for setting up a separate field of indirection capable of modifying the contents of multiple variables of the same type. Having the same pointer accessing multiple variables may be difficult to trace and reason with. It is preferred to maintain clarity over the convenience of typing one pointer to all variables of the same type. For this reason, making use of references is safer.

Pointers are not really terrible, in fact, they are one of the greatest features we unlock in languages like C/C++, however, their power comes with a cost.

In conclusion, references are not just syntax sugar to cast T const*, it has its own design goals and purpose namely containing the address of declared entities. This improves the clarity of our intent, and in these situations, the C++ compiler is our friend.

DEV Community: Dave Amiana

Introduction to CMake

What is CMake?

Benefits of using CMake

Installing CMake

Hello, World! in CMake

The Build Process

References

My Neovim Configuration

Why do People use Vim in 2022?

Vim and Neovim

Configuring Neovim

CocInstall example

References

Guidelines on importing modules in Python

Design Principles of Data Structures Library

Design Principles

References

Understanding Abstract Data Types

What is ADT?

How does ADT help us develop Data Structures?

Summary

References

Iterators: The link between Data Structures and Algorithms

Why iterators are important?

Why do we consider writing iterators?

Summary

References

Preface: Data Structures

Introduction: Mostly about my Experience

Importance

Outline of the series

Our Language

Schedule

Implementing Building Blocks of Reference Semantics: Weak Reference

Design goals

Implementation

Requirement: Must initialize only shared_reference<T> type

Requirement: Must not take ownership of shared_reference<T> type

Requirement: Pointer-like interface

Requirement: Must provide a function of counting references

Putting it all together

Test cases

Summary

References

Implementing Building Blocks of Reference Semantics: Shared Reference

Advantages

Disadvantages

Design Goals

Implementation

Requirement: Must Accept any Type

Requirement: Automatic Resource Management and Reference Counting

Requirement: Pointer-like Interface

Putting it all together

Test Cases

Summary

References

Implementing Building Blocks of Reference Semantics: Unique Reference

Design goals of unique reference

Implementation

Requirement: Must Accept any Type

Requirement: Automatic Resource Management

Requirement: Maintain Property of Uniqueness

Requirement: Pointer-like Interface

Putting it all together:

Test Cases

Summary

References

On Pointer Types: Peeking at Reference Semantics

Raw Pointers

The Dangling Problem:

Smart Pointers

Unique Pointer

Shared Pointer

The Circular Reference Problem

Weak Pointer

Summary

References

Pointers and References: Design Goals and Use Cases

Pointers

`Hello, World!` in CMake

`CocInstall` example

Requirement: Must initialize only `shared_reference<T>` type

Requirement: Must not take ownership of `shared_reference<T>` type