At the end of 2023, I published my first article on freeCodeCamp about how I created a SQL-like Language to run queries on local Git repositories. If you want a bit more context, give it a read.

At the start of 2024, the project got bigger and bigger with more features and amazing contributors, and I started to think: what if I could run SQL-like queries not only on .git files but on any kind of local and remote data?

In my last article about How to Run SQL-Like Queries on Files, I explained the internal design of the GitQL SDK components and how to use it with any kind of data in general and how to implement the FileQL project.

In this article, I will explain how I used the GitQL SDK to implement the ClangQL (Clang Query Language) project, which is a tool that helps you run SQL-like queries on local C/C++ files.

How I Came Up with the ClangQL Project

As I mentioned in my past articles, GitQL SDK can run SQL-like queries on any local or remote structured data. Also, the compiler parses your code into an AST (Abstract Syntax Tree) Data structure. So the question that jumped into my mind was, why not run the query on the Abstract Syntax Tree?

There were no limitations I could think of for implementing this idea, so I started to think of the two main requirements for using GitQL: creating the Data Schema to describe the table structures and columns types, and implementing the Data Provider component to provide the data which in our case is the ATS information and mapping it to the Engine format.

The Data Schema for the C/C++ Code

You can think of the Data Schema as the place where we put structure and relationships of our data – for example, which tables we have, and for each table what columns they contain, and finally the types of each column.

This information is very useful when you're performing type checking and detecting if the user has written the wrong column name, for example, which is not defined in the selected table they want to use.

In our case, the tables can be classes, structs, enumerations, functions, variables and any other data that can be read from C++ such as macros and so on. But I decided to start simple with functions and variables only, then I planned to add other kinds.

So for the functions table, let's define what columns we need to include. The columns and types are not hard to guess, so let's take a normal function as an example. It has the name Text, and it returns type as Text, the number of parameters as Int, other C++ flags as Booleans (for example, is it a virtual function is_virtual or a pure virtual function is_pure_virtual?), and another flag to tell you if it is a static function is_static.

So to create a Data Schema you need to define two things: what tables you have, and what columns there are in this table. For example, in the functions table it will look like this:

lazy_static! {
    pub static ref TABLES_FIELDS_NAMES: HashMap<&'static str, Vec<&'static str>> = {
        let mut map = HashMap::new();
        map.insert(
            "functions",
            vec![
                "name",
                "signature",
                "args_count",
                "return_type",
                "class_name",
                "is_method",
                "is_virtual",
                "is_pure_virtual",
                "is_static",
                "is_const",
                "has_template",
                "access_modifier",
                "is_variadic",
                "file",
                "line",
                "column",
                "offset",
            ],
        );
    }
}

You also need to define the expected data type for each column:

lazy_static! {
    pub static ref TABLES_FIELDS_TYPES: HashMap<&'static str, DataType> = {
        let mut map = HashMap::new();
        map.insert("name", DataType::Text);
        map.insert("type", DataType::Text);
        map.insert("signature", DataType::Text);
        map.insert("args_count", DataType::Integer);
        map.insert("return_type", DataType::Text);
        map.insert("class_name", DataType::Text);
        map.insert("is_method", DataType::Boolean);
        map.insert("is_virtual", DataType::Boolean);
        map.insert("is_pure_virtual", DataType::Boolean);
        map.insert("is_static", DataType::Boolean);
        map.insert("is_const", DataType::Boolean);
        map.insert("has_template", DataType::Boolean);
        map.insert("access_modifier", DataType::Integer);
        map.insert("is_variadic", DataType::Boolean);
        map
    };
}

Now let's move on to the most exciting part: the Data Provider.

The Data Provider for the C/C++ Code

The data provider component is used to tell the engine how to load the target data – for example from where and on which thread – and provide these data in a format that is known by our GitQL Engine. So how we can extract that information from our C/C++ code?

Well, we need to get the AST after parsing the C/C++ code. So the first option is to write a C/C++ parser to parse the files and provide the AST. But this option has some problems here: it'll require a lot of hard work, as C++ is a large language. To write a parser from scratch means you need to support every new feature, and handle errors, and so on.

The other option is to take a well-written C/C++ parser from any Compiler that provides the parser as a library and use it to provide the AST. After some searching, I found that the Clang Compiler is well-designed and can provide the parser as a library to use it to build other tools such as code formatter and linter.

LibClang is written in C++ so I used binding for the Rust Programming language to parse the source file as a TranslationUnit. This is the parent node that contains information about classes, functions, and so on.

LibClang provides more than one way to visit the TranslationUnit and all of the children of it. One of them is using the clang_visitChildren function. It takes a function pointer that gives you the Node and its parent and returns the flag as int. Using this flag, you can control if you want to break, continue, or walk inside this node using the return type.

For example if you are visiting the Class or Struct node and want to visit the methods inside them, you need to return CXChildVisit_Recurse – and clang_visitChildren will provide the methods for you. But if you want to just read class info then you need to return CXChildVisit_Continue to continue to other nodes. Using those flags in the wrong way can lead to performance issues and visiting many nodes that aren't useful.

So to get a function's info, we need to call clang_visitChildren as we pass a pointer to our data to save the information we got. For example:

let mut functions: Vec<FunctionNode> = Vec::new();
let data = &mut functions as *mut Vec<FunctionNode> as *mut c_void;

let cursor = clang_getTranslationUnitCursor(translation_unit);
clang_visitChildren(cursor, visit_children, data);

We passed visit_children that point to the function that extracts the C/C++ function's information. It will look like this:

extern "C" fn visit_children(
    cursor: CXCursor,
    parent: CXCursor,
    data: *mut c_void,
) -> CXChildVisitResult {

    let cursor_kind = clang_getCursorKind(cursor);
    if cursor_kind == CXCursor_FunctionDecl
        || cursor_kind == CXCursor_CXXMethod
        || cursor_kind == CXCursor_FunctionTemplate
    {
        let function_name = clang_getCursorSpelling(cursor);
        let function_type = clang_getCursorType(cursor);
        let result_type = clang_getResultType(function_type);
        let arguments_count = clang_getNumArgTypes(function_type);

        // ... Extracing more and more information

        return CXChildVisit_Continue
    }

    CXChildVisit_Recurse
}

Also, if you want to refactor or build advanced searching tools on top of ClangQL, you'll need to get the source code location. For example, where exactly does the function you're searching for exist – on which file and line?

So to get them from Clang, you can use the below code. It provides the file name, line, column and offset data of the selected node:

let cursor_location = clang_getCursorLocation(cursor);

let mut file: CXFile = std::ptr::null_mut();
let mut line: u32 = 0;
let mut column: u32 = 0;
let mut offset: u32 = 0;

clang_getFileLocation(
    cursor_location,
    &mut file,
    &mut line,
    &mut column,
    &mut offset,
);

let file_name = clang_getFileName(file);
let file_name_str = CStr::from_ptr(clang_getCString(file_name)).to_string_lossy();

The source code of visit_children is too large to include because, as you can see, the function node contains a lot of information. So you can check the full and updated code for all visitors from this file in the ClangQL repository: DataProviderFile.

The LibClang creators provide clear documentation on how to walk through the Translation Unit and extract the needed data.

So now we have our Data Schema and Provider, and we can perform a query like SELECT * FROM functions. The result will be likes this:

The result of running a query to select all function information from one file

So after that I decided to name the project ClangQL which stands for Clang Query Language. Now I'm working on extracting more and more important information from the AST (feel free to contribute).

You can find the full source code with all customizations in the ClangQL repository.

Conclusion

You can check out the ClangQL project as a full sample created only in three files.

If you liked the project, you could give it a star ⭐ on GitQL and ClangQL.

You can check out the website for how to download and use the project on different operating systems.

The project is not done yet – this is just the start. Everyone is welcome to join and contribute to the project and suggest ideas or report bugs.

You can sponsor my work on GitHub ❤️.

Thanks for reading

Concurrency is a programming term you'll need to be familiar with if you code in C++. It's especially relevant if you want to get more out of your available compute resources.

But concurrency comes with certain problems. Some of them can be solved using mutexes, although mutexes have their own set of challenges.

This is where atomics come in. However, atomics require an understanding of the memory model of a computer, which is a challenging topic to fully grasp.

This is what we'll cover in this article. Hopefully you'll gain a good understanding of how memory ordering works and how to use atomics in conjunction with memory ordering to build a lock-free queue in C++.

Pre-requisites

To get the most out of this guide, you need to have written some basic concurrent programs. Programming experience with C++ helps.

Note: If you want to actually compile the code and run it, make sure to do so with the TSan flag enabled for the CLang compiler. TSan is a reliable way of detecting data races in your code, instead of trying to repeatedly run the code in a loop hoping for a data race to occur.

Getting Started

Imagine you have some concurrent code operating on some shared data in memory. You have two threads or processes, one writing and one reading on some shared piece of state.

Processes sharing memory

The "safe" way of dealing with this is mutexes. But mutexes tend to add overhead. Atomics are a more performant but much more complicated way of dealing with concurrent operations.

What Are Atomics in C++?

This section is very simple. Atomics are simply operations or instructions that cannot be split by the compiler or the CPU or re-ordered in any way.

The simplest possible example of an atomic in C++ is an atomic flag. It looks like this:

#include <atomic>

std::atomic<bool> flag(false);

int main() {
  flag.store(true);
  assert(flag.load() == true);
}

We define an atomic boolean, initialise it, and then call store on it. This method sets the value on the flag. You can then load the flag from memory and assert its value.

Operations with Atomics

The operations you can perform with atomics are straightforward:

1. You can store some value into them with the store() method. This is a write operation.
2. You can load some value from them with the load() method. This is a read operation.
3. You can do a Compare-and-Set (CAS) with them using the compare_exchange_weak() or compare_exchange_strong() method. This is a read-modify-write (RMW) operation.

The important thing to remember is that each of these cannot be split into separate instructions.

Note: There are more methods available, but this is all we need for now.

There are various atomics available in C++ and you can use them in combination with memory orderings.

Memory Ordering

This section is a lot more complicated and is the meat of the matter. There are some great references to help you understand memory ordering in more depth that I've linked at the bottom.

Why Memory Ordering Matters

The compiler and CPU are capable of re-ordering your program instructions, often independently of one another. That is, your compiler can re-order instructions and your CPU can re-order instructions again. See this post for more detail.

But this is only allowed if the compiler can definitely not establish a relationship between the two sets of instructions.

For instance, the below code can be re-ordered because there is no relationship between the assignment to x and the assignment to y. That is, the compiler or CPU might assign y first and then x. But, this doesn't change the semantic meaning of your program.

int x = 10;
int y = 5;

On the other hand, the following code example cannot be re-ordered because the compiler cannot establish the absence of a relationship between x and y. It's pretty easy to see here because y depends on the value of x.

int x = 10;
int y = x + 1;

This doesn't seem like a big problem – until there's multi-threaded code. Let's see what I mean with an example.

Intuition for Ordering

#include <cassert>
#include <thread>

int data = 0;

void producer() {
  data = 100;  // Write data
}

void consumer() {
  assert(data == 100);
}

int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join();
  t2.join();
  return 0;
}

The multi-threaded example above will fail to compile with TSan because there is a clear data race when thread 1 is trying to set the value of data and thread 2 is trying to read the value of data. The easy answer here is a mutex to protect the write and read of data, but there's a way to do this with an atomic boolean.

We loop on the atomic boolean until we find that it is set to the value we are looking for and then check the the value of data.

#include <atomic>
#include <cassert>
#include <thread>

int data = 0;
std::atomic<bool> ready(false);

void producer() {
  data = 100;
  ready.store(true);  // Set flag
}

void consumer() {
  while (!ready.load())
    ;
  assert(data == 100);
}

int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join();
  t2.join();
  return 0;
}

When you compile this with TSan, it doesn't complain about any race conditions. Note: I'm going to refer back to why TSan doesn't complain here a little further on.

Now, I'm going to break it by adding a memory ordering guarantee to it. Just replace ready.store(true); with ready.store(true, std::memory_order_relaxed); and replace while (!ready.load()) with while (!ready.load(std::memory_order_relaxed)).

TSan will complain that there is a data race. But, why is it complaining?

The issue here is that we have no order among the operations of the two threads anymore. The compiler or CPU is free to re-order instructions in the two threads. If we go back to our abstract visualisation from earlier, this is what it looks like now:

Relaxed memory model ordering

The visualisation above shows us that our two processes (threads) have no way of agreeing upon the current state or the order in which that state has changed.

Once process 2 determines that the flag has been set to true, so it tries to read the value of data. But, thread 2 believes that the value of data has not yet changed even though it believes the value of flag has been set to true.

This is confusing because the classic model of interleaving concurrent operations doesn't apply here. In the classic model of concurrent operations, there is always some order that can be established. For instance, we can say that this is one possible scenario of operations:

Thread 1                  Memory                  Thread 2
---------                 -------                 ---------
  |                          |                          |
  |   write(data, 100)       |                          |
  | -----------------------> |                          |
  |                          |     load(ready) == true  |
  |                          | <----------------------  |
  |                          |                          |
  |   store(ready, true)     |                          |
  | -----------------------> |                          |
  |                          |                          |
  |                          |       read(data)         |
  |                          | <----------------------  |
  |                          |                          |

But, the above graphic assumes that both threads have agreed upon some global order of events, which isn't true at all anymore! This is still confusing for me to wrap my head around.

In a memory_order_relaxed mode, two threads have no way of agreeing upon the order of operations on shared variables. From thread 1's point of view, the operations it executed were the following:

write(data, 100)
store(ready, true)

However, from thread 2's point of view, the order of operations it saw thread 1 execute were:

store(ready, true)
write(data, 100)

Without agreeing upon the order in which operations occurred on shared variables, it isn't safe to make changes to those variables across threads.

Okay, let's fix the code by replacing std::memory_order_relax with std::memory_order_seq_cst.

So, ready.store(true, std::memory_order_relaxed); becomes ready.store(true, std::memory_order_seq_cst); and while (!ready.load(std::memory_order_relaxed)) becomes while (!ready.load(std::memory_order_seq_cst)).

If you run this again with TSan, there are no more data races. But why did that fix it?

Memory Barrier

So, we saw our problem earlier was about two threads being unable to agree upon a single view of events and we wanted to prevent that. So, we introduced a barrier using sequential consistency.

Thread 1                  Memory                  Thread 2
---------                 -------                 ---------
  |                          |                          |
  |   write(data, 100)       |                          |
  | -----------------------> |                          |
  |                          |                          |
  |  ================Memory Barrier===================  |
  |   store(ready, true)     |                          |
  | -----------------------> |                          |
  |                          |   load(ready) == true    |                   
  |                          | <----------------------  |
  |  ================Memory Barrier===================  |
  |                          |                          |
  |                          |       read(data)         |
  |                          | <----------------------  |
  |                          |                          |

The memory barrier here says that nothing before the store operation and nothing after the load operation can be re-ordered. That is, thread 2 now has a guarantee that the compiler or the CPU will not place the write to data after the write to the flag in thread 1. Similarly, the read operation in thread 2 cannot be re-ordered above the memory barrier.

The region inside the memory barrier is akin to a critical section that a thread needs to a mutex to enter. We now have a way to synchronise the two threads on the order of events across them.

This brings us back to our classic model of interleaving in concurrency because we now have an order of events both threads agree upon.

Types Of Memory Order

There are 3 main types of memory order:

1. Relaxed memory model (std::memory_order_relaxed)
2. Release-acquire memory model (std::memory_order_release and std::memory_order_acquire)
3. Sequentially consistent memory order (std::memory_order_seq_cst)

We already covered 1 and 3 in the examples above. The second memory model literally lies between the other two in terms of consistency.

#include <atomic>
#include <cassert>
#include <iostream>
#include <thread>

int data = 0;
std::atomic<bool> ready(false);

void producer() {
  data = 100;
  ready.store(true, std::memory_order_release);  // Set flag
}

void consumer() {
  while (!ready.load(std::memory_order_acquire))
    ;
  assert(data == 100);
}

int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join();
  t2.join();
  return 0;
}

The above is the same example from earlier, expect with std::memory_order_release used for ready.store() and memory_order_acquire used for read.load(). The intuition here for ordering is similar to the pervious memory barrier example.

Except, this time the memory barrier is formed on the pair of ready.store() and ready.load() operations and will only work when used on the same atomic variable across threads.

Assuming you have a variable x being modified across 2 threads, you could do x.store(std::memory_order_release) in thread 1 and x.load(std::memory_order_acquire) in thread 2 and you would have a synchronization point across the two threads on this variable.

The difference between the sequentially consistent model and the release-acquire model is that the former enforces a global order of operations across all threads, while the latter enforces an order only among pairs of release and acquire operations.

Now, we can revisit why TSan didn't complain about a data race initially when there was no memory order specified. It's because C++ by default assumes a std::memory_order_seq_cst when no memory order is specified. Since this is the strongest memory mode, there is no data race possible.

Hardware Considerations

Different memory models have different performance penalties on different hardware.

For instance, the x86 architectures instruction set implements something called total store ordering (TSO). The gist of it is that the model resembles all threads reading and writing to a shared memory. You can read more about that here.

This means that the x86 processors can provide sequential consistency for a relatively low computational penalty.

On the other side are the ARM family of processors has a weakly ordered instruction set architecture. This is because each thread or process reads and writes to its own memory. Again, the link above provides context.

This means that the ARM processors provide sequential consistency for a much higher computational penalty.

How to Build a Concurrent Queue

I'm going to use the operations we have discussed so far to build the basic operations of a lock-free concurrent queue. This is by no means even a complete implementation, just my attempt to re-create something basic using atomics.

I'm going to represent the queue using a linked list and wrap each node inside an atomic.

class lock_free_queue {
 private:
  struct node {
    std::shared_ptr<T> data;
    std::atomic<node*> next;

    node() : next(nullptr) {}  //  initialise the node
  };

  std::atomic<node*> head;
  std::atomic<node*> tail;
}

Now, for the enqueue operation, this is what it's going to look like:

void enqueue(T value) {
    std::shared_ptr<T> new_data = std::make_shared<T>(value);
    node* new_node = new node();
    new_node->data = new_data;

    //  do an infinite loop to change the tail
    while (true) {
      node* current_tail = this->tail.load(std::memory_order_acquire);
      node* tail_next = current_tail->next;

      //  everything is correct so far, attempt the swap
      if (current_tail->next.compare_exchange_strong(
              tail_next, new_node, std::memory_order_release)) {
        this->tail = new_node;
        break;
      }
    }
  }

The main focus is on the load and compare_exchange_strong operations. The load works with an acquire and the CAS works with a release so that reads and writes to the tail are synchronized.

Similarly for the dequeue operation:

std::shared_ptr<T> dequeue() {
    std::shared_ptr<T> return_value = nullptr;

    //  do an infinite loop to change the head
    while (true) {
      node* current_head = this->head.load(std::memory_order_acquire);
      node* next_node = current_head->next;

      if (this->head.compare_exchange_strong(current_head, next_node,
                                             std::memory_order_release)) {
        return_value.swap(next_node->data);
        delete current_head;
        break;
      }
    }
    return return_value;
  }

Note: This queue doesn’t handle the ABA problem. It's out of the scope of this tutorial to bring in hazard pointers, so I’m leaving that out – but you can look into them if you're curious.

Conclusion

So there you have it – atomics in C++. They're difficult to reason about but give you massive performance benefits. If you want to see production grade implementations of lock-free data structures, you can read more here.

Typically, you'd see lock-based concurrent data structures put into production, but there is increasing research around the area of lock-free and wait-free implementations of concurrent algorithms to improve compute efficiency.

If you want to read this and other tutorials, you can visit my website here.

This improves program performance since operations are no longer being computed on the fly, during runtime.

While these techniques of offloading operations to compile time improve performance, they can also help subtle problems such as a the 'Static initialization Order Fiasco' which I covered in a previous article.

This tutorial teaches you two ways to make this happen in C++. Here is what we'll cover:

• Prerequisites
• How to evaluate functions at compile time using constexpr
• The constinit specifier and its uses
• Summary

##Prerequisites

• A basic understanding of C++: For readers not familiar with C++, Learn C++ Programming for Beginners – Free 31-Hour Course is a helpful resource
• A read through of my previous article What is the Static Initialization Order Fiasco in C++ will benefit you with context around constinit.

How to Evaluate Functions at Compile Time Using constexpr

To understand this, let's first take a look at an example of a function which performs a very simple computation:

int add2(int input) {
    return input + 2;
}

int main() {
    int b = add2(3);
    std::cout << "b = " << b;
    return 0;
}

Here, all that the function add2() does is it adds 2 to the input. In main(), add2() was called with input 2. So, it's pretty straightforward for anyone looking at the program to tell what the output of the function is going to be: 5. There is no sort of non-determinism here.

But if we look at the x86 assembly code generated by the compiler it would look similar to the below:

add2(int):
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, 2
        pop     rbp
        ret
.LC0:
        .string "b = "
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     edi, 3
        // Function add2() getting called
        call    add2(int)
        mov     DWORD PTR [rbp-4], eax
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)
        mov     rdx, rax
        mov     eax, DWORD PTR [rbp-4]
        mov     esi, eax
        mov     rdi, rdx
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        mov     eax, 0
        leave
        ret

(Note that the reference assembly codes in this article were generated by using the compiler explorer tool at godbolt.org.)

The function add2() actually gets called at runtime in main() with the call add2(int) line.

Since this function does something that can be completely computed before the program actually executes (2+3 = 5, even in our heads!), wouldn't it be cool if we could have the compiler not create a function for this operation and just fill in the answer directly in assembly code? This is exactly what constexpr does.

If the code was changed to this:

constexpr int add2(int input) {
    return input +2;
}

int main() {
    int b = add2(3);
    std::cout << "b = " << b;
    return 0;
}

the compiler would output the following assembly code:

.LC0:
        .string "b = "
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], 5
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        call    std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)
        mov     rdx, rax
        mov     eax, DWORD PTR [rbp-4]
        mov     esi, eax
        mov     rdi, rdx
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        mov     eax, 0
        leave
        ret

The function add2() has disappeared and the line mov DWORD PTR [rbp-4], 5 has baked into the program the evaluation of the function add2() at compile time. There is no runtime call to add2().

Mind you, this is possible since we've passed in 3 – an expression that is known at compile time – to the add2() function. If something that couldn't be evaluated at compile time was passed in, the compiler would again generate an add2() function.

You can see what I mean in this snippet:

#include<iostream>
#include <random>

constexpr int add2(int input) {
    return input +2;
}

int main() {
    int rd = std::rand();
    int b = add2(rd);
    std::cout << "b = " << b;
    return 0;
}

The assembly generated again has the add2() function:

add2(int):
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, 2
        pop     rbp
        ret
.LC0:
        .string "b = "
main:
        push    rbp
// Snip

Alright, you've now seen how using the constexpr specifier can help programs move runtime costs to compile time costs in many cases.

Let's now look at another specifier introduced recently, in C++20, which verifies that variables are initialized at compile time.

The constinit Specifier and its Uses

The constinit specifier was introduced in C++ 20. This specifier asserts that a variable has constant initialization – it sets the initial values of the static variables to a compile-time constant. Otherwise, the program is ill-formed and the compiler produces an error. For example:

int add2(int v) {
    return v + 2;
}

//Error: 'constinit' variable 'glob' does not have a constant initializer  
constinit int glob = add2(2);

int main() {

    return 0;
}

The compiler errors out here since the add2() function isn't sure to have constant initialization – which can be determined at compile time. Now if the add2() function is marked constexpr, it will have constant initialization, so the code compiles.

constexpr int add2(int v) {
    return v + 2;
}

//OKAY 'constinit' variable 'glob' does have a constant initializer.  
constinit int glob = add2(2);

int main() {

    return 0;
}

Now you may ask – what's really the use of this specifier?

The answer is it that can be used in certain cases to solve the 'Static Initialization Order Fiasco'.

I talked about the 'Static Initialization order Fiasco' in an earlier article. If we use constinit, the compiler is giving the programmer its word that the constinit variable will be constant initialized – so that's before any other static variables are constructed at runtime. We get rid of the 'Static Initialization / Destruction Order Fiasco'.

Another example where we use strings that are constant initialized illustrates this:

// Parent.h
#pragma once
class Parent {
    public:
       size_t getMoneyCount();
       constexpr Parent(const char *moneyString): mData(moneyString) {};
    private:
        std::string_view mData;     
};
extern Parent everyonesParent;

// Parent.cpp
#include<Producer.h>

constinit static Parent everyonesParent("TheParent");

size_t Parent::getMoneyCount() {
    return mData.size();
}

//Child.cpp
#include<Child.h>

class Child {
    public:
    Child(Parent &parent) : mMoneyCount(parent.getMoneyCount()) {};
    private:
    size_t mMoneyCount;
};

static Child everyonesChild(everyonesParent);

There is no static initialization order problem here, since the static object everyonesParent is guaranteed to be initialized before everyonesChild, since it was marked constinit.

It was okay to mark everyonesParent constinit since it used std::string_view which can be constant initialized – unlike std::string. Also, it had a constexpr constructor. If it didn't use either of these, compilation would have failed!

In closing, something to note about constinit: constinit does not imply const.

constinit values can be modified after construction. Take this example – it is perfectly legal:

#include<iostream>

constinit int i = 42;
int main() {
 i++;
 std::cout << " i is " << i << "\n";
}

##Summary

This article covered compile time operations and run time operations. It analyzed how compilers produce code to either generate functions used at runtime or evaluate them at compile time.

You learned about the constexpr and constinit specifiers in C++, and how they are extremely useful.

I hope you enjoyed the article!

I'll first go over what the problem is, then go onto some solutions and explore how they work. Let's get started.

This is what we'll cover:

• Prerequisites
• What is the 'Static Initialization Order Fiasco' in C++ ?
• Solutions to the static de-initialization order problem
• Construct on first use idiom
• Nifty Counter Solution
• Summary

##Prerequisites

• A basic understanding of C++: For readers not familiar with C++, Learn C++ Programming for Beginners – Free 31-Hour Course is a helpful resource
• In particular, an understanding of storage classes in C++ will be helpful.

##What is the 'Static Initialization Order Fiasco' in C++ ?

The C++ standard states:

"The order in which static objects are initialized across different translation units is undefined or ambiguous."

A translation unit is just a way of saying a file that is fed into the compiler. It's a C++ source file with all the code from the headers included in it.

One thing to note though, for later in the article: static objects in the same translation unit are constructed in order of declaration and destructed in the reverse order.

So, how is this a problem?

It can be a problem in the following situation:

Let's say there are 2 static objects in 2 different files. File1.cpp has a static object of type class A – aObj . File2.cpp has a static object of type class B – bObj. The static object in File1.cpp is visible to File2.cpp since it declares aObj as extern in File1.h.

// Static initialization order problem
// File1.h
class A {
....
  void doSomething() {
    ...
  } 
}
extern A aObj;

//File1.cpp


static A aObj;

// File2.cpp

class B {
B() {
 aObj.doSomething();// Not okay! aObj may not have been constructed
}
....
}

static B bObj;

In this program, it is possible that the object aObj in File1.cpp gets initialized before bObj in File2.cpp. That is all good since in that case, the constructor for bObj runs after aObj has been constructed. It is safe to call call methods on aObj.

But it is also possible that the object bObj in File2.cpp gets initialized before aObj in File1.cpp. In that case, the constructor of bObj calls doSomething() on aObj which has not been constructed! The memory has been allocated for aObj, but it hasn't been constructed. This could lead to unintended behavior / a corrupt program.

So this is what the static initialization order fiasco is all about.

But we're not done: the other problem is the static de-initialization order fiasco! This is pretty much the same problem, just applied to the order of de-initialization of static objects.

The C++ standard doesn't specify the order in which static objects get de-initialized as well. So it is possible that static object aObj gets destroyed before bObj. This is a problem if bObj's destructor uses or references aObj.

This is illustrated in the code snippet below – it is pretty much the same as the example above, just that its the de-initialization order which is dangerous this time:

// Static de-initialization order problem
// File1.h
class A {
....
  void doSomething() {
    ...
  } 
}
extern A aObj;

//File1.cpp

static A aObj;

// File2.cpp

class B {
B() {}
~B() {
 aObj.doSomething(); // Not okay! aObj may have already been destructed!
}
....
}

static B bObj;

Note: These problems are only applicable to objects with static storage scope. They won't occur if bObj was a variable with automatic storage scope. In that case, the C++ standard guarantees that aObj is constructed before bObj and destructed after it.

Another note: These problems also do not occur in C programs. Why is that so? Well in C, there's no concept of constructors and destructors. Static objects are completely defined during compile time.

How to Solve the Static De-initialization Order Problem

Now that it is clear what the problem is, I will discuss some solutions. There are multiple ways of solving this problem – each with its tradeoffs. Let's take a look.

###Construct on first use idiom:

This idiom tries to make sure that there is always a fully constructed object whenever the static object in question is used. Following the examples in the previous section, we can do this by replacing all references to aObj by a function call aObj() which returns a reference to an object of type A.

In code it looks like this:

// Static initialization order problem
// File1.h
class A {
....
  void doSomething() {
    ...
  } 
};

A& aObj();

//File1.cpp

A& aObj() {
  static A *aObj = new A();
  return *aObj; 
}

// File2.cpp

class B {
 B() {
   /*
    * Okay since calling aObj() gaurantees that
    * static A *aObj = new A(); ran
    */
   aObj().doSomething();  
  }
  ....
};

static B bObj;

bObj can safely assume that calling aObj() returns a fully constructed aObj since this line:

static A *aObj = new A();

would have run on the function call and will give it a fully constructed object. Also, since the program never calls delete on aObj, it is never destructed so it is also safe to use aObj in bObj's destructor.

But this does mean that the memory allocated for aObj always stays alive and valid throughout the lifetime of the program. And this may or may not be a problem (it does get reclaimed by the OS after the program exits, of course).

So, in which situation is this solution not great? In the case that aObj's destructor does something desirable. For example: when aObj gets destructed – it writes to a log file / does something else that has some side effects.

Now you may ask, okay, why don't just I replace the static pointer in the aObj() function call with a static aObj object?

A& aObj() {
  static A aObj;
  return aObj; 
}

That still ensures that aObj has been fully constructed by the time the function is called right? Right. But it does not save us from the static de-initialization order problem. It is still possible that aObj's destructor runs before bObj 's destructor.

There is an interesting trick that solves both of these problems: The Nifty Counter Idiom.

###Nifty Counter Solution

Reference: this resource on the Nifty counter idiom presents the idea behind this idiom. Let's examine it.

The idea is to ensure that:

1. The static object being used gets constructed before any other static object in the translation unit that it is being used in.
2. The static object being used gets destructed after any other static object in the translation unit that it is being used in.

// File1.h
#pragma once

struct A {
  A();
  ~A();
};
extern A& aObj;

static struct AInitializer {
  AInitializer ();
  ~AInitializer ();
} aInitializer; // static initializer for every translation unit that aObj is used in

// File1.cpp
#include "File1.h"

#include <new>         // Used for placement new
#include <type_traits> // Used for aligned_storage

static int niftyCounter; // this is zero initialized at load time

/*
 * Memory for the static object aObj - memory itself is valid throughout the
 * the lifetime of the program.
 */
static typename std::aligned_storage<sizeof (A), alignof (A)>::type
  aObjBuf; 

A& aObj = reinterpret_cast<A&> (aObj);

A::A ()
{
  // Construct A
}
A::~A ()
{
  /*
   * Destruct A: with possible side effects
   * like writing to a file.
   */
} 

AInitializer::AInitializer ()
{
  if (niftyCounter++ == 0) {
    new (&aObj) A (); // use placement new operator
  }
}

AInitializer::~AInitializer ()
{
  if (--niftyCounter == 0) {
    (&aObj)->~A(); // run the destructor
  }
}

Let's try to understand what this code does.

First, in the header file, File1.h has the definition of class A first. After that, is have the definition of a class called AInitializer.

There is also a static object defined in the header file of type AInitializer. This makes sure that the constructor for AInitializer runs before the constructor for any other static object in the translation unit that File1.h is included in (of course you have to include File1.h before any other static object's definition in source files).

Remember: static objects in the same translation unit are constructed in order of declaration and destructed in the reverse order.

So now that AInitializer is constructed before any other static objects in a translation unit, how can we use this to our advantage? aObj can be constructed in the constructor of AInitializer! Which is what is happening in the lines below:

AInitializer::AInitializer ()
{
  if (nifty_counter++ == 0) {
    new (&aObj) A (); // use placement new
  }
}

Note that the placement new operator is being used here instead of the new operator to construct aObj. Let's see what would happen if we used new instead. The code would look like this:

A& aObj;
A *aObjp = nullptr;

AInitializer::AInitializer ()
{
  if (nifty_counter++ == 0) {
    aObjp = new A (); 
    aObj = *aObjp; // Not okay! Cannot re-assign a reference
  }
}

This doesn't work since a reference needs to be defined and declared at the same time. That is precisely why the placement new operator needs to be used.

static typename std::aligned_storage<sizeof (A), alignof (A)>::type
  aObjBuf; 

A& aObj = reinterpret_cast<A&> (aObj)

This allocates memory to fit an object of type A and later assigns that to the reference. Now all that's left to be done is to actually construct the object in AInitializer's constructor – which is what is done with the placement new operator.

Another question that may arise in your mind: here, there is a static object aObjBuf. But isn't that subject to the same de-initialization order problem that we talked about in the second part of the Construct on first use idiom?

The answer is that the memory for aObjBuf stays alive and valid until the program is alive. Nothing happens in the construction of the memory. So it's valid to this.

This approach also makes sure that the static de-initialization order problem isn't hit, since the last AInitializer object destructed will call the destructor of aObj. That is guaranteed to run after any static objects in other translation units run, since within the particular translation unit, the static object aInitializer is declared before any other static object using aObj. This means it will get destructed in the reverse order – that is after the destructor for any other static objects have run.

There are some caveats here: this solution isn't the easiest to understand and implement. This is also not thread safe. You can find more information in the article on Nifty counters presented in the The C/C++ Users Journal, May, 1999 here.

##Summary

Using statically initialized objects in C++ is tricky and should be done with care. Fortunately, there are multiple solutions and ways to get around the problem.

In this article, we covered some common solutions: the 'Construct on first use' idiom and the 'Nifty counter solution', along with their merits and challenges.

Hope you enjoyed this article!

• Measure/profile the performance of certain parts of code.
• Do work at certain periods of time, from within a program.
• Detect whether threads are in a deadlock / taking too long to complete an operation.
• Synchronize tasks between different components of software

and many more…

This article will guide you through how you can measure time in modern C++.

Prerequisites

• A basic understanding of C++: For readers not familiar with C++, Learn C++ Programming for Beginners – Free 31-Hour Course is a helpful resource.
• A quick read through Linux time tracking infrastructure – such as you can find here – will help you get familiar with the ideas presented in the article.

Common Ways to Track Time in C++

This article covers how you can keep track of time in C++. In C, on UNIX like systems, you can use the clock_gettime() function to keep track of time. It returns time in a structured way through the timespec struct.

The clock_gettime() /gettimeofday function gives us back a filled timespec struct which has two fields:

1. tv_sec, which gives us the time in seconds since the time source – CLOCK_REALTIME / CLOCK_MONOTONIC that was passed into clock_gettime. The 'type' of this field is time_t which is usually an integral value.
2. tv_nsec, which gives the time after tv_sec, in nanoseconds since the time source that was specified while calling clock_gettime(). The type of this field is a long int.

So why is clock_gettime() not good enough? The answer is that the members of struct timespec can easily be passed to functions as they're really just ints / floats. They're not strongly typed.

It's also easy to forget about the units in which they represent time while passing information around to functions. This can happen when you're dealing with projects that have thousands of lines of code.

So what's the solution?

##The std::chrono API

C++11 introduced the std::chrono API, which can help you avoid some of these problems.

There are 3 important parts of the API.

###1. std::chrono::duration

As its name suggests, std::chrono::duration is a type that represents a time interval. The official C++ reference mentions that std::chrono::duration is a templated type with the following signature:

template<
    class Rep,
    class Period = std::ratio<1>
> class duration;

Here, the Rep template parameter represents the type that is used to count 'ticks' of time. A tick is just a unit of time which is a given fraction of a second. Period, the second parameter, defines what exactly that fraction is.

So, for example, if you write:

using my_ms_type = std::chrono::duration<int, std::ratio<1, 1000>>

my_ms_type duration_ms duration = 3; // error: cannot convert from int
my_ms_type duration_ms duration_ok{3} // OK, can construct from int

my_ms_type is a type that has been defined, which counts in units of milliseconds (1/1000th of a second). This count is expressed as an integer. As you might be able to guess, the Rep template parameter is int and Period is std::ratio<1,1000> (which really is a way of saying 1/1000).

Now that it's clear how durations are represented, let's see what we can and cannot do with these.

If there is a function that takes in a my_ms_type duration and you instead try to pass in any non-std::chrono::duration type, you'll get a compiler error.

It is possible to implicitly convert between different types of std::chrono::duration as long as information isn't lost with the type of Rep, since the standard library can compute the relationship between two std::chrono::durationtypes. It is not possible to implicitly convert if there is a loss of information. For example:

#include<chrono>

using namespace std::chrono;
using my_type_ms = std::chrono::duration<int, std::ratio<1, 1000>>;
using my_type_ms_f = std::chrono::duration<float, std::ratio<1, 1000>>;
using my_type_hundredth_s = std::chrono::duration<int, std::ratio<1, 100>>;
void f(my_type_ms millis) {}
int main()
{
   int duration = 2;
   my_type_ms_f duration_f{2.5};
   my_type_hundredth_s duration_compatible{100};

   f(duration); // error: could not convert 'duration' from 'int' to 'my_type_ms'

   f(duration_f) //error: since float -> int will lose information

   f(duration_compatible) // OK since no information is lost
}

The standard library also has some predefined std::chrono::duration template specializations for common time durations such as std::chrono::duration::seconds, milliseconds, microseconds, and so on.

You can also get the 'count' value contained in a duration by using the count method in a duration.

std::chrono::seconds duration{3};
// Prints: 'Duration count: 3 seconds'
std::cout << "Duration count: " << duration.count() << " seconds";

Interestingly, converting from a unit with higher precision like nanosecond to something with a lower precision such as millisecond may also lead to a loss of information. For these specific cases, you need to use an explicit cast for conversion. This is called duration_cast. For example:

nanoseconds durationInNs = 3000000000;
seconds ms = duration_cast<seconds>(durationInNs); //OK 3s
durationInNs = 3500000000;
ms = duration_cast<nanoseconds>(durationInNs); // OK 3s - truncates down

Now that we know why std::chrono::duration is useful, let's move on. The next section explores std::chrono::time_point.

###2. std::chrono::time_point

std::chrono::time_point is a way of expressing a particular point in time – surprise, surprise!

If you think about it, how can you logically define a point in time ? We need to have a reference starting point and a duration from the starting point. This is exactly what std::chrono::time_point does.

The class declaration looks like this:

template<
    class Clock,
    class Duration = typename Clock::duration
> class time_point;

There are two template parameters here:

The first one is Clock which represents a reference clock relative to which the point in time is being measured. For now, some examples of clocks are:

• system_clock: this represents a real-world wall clock. It's useful when you want to measure time in terms of real-world times. It's important to note that the system time can usually be changed on any system, so you shouldn't depend on this clock to calculate time periods between tasks / performance profiling.
• steady_clock: this represents a monotonically increasing clock. It's useful when you need stop-watch like clock accounting.

The second template parameter is Duration which is what we discussed in the previous section. A time_point needs to be associated with a duration type since that's what is being used to measure ticks since the 'epoch' of the Clock.

Epoch is just a way of saying a reference point in time. While there's no mandate for which reference to use, Unix Time - that is, the time since 00:00:00 Coordinated Universal Time (UTC), Thursday, 1 January 1970 is a common one.

Time points based on the same clock can be subtracted and not added. For example:

auto tp1 = std::chrono::system_clock::now();
...
auto tp2 = std::chrono::system_clock::now()
auto tp3 = std::chrono::steady_clock::now();

auto diff = tp2 - tp1; // OK
auto add = tp1 + tp2; // Not Ok
auto add = tp3 - tp2; // Not Ok - based on different clocks

Let's now see what clocks are.

###3. Clock Types

A Clock is a type that ties together std::chrono::duration and std::chrono::time_point. It has a function now() that returns the current time_point. The formal requirements for a type to be a Clock can be found in the C++ spec here.

As mentioned before, system_clock and steady_clock are two popular clocks provided by the standard library. Each clock has its own associated duration as well.

Each time_point is associated with some clock, since it really has to be relative to some given reference.

Finally, let's see some examples of how you can tie together duration, time_point, and Clock. Let's say you want to measure the time that looping 100,000,000 times takes in nanoseconds, and you also want to print out the current wall time:

#include <chrono>
#include <iostream>
#include <ratio>
#include <thread>
#include <ctime>

using namespace std::chrono;
constexpr size_t kIterations = 100000000;
void testFunction () {
    for (size_t i = 0; i < kIterations; i++) {
    }
}

int main()
{
    auto tStartSteady = std::chrono::steady_clock::now();
    std::time_t startWallTime = system_clock::to_time_t(system_clock::now());
    std::cout << "Time start = " << std::ctime(&startWallTime) << " \n";
    testFunction();
    auto tEndSteady = std::chrono::steady_clock::now();
    nanoseconds diff = tEndSteady - tStartSteady;
    std::time_t endWallTime = system_clock::to_time_t(system_clock::now());
    std::cout << "Time end = " << std::ctime(&endWallTime) << " \n";
    std::cout << "Time taken = " << diff.count() << " ns";
    return 0; 
}

The output of the program is the following:

Output:
// This can of course vary from system to system
Time start = Tue Nov  7 07:11:13 2023

Time end = Tue Nov  7 07:11:13 2023

Time taken = 50998885 ns

Summary

This article explored various facets of the std::chrono API in C++. The std::chrono API allows C++ programmers to safely keep track of time thanks to its strongly typed system. It also helps maintain support for convenient conversions between different 'types' of time points.

This article will show you how to use Clang's front end libraries to build a simple static analysis tool which will operate on C++ source / header files. It will use the power of AST (Abstract Syntax Tree) traversal.

An abstract syntax tree is a tree structure representing the syntactical structure of code. Here is a good explanation of how it works, and here is a tool to help you explore the AST for a given piece of code.

Here, I will teach you how you can use the Clang AST to find information about the code given to it to show you how powerful it is.

This article goes through everything step by step, and I’ll explain the terminology I'm using briefly at each step.

In the first section, you'll learn how to get the open source Clang project. Then, we'll explore how you can build a static analysis tool with a simple goal: to check if each Class defined in a source / header file starts with an uppercase character. We'll do this using Clang's frontend libraries which will analyze the C++ source AST.

So go ahead and grab your favorite coding beverage, get comfortable, and read on!

Here's what we'll cover:

• Prerequisites
• How to Get the Clang Project and Access the Front-end Libraries
• How to Create the Scaffolding for the Static Analysis Tool
• Putting it All Together in Code
• Summary

Prerequisites

Before getting started, it would be beneficial to have a basic understanding of the following:

• Compilers: this page is a good primer for beginners.
• C++ : For readers not familiar with C++, Learn C++ Programming for Beginners – Free 31-Hour Course is a helpful resource.
• Git: Git Best Practices – A Guide to Version Control for Beginners is an excellent starting point.

How to Get the Clang Project and Access the Front-end Libraries

Since clang and llvm are open source projects, they have very comprehensive documentation around how to get started with getting the code and building tools using them.

You can check out the Getting Started page of the llvm project to get more information about this. I've referenced that in this article as well.

###1. Get the Clang project

On a UNIX like terminal, clone the llvm Git project into your own directory. I'll call it ast-anaylzer.

1. mkdir -p ~/ast-analyzer; cd ~/ast-analyzer
2. git clone https://github.com/llvm/llvm-project.git #Clone the llvm project source

###2. Get the CMake build system and Ninja build tool

CMake and ninja work in conjunction to form a build system. CMake generates build.ninja files, which contain commands that tell ninja how to generate output targets. We’ll get into this more a little later.

####2.1 Get and install Ninja

Here are the steps you can follow to install Ninja:

1. cd ~/ast-analyzer
2. Clone the ninja source project with this command: git clone https://github.com/martine/ninja.git
3. cd ninja
4. Checkout the release branch - this is the stable branch - with this command: git checkout release
5. python3 configure.py –bootstrap This prepares and creates a Ninja binary (configure.py –help will give you more information).
6. Install ninja with this command: sudo cp ninja /usr/local/bin. After this step, as a basic validity check, do which ninja to make sure it says /usr/local/bin/ninja.

####2.2. Get and install CMake

Here are the steps you can follow to install cmake:

1. cd ~/ast-analyzer
2. Clone the cmake project source code: git clone git://cmake.org/stage/cmake.git
3. cd cmake
4. Checkout the release branch - this is the stable branch - with this command: git checkout release.
5. Run the bootstrap script: ./bootstrap. This prepares cmake to be built and installed on your host machine.
6. Build cmake from source with this command: make.
7. Then finally install cmake: sudo make install.

Once we’ve gotten Clang, we’ll build it and configure it so we can build Clang-based tools as well.

###3. Build Clang and configure it

Create a ‘build’ directory. This is where our build.ninja/ output binaries and so on will get created:

cd ~/ast-analyzer; mkdir -p build; cd build

Now we need to generate the build.ninja file in order to build Clang and also the tools in the directory from the project cloned earlier (llvm/clang-tools-extra). You can do this using CMake like this:

cmake -G Ninja ../llvm-project/llvm -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" # Enable the clang-tools projects in our build as well

This should generate a build.ninja file, which I encourage you to open and check out the contents. You will see that it contains a list of targets followed by dependencies. For example, one of the targets may look something like this:

#############################################
# Utility command for install-llvm-headers

build install-llvm-headers: phony CMakeFiles/install-llvm-headers llvm-headers

We’ll also do this for the custom static analysis tool we build in the next steps.

###4. Build and install all targets specified in the build.ninja file

ninja; ninja install

Okay, the setup is done and now we get to the fun part!

How to Create the Scaffolding for the Static Analysis Tool

We’ll be building our tool as a part of the clang-tools-extra directory in llvm-project/clang-tools-extra. Let's go ahead and create that directory. We’ll call our tool class-analyzer.

mkdir ~/ast-analyzer/llvm-project/clang-tools-extra/class-analyzer
cd ~/ast-analyzer/llvm-project/clang-tools-extra/class-analyzer

Now we need to create a CMakeLists.txt. This is basically a file that tells the CMake build system to add the source files in this tool to the build.ninja file it will generate. This lets ninja know how to build our tool.

Our CMakeLists.txt file will look like this:

CMakeLists.txt

set(LLVM_LINK_COMPONENTS support)
set(CMAKE_CXX_COMPILER /usr/bin/clang++)  


add_clang_executable(class-analyzer
  ClassAnalzyer.cpp
  MyFrontendActionFactory.cpp
  MyFrontendAction.cpp
  MyASTConsumer.cpp
  )
target_link_libraries(class-analyzer
  PRIVATE
  clangAST
  clangFrontend
  clangTooling
  )

The first couple lines tell the build system that the compiler should be /usr/local/bin/clang++ (the one just built in the previous steps).

The next add_clang_executable section tells the build system which source files to build as a part of our executable. We'll get more into the details of what each source file does soon. It also tells defines the name of the executable for the build system. Here it is called class-analyzer since it analyzes class names.

The target_link_libraries section informs the build system about the Clang front end libraries we should be linking against. These are the libraries which really expose the power of Clang’s AST to the tool we'll build.

Clang's API documentation is a good place to start looking for hints on how we should start writing the class-analyzer tool. Another good place to start is by scanning the source code of the Clang project we cloned earlier, for other tools! [clang-tools-extra](https://github.com/llvm/llvm-project/tree/main/clang-tools-extra) has multiple examples – these have been a source of inspiration for the code written here.

So now, let's start with the code for our very first source file. This file is contains the main() function of the executable. It looks something like this:

#include "clang/Tooling/CommonOptionsParser.h"
#include "clang/Tooling/Tooling.h"

#include "MyFrontendActionFactory.h"

#include <memory>

using namespace clang::tooling;
using namespace llvm;

static llvm::cl::OptionCategory toolCategory("class-analyzer <options>");

int main(int argc, const char** argv)
{
    // Use clang's argument parser infrastructure
    // This is used for giving clang tooling the path
    // to the source files passed in to the tool.
    // It also gets the compilation database - a collection
    // of the compiler options used in the invocation of the tool
    auto argsParser = CommonOptionsParser::create(
        argc, argv, toolCategory);
    if (!expectedArgsParser) {
        llvm::errs() << argsParser.takeError();
        return -1;
    }
    CommonOptionsParser& optionsParser
        = argsParser.get();
    ClangTool tool(optionsParser.getCompilations(),
                   optionsParser.getSourcePathList());
    auto myActionFactory
        = std::make_unique<MyFrontendActionFactory>();

    return tool.run(myActionFactory.get());
}

This source file essentially creates a tool which runs a clang FrontendActionFactory. Now to understand what FrontendActionFactory does, let's take a look at Clang's documentation for it.

We see that it has a pure virtual method,

virtual std::unique_ptr<FrontendAction> create () = 0;

which returns an std::unique_ptr to a [FrontendAction](https://clang.llvm.org/doxygen/classclang_1_1FrontendAction.html) object. FrontendAction is, in its essence, a class which allows callers to perform custom actions as Clang parses the AST of a translation unit given to it. A translation unit in simple words is the combined code given to the compiler to create an object file. It contains code included through all the header files + code in a C / C++ source file

This will become clearer as we get further along in the article.

Now we come to writing our own FrontendActionFactory which you can call MyFrontendActionFactory. This is a very simple class which just overrides the create() virtual method. It looks like this:

// Header file MyFrontendActionFactory.h
#pragma once

include<clang/Tooling/Tooling.h>


class MyFrontendActionFactory : public clang::tooling::FrontendActionFactory{
    public:
    MyFrontendActionFactory();
    std::unique_ptr<clang::FrontendAction> create() override;
};                                                         

// Source file MyFrontendActionFactory.cpp

#include "MyFrontendActionFactory.h"
#include "MyFrontendAction.h"

MyFrontendActionFactory::MyFrontendActionFactory() {

}

std::unique_ptr<clang::FrontendAction> MyFrontendActionFactory::create() {
    return std::make_unique<MyFrontendAction>();
}

Since MyFrontendActionFactory::create() needs to return an std::unique_ptr to clang::FrontendAction, we'll need to create a clang::FrontendAction object.

If we look at the Clang documentation for FrontendAction, we'll be particularly interested in looking at what we can do with the AST (Abstract Syntax Tree) of the source.

We might spot the following method:

virtual std::unique_ptr< ASTConsumer >
CreateASTConsumer (CompilerInstance &CI, StringRef InFile) = 0;

This is a virtual method that a class which inherits from FrontendAction can implement. It returns an ASTConsumer which according to the documentation,

"...is an abstract interface that should be implemented by clients that read ASTs."

So, this method looks really promising if we want to create something that will let us read the Clang generated AST!

If we look at the FrontendAction documentation again, it shows us that ASTFrontend is a class that inherits from FrontendAction. We also learn that it is:

"The Abstract base class to use for AST consumer-based frontend actions."

It only has one pure virtual method: CreateASTConsumer(). This seems promising, since...we might be able to create our own ASTConsumer object.

So, we start by reading through ASTConsumer's documentation. We see that it has a virtual method

virtual void
clang::ASTConsumer::HandleTranslationUnit(ASTContext &Ctx)

where the documentation states:

"HandleTranslationUnit - This method is called when the ASTs for entire translation unit have been parsed".

This is exactly what we want. We can override this method to do interesting things with the parsed AST.

You might now be wondering – how exactly can we use the parameter passed to this function ASTContext to actually go through the AST?

There's a class in the Clang front end API which can help us here: RecursiveASTVisitor. This is a class that does a depth-first traversal of the Clang AST and visits each node. It has methods such as VisitDecl(), VisitStmt() and so on which can help us go through virtually the whole source file's AST.

It also has a method which is particularly interesting: TraverseDecl(). This method recursively traverses through all the declarations starting from the root declaration given to it.

Putting it All Together in Code

So now what we need to do is give TraverseDecl() the root declaration of our translation unit and it will traverse the entirety of it. We can define special 'hooks' which will get called as this traversal happens. One such hook is:

bool VisitRecordDecl(const clang::RecordDecl *record);

This is called each time the RecursiveASTVisitor traverses through a CXXRecordDecl – which is Clang speak for a C++ class. We'll overload this method with our own version to do something interesting: getting the C++ Class' name and seeing if it starts with an upper-case character.

Putting all this together, here's what we get:

// MyFrontendAction.h header file
#pragma once

#include <clang/Frontend/FrontendAction.h>

class MyFrontendAction : public clang::ASTFrontendAction {
    protected:
        std::unique_ptr<clang::ASTConsumer> CreateASTConsumer(clang::CompilerInstance &ci, llvm::StringRef file) override;
};    

// MyFrontendAction.cpp source file
#include "MyFrontendAction.h"
#include "MyASTConsumer.h"

std::unique_ptr<clang::ASTConsumer> MyFrontendAction::CreateASTConsumer(clang::CompilerInstance &ci, llvm::StringRef file) {
    return std::make_unique<MyASTConsumer>(ci, file);
}

//MyASTConsumer.h header file

#pragma once

#include<clang/AST/ASTConsumer.h>
#include<clang/Frontend/CompilerInstance.h>

class MyASTConsumer : public clang::ASTConsumer {

public:
    MyASTConsumer(clang::CompilerInstance &ci, llvm::StringRef file) {}
    void HandleTranslationUnit(clang::ASTContext &context) override;
};

// MyASTConsumer.cpp source file

#include <clang/AST/RecursiveASTVisitor.h>
#include "MyASTConsumer.h"

#include <iostream>

static bool isFirstLetterUpperCase(const std::string &str) {
    return str.size() != 0 && std::isupper(str[0]);
}
class MyASTVisitor : public clang::RecursiveASTVisitor<MyASTVisitor> {
    public:
    bool VisitCXXRecordDecl(const clang::RecordDecl *record) {
        std::string name = record->getNameAsString();

        if (!isFirstLetterUpperCase(name)) {
            std::cout << "Record Decl : " << name
                      <<" doesn't start with uppercase! \n";
        }

        return true;
    }
    bool TraverseDecl(clang::Decl *decl)  {
        return
           clang::RecursiveASTVisitor<MyASTVisitor>::TraverseDecl(decl);
    }
};

void MyASTConsumer::HandleTranslationUnit(clang::ASTContext &ctx) {
    clang::TranslationUnitDecl *tuDecl = ctx.getTranslationUnitDecl();
    MyASTVisitor visitor;
    visitor.TraverseDecl(tuDecl);
}

Now to build, we just do:

cd ~/ast-analyzer/build/; ninja class-analyzer

This builds the class-analyzer executable in the build/bin directory.

Now to test out the analyzer, we create a test.cpp source file:

// test.cpp
class Test {
public:
 int a;
};

class testLower {
public:
 int b;
};

int main() {
        return 0;
}

Run class-analyzer on it:

bin/class-analyzer test.cpp

The output of this command is :

Record Decl : testLower doesn't start with uppercase!

We can use a multitude of such Visit* methods such as VisitEnumDecl, VisitFunctionDecl, VisitVarDecl, and so on to get valuable information about the source file and create our own tools. Just think about any tool which runs and performs actions on code or gives suggestions to the user.

You may think that this seems like a lot of work for a small task. But think about the potential. For example, you could write a tool which automatically gives a user suggestions to improve their code style. Or you could create a tool which analyses C++ code and finds lines of code where there might be security vulnerabilities.

The possibilities are endless. Clang's front-end libraries are extremely powerful and you can build many cool projects and tools with them.

Summary

In this article, you learned how to get and use the rich collection of Clang's Front-end libraries to parse a C++ source AST. You can use these libraries to write interesting static code analysis tools.

As this article showed, one of the most important parts of the journey of exploring Clang's libraries is the art of reading the API documentation and applying it to the problems your tools aim to solve. I hope you enjoyed the article!

The algorithm is fast in searching for elements because it removes half of the array every time the search iteration happens.

So instead of searching through the whole array, the algorithm removes half of the array where the element to be searched for can't be found. It does this continuously until the element is found.

In a case where the element to be searched for doesn't exist, it returns a value of -1. If the element exists, then it returns the index of the element.

If the explanations above seem complex, then you should check out this visual guide on how the binary search algorithm works.

In this article, you'll see an implementation of the binary search algorithm in C++.

Let's get started!

Binary Search Algorithm Example in C++

In this section, we'll break down and explain the implementation of binary search in C++.

Here's the code:

#include <iostream>
using namespace std;

int binarySearch(int array[], int low, int high, int number_to_search_for) {

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (number_to_search_for == array[mid]){
            return mid;
        }

        if (number_to_search_for > array[mid]){
            low = mid + 1;
        }

        if (number_to_search_for < array[mid]){
            high = mid - 1;
        }

    }

  return -1;
}

int main(void) {
  int arrayOfNums[] = {2,4,7,9,10,13,20};

  int n = sizeof(arrayOfNums) / sizeof(arrayOfNums[0]);

  int result = binarySearch(arrayOfNums, 0, n - 1, 13);

  if (result == -1){
      printf("Element doesn't exist in the array");
  }
  else{
      printf("The index of the element is %d", result);
  }

  // The index of the element is 5
}

To start with, we created a method called binarySearch which had four parameters:

• array[] represents the array to be searched through.
• low represents the first element of the array.
• high represents the last element of the array.
• number_to_search_for represents the number to be searched for in array[].

Next, we created a while loop that will run continuously until the search operation returns a value – either the index of the element or -1.

In the while loop:

mid is used to represent the center/midpoint of the array: int mid = low + (high - low) / 2;.

The first if statement is executed if mid has the same value as the element to be searched for:

if (number_to_search_for == array[mid]){
    return mid;
}

The second if statement moves the position of low to the index after the midpoint of the array:

if (number_to_search_for > array[mid]){
    low = mid + 1;
}

This removes all the elements on the left side of the array because the element to be searched for is greater than they are, so there is no need to search through that part of the array.

The third if statement does the opposite of the second statement – it moves the position of high to the index before the midpoint of the array:

if (number_to_search_for < array[mid]){
    high = mid - 1;
}

Here's a summary of the code in the if statements:

1. If the number to be searched for is equal to mid, the mid index will be returned.
2. If the number to be searched for is greater than mid, search through the elements on the right side of mid.
3. If the number to be searched for is less than mid, search through the elements on the left side of mid.

If the number to be searched for doesn't exist, -1 will be returned. You can see this after the while loop in the code.

Lastly, we tested the binarySearch method:

int main(void) {
  int arrayOfNums[] = {2,4,7,9,10,13,20};

  int n = sizeof(arrayOfNums) / sizeof(arrayOfNums[0]);

  int result = binarySearch(arrayOfNums, 0, n - 1, 13);

  if (result == -1){
      printf("Element doesn't exist in the array");
  }
  else{
      printf("The index of the element is %d", result);
  }

  // The index of the element is 5
}

In the code above, we passed in the values of the parameters created in the binarySearch method: binarySearch(arrayOfNums, 0, n -1, 13).

• arrayOfNums represents the array to be searched for: {2,4,7,9,10,13,20}.
• 0 represents the first index of the array.
• n - 1 represents the last index of the array. Have a look at the code to see how n was created.
• 13 is the number to be searched for in arrayOfNums.

When you run the code, "The index of the element is 5" will be printed in the console. This is because the index of the number to be searched for (13) is 5.

You can play around with the code by changing the value of the number to be searched for.

Summary

In this article, we talked about the implementation of the binary search algorithm in C++.

We saw a code example that had a binarySearch method which took in parameters, searched through an array of numbers, and returned the appropriate value after the search operation.

We also saw a detailed explanation of each part of the code.

Happy coding!

For example, you might know that C++ is faster than Python. So why is this the case?

Well, C++ is a language that uses a compiler, not to mention it is a much lower-level programming language than Python. That is to say, C++ provides much less abstraction from a computer's instruction set and architecture.

On the other hand, Python is an interpretated language, which just means that every line of the program is evaluated as the program is running.

But, how much faster IS C++ compared to Python? In this article you will see 3 algorithms and how they perform in C++ and Python. These algorithms are from "Data Structures and Algorithms Using C++" by Michael T. Goodrich.

Note: The computer I ran these tests on was an Acer Swift 3. The CPU was a Ryzen 7 7500U with Radeon Graphics 1.80Gz. Along with 8GB of RAM, running Windows 10 Home.

You will be looking at these algorithms and their Big O Notation. Big O is a mathematical way of expressing the worst-case scenario of the time or space complexity of an algorithm.

The time complexity is the amount of time it takes for an algorithm to run, while the space complexity is the amount of space (memory) an algorithm takes up. Here is a graph to help explain Big O:

Big O Cheat Sheet – Time Complexity Chart (freecodecamp.org)

From now on, I'll refer to each algorithm as running with a certain time complexity.

For example, if I say an algorithm runs with a O(n) time complexity, this means that as the input grows, the time it takes for an algorithm to run is linear. If I say it runs with O(n^2) time complexity, this means that as the input grows, the time it takes for an algorithm to run is quadratic.

Performance of the 1st Algorithm:

Algorithm Ex1(A):
    Input: An array "A" storing n >= 1 integers.
    Output: The sum of the elements in A.

    s = A[0]
    for i = 1 to n - 1 do:
        s = s + A[i]
    return s

In Python, we can express this algorithm as:

def ex1(A):
    sum = A[0]
    for i in A:
        sum = sum + A[i]
    return sum

If you use inputs up to about 5 million you will see that this algorithm takes about 4 seconds to run with that large of an input.

Performance of the 1st Algorithm

Then you can compare this algorithm in C++, like this:

double ex1(double A[], size_t n)
{
    double sum = A[0];
    for(size_t i = 0; i < n; i++)
    {
        s = s + A[i];
    }
    return sum;
}

You may be wondering, what is size_t? size_t is an "unsigned integer". This just means that this variable does not have a sign. Which also just means that this variable is not negative.

In C++, we use size_t to keep track of positions in an array, since those positions cannot be negative (at least in C++, since in Python we can have negative indexes).

Now let's take a look at the running time of the first algorithm:

Performance of the 1st Algorithm in C++

As you can see from these two charts, the time complexity seems to be linear. This means that the time complexity of this algorithm is O(n) – as the input size for A grows, the time it takes for this algorithm to run grows linearly.

But it is interesting to notice that for very large inputs of 5 million, C++ does not even break the 1 second mark. Whereas Python breaks the 3-4 second mark for inputs at about 5 million. Let's move on to our next algorithm.

Performance of the 2nd Algorithm:

Algorithm Ex3(A):
    Input: An array "A" storing n >= 1 integers.
    Output: The sum of the prefix sums in A.
    s = 0
    for i = 0 to n - 1 do:
        s = s + A[0]
        for j = 1 to i do:
            s = s + A[j]
    return s

Here, you can see that this algorithm has two for-loops. So, moving forward this is something to acknowledge when analyzing the time complexity.

In Python, you can express this algorithm like this:

def ex3(A):
    sum = 0
    for i in range(len(A)):
        sum = sum + A[i]
        for j in range(1, i):
            sum = sum + A[j]
    return sum

Let's also use inputs all the way up to 70,000. Then we will record the times and chart the data like so:

Time Performance of the 2nd Algorithm in Python

These results are much different from our previous charts from algorithm 1. Something to point out is that with an input of 70,000, this algorithm takes a whopping 91 seconds in Python. Thats a long time!

Also, when I tried to run inputs higher than 70,000, my computer started to become unresponsive. Yikes.

Let's take a look at this algorithm in C++:

double ex3(double A[], size_t n)
{
    double s = 0;
    for(size_t i = 0; i < n; i++)
    {
        s = s + A[i];
        for(size_t j = 1; j < i; j++)
        {
            s = s + A[j];
        }
    }
    return s;
}

For the C++ code I was able to increase the input size to ~90,000.

Time Performance of the 2nd Algorithm in C++

For an input size of 70,000 this algorithm takes ~4 seconds to run in C++. That difference is huge. Not to mention, I was able to use inputs that were about ~90,000 elements in size for C++, with it not even breaking past the 10 second mark.

Also, we can see that the curve is not as smooth as the Python graph. This could be due to some other processes running in the background (since I'm running on Windows 10) or some other reason.

Also, we can classify the time complexity of this algorithm as O(n^2), which just means that the time complexity for this algorithm is quadratic.

Let's move on to the last algorithm.

Performance of the 3rd Algorithm:

Algorithm Ex5(A, B):
    Input: Arrays "A" and "B" each storing n >= 1 integers.
    Output: The number of elements in B equal to the sum of
            prefix sums in A.
    c = 0
    for i = 0 to n - 1 do:
        s = 0
        for j = 0 to n - 1 do:
            s = s + A[0]
            for k = 1 to j do:
                s = s + A[k]
            if B[i] == s then:
                c = c + 1
    return c

Let's take a look at this code in Python:

def ex3(A, B):
    c = 0
    for i in range(len(A)):
        s = 0
        for j in range(len(A)):
            s = s + A[0]
            for k in range(1, j):
                s = s + A[k]
            if B[i] == s:
                c = c + 1
    return c

Now, let's analyze the timings:

Time Performance of the 3rd Algorithm in Python

Woah, what's going on here? We can see that as our inputs starts to increase, the rate at which the algorithm runs also starts to increase, but it is increasing at a drastic rate.

In this case, we can see with an input size of 3500 that it takes 761 seconds for this algorithm to run in Python. You may be asking, "Did you actually sit through all 761 seconds?", the answer is yes. Yes, I did.

Now let's take a look at the C++ code:

double ex5(double A[], double B[], size_t n)
{
    double c = 0;
    for(size_t i = 0; i < n; i++)
    {
        double s = 0;
        for(size_t j = 0; j < n; i++)
        {
            s = s + A[0]
            for(size_t k = 1; k < j; k++)
            {
                s = s + A[k];
            }
            if(B[i] == s)
            {
                c = c + 1
            }
        }
    }
    return c;
}

Let's take a look at the graph.

Time Performance of the 3rd Algorithm in C++

Similar to the second algorithm, it is interesting to see that the curve is not as smooth as the Python graph.

Also, we can see that we can go well above an input size of 3500. My computer started acting up once I pushed the input size past 10,000 for C++. Not to mention, with an input size of 10,000 the algorithm averaged about 544-545 seconds.

We can classify this algorithm as having a time complexity of O(n!). Which just means that this algorithm is factorial, which runs very slowly.

Wrapping Up

I hope you found the differences of running times between Python and C++ just as fascinating as I have.

Also, just because Python runs slower than C++ for every algorithm does not mean that C++ is the "better" language. Both of these languages have their own purposes for the type of software you are trying to create.

C++ would be the preferred language if performance is critical. If you were programming games, operating systems, or communicating between machinery, C++ would be the better choice due to its compiled and fast nature.

Python would be preferred if you need to develop software quickly. Due to its easier learning curve, almost anyone can pick up Python and start creating software with it. Python also provides many resources for data science and machine learning.

Check out the code if you would like to try these tests on your own computer:

Cheers!

But sometimes you might need to use what is commonly referred as virtual inheritance.

In this article we will discuss when you might need to use virtual inheritance and how to implement it in C++.

What is Virtual Inheritance?

In C++, a class can inherit from multiple classes which is commonly referred as multiple inheritance. But this can cause problems sometimes, as you can have multiple instances of the base class.

To tackle this problem, C++ uses a technique which ensures only one instance of a base class is present. That technique is referred as virtual inheritance.

Example of When Virtual Inheritance is Useful

Let's look at an example and then explain what's happening:

#include <iostream>

class A {
    public:
     int x = 5;
     //some other things
};
class B : public A { // inherit from the Class A.
    public:
      int i = 6;
};
class C : public A { // inherit from the Class A.
    public:
      int i = 7;
};
class D : public B, public C { // inherit from both class B and C
    // something can go here..
};

int main(){
    D obj;
    std::cout << obj.x << std::endl;
    return 0;
}

Let's see what's going on here:

First, we have a class A which is being inherited by two classes B and C. Both of these classes are then inherited by another class D.

Inside our main function, we create a new instance (object) of the class D. We then simply tried to print the value of x to the console.

It might look legit to access the value of x here, because class D is inherited from both B and C which are ultimately inherited from the class A.

But when you try to compile the above program, you get the following error:

<source>: In function 'int main()':
<source>:21:22: error: request for member 'x' is ambiguous
   21 |     std::cout << obj.x << std::endl;
      |                      ^
<source>:5:10: note: candidates are: 'int A::x'
    5 |      int x = 5;
      |          ^
<source>:5:10: note:                 'int A::x'

The error is pretty clear: error: request for member 'x' is ambiguous. Let's now see how the request is ambiguous.

If we draw the hierarchical class structure, it should become pretty clear:

Hierarchical class structure

We can see that we have multiple instances of the class A. So the request to the variable x becomes ambiguous because the compiler doesn't know which instance we are referring to – is it through B or through C ? That's the real problem.

One Way to Solve this Problem

One way to tackle the problem is to use the scope-resolution operator (::) with which we can directly specify which instance of A we want.

int main(){
    D obj;
    std::cout << obj.B::x << std::endl;
    std::cout << obj.C::x << std::endl;
}

Using the scope-resolution operator we explicitly told the compiler which instance of A we referred to.

The main problem with this approach is that it doesn't solve our problem – because our main problem is having multiple instances of class A, and we still have that. So we need to look around for some other solutions.

And the other solution is to use virtual inheritance. Let's see how it works now.

How to Use Virtual Inheritance

To inherit virtually we simply add a keyword virtual before our base class name in the derived class declaration like this:

class B : virtual public A{
    public:
      int i = 6;
};
class C : virtual public A{
    public:
      int i = 7;
};

The addition of the virtual keyword indicates that we want to inherit from A virtually.

Inheriting virtually guarantees that there will be only one instance of the base class among the derived classes that virtually inherited it. After the changes, our hierarchical class structure becomes:

The Hierarchical structure after virtual inheritance

So now if we try to compile the following code, it will successfully compile.

#include <iostream>

class A {
    public:
     int x = 5;
};
class B : virtual public A{
    public:
      int i = 6;
};
class C : virtual public A{
    public:
      int i = 7;
};
class D : public B, public C{

};

int main(){
    D obj;
    std::cout << obj.x << std::endl;

}

So with the introduction of virtual inheritance we are able to remove the ambiguities we had earlier.

Wrapping Up

In this article you learnt about the problem you might face while inheriting a class and a way to solve it using virtual inheritance.

Happy Coding!

You might have also needed to do this by either using a user-defined function or not using any function at all.

If this problem seems kind of complicated to you, then don't worry! I have come to help you. So, let's dive into the question real quick and see how it works.

🎥 If you are the kind of person that loves to follow along with a video too, I have also created a video for you:

Understand The Question – Then Start Solving

For solving any kind of problem, the first thing you have to do is to understand the question first. Not only that, you also need to pay close attention to all the instructions including the required criteria for solving that problem.

If your question asks you to use recursion, that's the technique you'll employ. If your question asks you not to use any built-in special functions, you'll avoid those.

For this article, I will be using only one question but with two different criteria. I will go through the process to help you understand what you would need to do from the beginning for solving the problem.

Here's the question with its criteria:

Create an integer array. Take the array elements as input from the user and print all the array elements in the given order and later in reverse order. You can't use any user-defined function.

Alright, now that we have our question, make sure you've read it fully. If reading it through one time does not make it clear in your mind, then read it two or three – or even more – times.

Then also look into the given criteria carefully. The question tells you that you can not use any user defined function. That means you can not add any kind of manually user-defined function in your code like myFunction(), and so on.

For this article, I will be using the C++ programming language. But if you can understand the core concept then you can use any other programming language to solve this problem. After solving the problem, make sure to add your solution to this GitHub repository.

Also, if you like to solve problems using programming languages, then make sure to check my ongoing YouTube playlist where I solve problems using the programming language.

How to Solve the Problem

In C/C++, if you declare an array without initializing the value, then you need to specify the array size as well.

When you declare the array with the array size, it automatically takes the necessary space in the memory for the entire array. So, if you take a larger array than you actually need, you will waste memory, as it takes the full space in memory for the full array whether you use all the indexes or not.

So first, we want the user to input the array size (how many numbers they want us to process). Then we will create the array with the given array size. In that way, we can save unnecessary memory wastage.

Well, as today's computers are more powerful, you would likely not notice any differences in memory wastage, as it would be pretty negligible. But trust me, you do need to understand how to save memory as that is one of the biggest concerns in today's world. Also, you never know when this knowledge will help you later, right?

    cout << "Enter the array size: ";
    int arraySize;
    cin >> arraySize;
    int arr[arraySize];

Well then, after declaring our array, we will take the array elements from the user. We can simply use a for() loop for that.

    cout << "Enter the array elements " << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cin >> arr[i];
    }

In this way, we can take each value from the user and store it in our array in a sequential way. Keep in mind that the array always starts from the 0 index (the first element is at index 0, the second is at index 1, and so on).

Now it is time to print all the array elements (the value that each index of the array has) in the given order. That means we have to print the entire array in the same order we received from the user.

    // printing the array in the correct order
    cout << "Printing the array in the original order" << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cout << arr[i] << " ";
    }

For printing the array in reverse order, we can simply print the array in a backwards direction. In this way, the last indexed value from the array will get printed first. Then the second to last indexed value (from the right side of the array) would get printed in the second position, and so on.

    // printing the array in the reverse order
    cout << "\nPrinting the array in the reversed order" << endl;
    for (int i = arraySize - 1; i >= 0; i--)
    {
        cout << arr[i] << " ";
    }

That's it! Through this, you can solve the problem easily. Notice that we did not use any kind of user-defined function in our entire code. Thus, we also made sure that we successfully met all of the criteria.

The entire code now looks like this:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cout << "Enter the array size: ";
    int arraySize;
    cin >> arraySize;
    int arr[arraySize];
    cout << "Enter the array elements " << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cin >> arr[i];
    }
    // printing the array in the correct order
    cout << "Printing the array in the original order" << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cout << arr[i] << " ";
    }
    // printing the array in the reverse order
    cout << "\nPrinting the array in the reversed order" << endl;
    for (int i = arraySize - 1; i >= 0; i--)
    {
        cout << arr[i] << " ";
    }    
}

Here's another example question and criteria:

Create an integer array. Take the array elements as input from the user and print all the array elements in the given order and later in the reverse order. You have to use a user-defined function for printing the array in reverse order.

Now, this time the criteria has been changed. The only difference is that we need to use a user defined function right now.

If you can understand the previous technique and the code, then most probably you have already guessed how to solve this problem. We have to shift the part of the code that prints the array in the reverse order to a new user-defined function. Simply doing that will solve our problem.

For example, I am going to name the new user-defined function printReversely(int arr[], int arraySize). You can name it however you want by following the naming conventions of C++ (or whatever programming language you're using).

I am simply giving you the entire code for now:

#include <bits/stdc++.h>
using namespace std;
void printReversely(int arr[], int arraySize);
int main()
{
    cout << "Enter the array size: ";
    int arraySize;
    cin >> arraySize;
    int arr[arraySize];
    cout << "Enter the array elements " << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cin >> arr[i];
    }
    // printing the array in the correct order
    cout << "Printing the array in the original order" << endl;
    for (int i = 0; i < arraySize; i++)
    {
        cout << arr[i] << " ";
    }
    // printing the array in the reverse order
    cout << "\nPrinting the array in the reversed order" << endl;
    printReversely(arr, arraySize);
}

void printReversely(int arr[], int arraySize)
{
    for (int i = arraySize - 1; i >= 0; i--)
    {
        cout << arr[i] << " ";
    }
}

In C/C++, the code execution always starts from the upper left corner.

As I wrote my printReversely(int arr[], int arraySize) function after the main function, I added the declaration part of it before the main() function. This will help the compiler determine whether it has access to the function or not. If you do not do that, then you'll get an error.

But if you write the entire printReversely(int arr[], int arraySize) function before the main() function then you do not necessarily need to add the declaration again before that.

Conclusion

Thanks for reading the entire article. If it helps you then you can also check out other articles of mine at freeCodeCamp.

If you want to get in touch with me, then you can do so using Twitter, LinkedIn, and GitHub.

You can also SUBSCRIBE to my YouTube channel (Code With FahimFBA) if you want to learn various kinds of programming languages with a lot of practical examples regularly.

If you want to check out my highlights, then you can do so at my Polywork timeline.

You can also visit my website to learn more about me and what I'm working on.

Thanks a bunch!

Before approaching the process of running your first C or C++ code on Visual Studio Code, let me guide you through the process and get it all set up based on the operating system you are using on your computer.

C and C++ compilers

For running C or C++ code, you just need to have a valid C/C++ compiler installed on your computer. If you are using a Linux operating system, then there is a high chance that it is already installed on your system. But we need to make sure that it is correctly installed.

For checking whether or not you have the compiler (GCC/G++/MinGW) installed on your system or not, you have to check the compiler version first.

Simply open your terminal and use gcc --version and g++ --version. If you get the version number, then the compiler is already installed on your system.

You can check the version using the same commands on any operating system, whether that is a Windows, Linux, or macOS-based operating system.

If you get feedback on your terminal that it does not know anything about GCC or G++, then you have to install the compiler correctly.

If you are using the most used Windows operating system, then I already have written an in-depth article showing you all the processes step-by-step on freeCodeCamp. Make sure to read the entire article first, as it also contains a complete video to provide you with complete support.

Embedded content

If you are using another operating system, and you don't have the compilers installed, then make sure to install them before proceeding.

How to Install VS Code or VS Code Insiders

You have to download Visual Studio Code directly from the official website: https://code.visualstudio.com/.

If you want, you can also install VS Code Insiders, and the same process is applicable for that as well.

Visual Studio Code Insiders is actually the "Insiders" build of Visual Studio Code, which contains all the latest features that are shipped daily. You can think of VS Code as the stable release and the VS Code Insiders as the Insiders release of that.

If you want to experience the latest updates instantly, then you might also try Visual Studio Code Insiders (I use it myself). For downloading VS Code Insiders, you can visit the official website for VS Code Insiders here: https://code.visualstudio.com/insiders/

Make sure to download the exact file for your operating system.

Download Page: VS Code

Download Page: VS Code Insiders

The installation process is pretty basic. But I am going to show you all the steps sequentially. For now, I am going to show you the installation process using VS Code Insiders, but everything you will see here is going to be exactly the same for VS Code as well.

Make sure to click the box on the "I accept the agreement " box and click on Next.

Accept the agreement and click Next

Keep everything as it is. Do not change anything from here.

Click Next

Click Next. Again, simply click Next.

Click Next

Make sure to add the checkmark (✔) on all of the boxes. Then click on Next.

Check all of the boxes, and click Next

Click on Install.

Click Install

It might take a little time to finish the installation.

Let it finish...

Click on Finish.

Click Finish

Congrats - you've successfully installed VS Code/VS Code Insiders on your system. Now, cheers! 🥂

How to Prepare VS Code/VS Code Insiders For C and C++ Code

First, open VS Code or VS Code Insiders.

Go to the Extension tab. Search for "C" or "C++" and install the first one that is already verified by Microsoft itself.

Install C/C++ extension

Also, install C/C++ Extension Pack. It should also be verified by Microsoft.

Install C/C++ Extension Pack

Then you have to search for Code Runner and install the extension as well.

Install Code Runner Extension

Now, we need to change some settings.

Change some settings

Click the gear box (It is called the Manage section), and then click Settings. Alternatively, you can also use the shortcut keys Ctrl + ,. You need to replace the Ctrl key with the Command key for Mac.

Type "Run code in terminal" and press Enter key

In the search bar, type "Run code in terminal" and press the Enter key.

Scroll down a little bit until you find Code-runner: Run In Terminal. Make sure that the box is checked (✔).

Make sure to check the box

Now you need to restart your VS Code/VS Code Insiders. Simply close and reopen the program.

How to Test Your Code

Simply open VS Code/VS Code Insiders, open any folder, and create any file with the extension .c for the C file and .cpp for the C++ file.

After writing your code, you can run the code directly using the play button you'll find in the upper right corner.

This is how you can run any C/C++ program from VS Code/Insiders

It will compile and then run the code directly. After running a code, the code runner button would be set default to run directly. So, your computer is 100% ready for compiling and running any C/C++ programming code. 😀

Conclusion

Thanks for reading the entire article. If it helps you then you can also check out other articles of mine at freeCodeCamp.

If you want to get in touch with me, then you can do so using Twitter, LinkedIn, and GitHub.

You can also SUBSCRIBE to my YouTube channel (Code With FahimFBA) if you want to learn various kinds of programming languages with a lot of practical examples regularly.

If you want to check out my highlights, then you can do so at my Polywork timeline.

You can also visit my website to learn more about me and what I'm working on.

Thanks a bunch!

Type casting can be done implicitly or explicitly.

Implicit type casting gets done automatically via the compiler, while explicit type casting is done by the developer.

In this article, you'll learn how to convert an integer to a string in C++ using the stringstream class and the to_string() method.

How to Convert an Int to a String in C++ Using the stringstream Class

Using the stringstream class, we can convert an integer to a string.

Here's an example to help you understand why you'd need to convert an integer to a string:

#include <iostream>
using namespace std;

int main() {

    int age = 20;

    cout << "The user is " + age + " years old";
    // error: invalid operands of types 'const char*' and 'const char [11]' to binary 'operator+'

    return 0; 

}

In the example above, we created an int variable with a value of 20.

When we tried to concatenate that value in a string, we got an error saying "invalid operands of types...".

The error was raised because we tried to perform an operation using two incompatible variable types. The solution would be to convert one variable and make it compatible with the other.

The stringstream class has insertion (<<) and extraction (>>) operators.

The insertion operator is used to pass a variable to the stream. In our case, to pass an integer to the stream.

The extraction operator is used to give out the modified variable.

In other words, a stringstream object would take in a data type, convert it to another data type, and assign the new data type to a variable.

Here's an example:

#include <iostream>
#include <sstream>  
using namespace std;

int main() {

    int age = 20;

    // stringstream object
    stringstream stream;

    // insertion of integer variable to stream
    stream << age;

    // variable to hold the new variable from the stream
    string age_as_string;

    // extraction of string type of the integer variable
    stream >> age_as_string;

    cout << "The user is " + age_as_string + " years old";
    // The user is 20 years old

    return 0; 

}

In the code above, we created a stringstream object called stream. Note that you must include the stringstream class before you can use it: include <sstream>.

We then inserted the integer into the stream: stream << age;.

After that, we created a new variable called age_as_string. This variable will store the string variable that will be extracted from the stream.

Lastly, we extracted the string type of the integer and stored it in the variable created above: stream >> age_as_string;.

Now we can concatenate the strings and get the desired result:

    cout << "The user is " + age_as_string + " years old";
    // The user is 20 years old

How to Convert an Int to a String in C++ Using the to_string() Method

You can use the to_string() method to convert int, float, and double data types to strings.

Here's an example:

#include <iostream>
using namespace std;

int main() {

    int age = 20;

    string age_as_string = to_string(age);

    cout << "The user is " + age_as_string + " years old";
    // The user is 20 years old

    return 0; 

}

In the code above, we passed in the age variable to the to_string(): string age_as_string = to_string(age);.

This converted the age variable to a string. Just like the example in the last section, we can now use the variable as a string:

cout << "The user is " + age_as_string + " years old";
// The user is 20 years old

Summary

In this article, we talked about the different ways of converting an integer to a string in C++.

The examples showed how to use the stringstream class and the to_string() method to convert an integer to a string.

Happy coding!

You'll get to know how the algorithm works with the help of visual guides. You'll also see some code examples that will help you implement the algorithm in C++ and Java.

Last but not the least, we'll talk about the time complexity for the quick sort algorithm in worst, average, and best case complexity scenarios.

Let's get started!

How Does the Quick Sort Algorithm Work?

The quick sort algorithm is based on the divide and conquer rule. In a given array of unordered elements (numbers), a pivot is chosen. The pivot is important because other elements will be sorted in respect to its value.

At the end of the sorting operation, all the numbers lower than the pivot will be moved to the left side of the pivot while all numbers higher will be on the right. This is also known as partitioning.

At this stage, the numbers on the right and left of the pivot may/will most likely be unordered.

Next, the unordered numbers before and after the pivot are put into separate arrays – one array for the numbers on the left and another for those on the right.

A pivot will then be chosen in each array and the process from the start is repeated until each number is sorted out separately. Combining all the numbers, you'll have a sorted array in ascending order.

Here's a summary of the above explanations:

Step #1: An array of unordered numbers is given.

Step #2: One number is chosen as the pivot.

Step #3: Numbers lower than the pivot move to the left side of the pivot.

Step #4: Numbers higher than the pivot move to the right side of the pivot.

Step #5: The array is broken down into two arrays – the first array will contain elements on the left side of the pivot while the second array will contain elements on the right.

Step #6: Step #2 to #5 is repeated for each array until every element has been sorted in ascending order.

The steps above may seem confusing. You'll understand it better in the next section with the help of visual guides.

How Does Quick Sort Work?

In the last section, I gave a brief summary of what happens when you use the quick sort algorithm to sort an array of numbers. But that didn't explain how the sorting operation works under the hood.

In this section, using visual guides, you'll understand how numbers are moved to either the left or right side of the pivot, and how sub arrays are created (also known as partitioning). This will also help you understand the code easily when we get to that part.

Here's the array we'll be working with: 9,4,8,3,7,1,6,2,5.

The array above has a set of unordered numbers. So how does quick sort work?

As I explained in the previous section, we have to select one element to act as the pivot.

So let's take 5 as the pivot. We'll also need two variables: X and Y. They will be used to compare and interchange the positions of numbers in respect to the pivot.

Here's what that looks like:

quick-sort parameters

In the image above, we have three arrows: red, blue, and yellow which denote X, Y, and the pivot, respectively.

The operation is pretty simple:

• If the value of y is greater than the pivot, increment Y.
• If the value of y is less than or equal to the pivot, increment X, and swap the x with y.

Let's demonstrate that using the array in the image above: 9,4,8,3,7,1,6,2,5.

Iteration #1

Pivot = 5.
Y = 9.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #2

Pivot = 5.
Y = 4.

Is Y less than or equal to the pivot? Yes.

Step #1 - Increment X

Step #2 - Swap the value of X and Y

Step #3 - Increment Y

Iterations #1 and #2 are basically all that happens during the sorting operation.

In order to help you understand better, I'll go over all the iterations until we have numbers smaller than the pivot on the left and those higher on the right.

Iteration #3

Pivot = 5.
Y = 8.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #4

Pivot = 5.
Y = 3.

Is Y less than or equal to the pivot? Yes.

Step #1 - Increment X

Step #2 - Swap the value of X and Y

Step #3 - Increment Y

Iteration #5

Pivot = 5.
Y = 7.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #6

Pivot = 5.
Y = 1.

Is Y less than or equal to the pivot? Yes.

Step #1 - Increment X

Step #2 - Swap the value of X and Y

Step #3 - Increment Y

Iteration #7

Pivot = 5.
Y = 6.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #8

Pivot = 5.
Y = 6.

Is Y less than or equal to the pivot? Yes.

Step #1 - Increment X

Step #2 - Swap the value of X and Y

Step #3 - Increment Y

Iteration #9

At this point, Y is now pointing to the pivot. You can either increment X and swap if with Y, or you can use the format in the previous iterations. I'll go with the latter.

Pivot = 5.
Y = 5.

Is Y less than or equal to the pivot? Yes.

Step #1 - Swap the value of X and Y

Our array now looks like this: 4,3,1,2,5,8,6,9,7

If you look at the current state of the array, you'd realize that:

• The pivot is now at the center.
• All the numbers on the left side of the pivot are lower than the pivot.
• All the numbers on the right side of the pivot are higher than the pivot.

But we're not yet done. The numbers are still unordered. To sort them, we'll break the array down into two sub arrays (excluding the pivot element).

The first array will have all the numbers on the left side of the pivot: 4,3,1,2.

The second array will have all the numbers on the right side of the pivot: 8,6,9,7.

Let's sort the first array. As usual, you need a pivot.

Iteration #1

Pivot = 2.
Y = 4.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #2

Pivot = 2.
Y = 3.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #3

Pivot = 2.
Y = 1.

Is Y less than or equal to the pivot? Yes.

Step #1 - Increment X

Step #2 - Swap the value of X and Y

Step #3 - Increment Y

Iteration #3

Pivot = 2.
Y = 2.

Is Y less than or equal to the pivot? Yes.

Step #1 - Swap the value of X and Y

Again, we break down the array into sub arrays excluding the pivot (2). Note that we're still dealing with the numbers on the left side of the initial array.

The first array will have this: 1.

The second array will have these: 4,3.

The first array has only one element so it is already sorted. Let's sort the second array:

Iteration #1

Pivot = 3.
Y = 4.

Is Y less than or equal to the pivot? No.

Increment Y.

Iteration #2

Pivot = 3.
Y = 3.

Is Y less than or equal to the pivot? Yes.

Step #1 - Swap the value of X and Y

We'll now have the numbers in this order:

All the numbers on the left side of the first pivot have been sorted in ascending order: 1,2,3,4,5,8,6,9,7.

The process is the same for sorting the numbers on the right side. It's time to attempt doing it yourself! Just follow the steps in previous examples.

Quick Sort Algorithm Java Code Example

Here is a code example in Java for the quick sort algorithm. I've included comments to make the code easier to understand.

If you have followed along in the previous sections then this should be self-explanatory.

// Quick sort in Java

import java.util.Arrays;

class Quicksort {

    // method for swapping elements x and y
    static void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

  // partition method
  static int partition(int array[], int low, int high) {

    //pivot
    int pivot = array[high];

    int x = (low - 1);



    // loop for comparing all elements with pivot element
    for (int y = low; y < high; y++) {
      if (array[y] <= pivot) {
        x++;

        swap(array, x, y);
      }

    }

    int temp = array[x + 1];
    array[x + 1] = array[high];
    array[high] = temp;

    return (x + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      int array_partition = partition(array, low, high);

      // quick sort elements on the left recursively
      quickSort(array, low, array_partition - 1);

      // quick sort elements on the right recursively
      quickSort(array, array_partition + 1, high);
    }
  }
}

class Main {
  public static void main(String args[]) {

    int[] my_array = { 9,4,8,3,7,1,6,2,5 };

    int size = my_array.length;

    Quicksort.quickSort(my_array, 0, size - 1);

    System.out.println("Sorted Array: ");
    System.out.println(Arrays.toString(my_array));
    // Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
  }
}

Quick Sort Algorithm C++ Code Example

Here's an example of the quick sort algorithm in C++:

#include <bits/stdc++.h>
using namespace std;

// function for swapping elements x and y
void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int arr[], int low, int high)
{
    // pivot
    int pivot = arr[high]; 
    int x = (low- 1); 

    // loop for comparing all elements with pivot element
    for (int y = low; y <= high - 1; y++) {

        if (arr[y] < pivot) {
            x++; 
            swap(&arr[x], &arr[y]);
        }
    }
    swap(&arr[x + 1], &arr[high]);
    return (x + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high) {

        int array_partition = partition(arr, low, high);

        // quick sort elements on the left recursively
        quickSort(arr, low, array_partition - 1);

        // quick sort elements on the right recursively
        quickSort(arr, array_partition + 1, high);
    }
}

// print array function 
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int arr[] = { 9,4,8,3,7,1,6,2,5 };

    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size - 1);
    cout << "Sorted array: ";
    printArray(arr, size);
    // Sorted array: 1 2 3 4 5 6 7 8 9 

    return 0;
}

Time Complexity for Quick Sort Algorithm

Worst case => O(n²)

Average case => O(n*log(n))

Best case => O(n*log(n))

Summary

In this article, we talked about the quick sort algorithm.

We gave a brief explanation of how the algorithm works. After that, we saw an example that explained how it works under the hood using visual guides to sort an unordered array.

We also saw how to implement the quick sort algorithm in Java and C++.

Lastly, we listed the quick sort time complexity for worst, average, and best case.

Happy coding!

A real-world example of a bubble sort algorithm is how the contact list on your phone is sorted in alphabetical order. Or the sorting of files on your phone according to the time they were added.

In this article, I will explain all you need to know about the bubble sort algorithm with some infographics I’ve prepared. I will then show you example code of the bubble sort algorithm in Python, Java, and C++.

Table Of Contents

• How the Bubble Sort Algorithm Works
  • First Iteration of the Sorting
  • Second Iteration of the Sorting and the Rest
• Python Code Example of Bubble Sort Algorithm
• Java Code Example of Bubble Sort Algorithm
• C++ Code Example of Bubble Sort Algorithm
• Final Thoughts

How the Bubble Sort Algorithm Works

To implement a bubble sort algorithm, developers often write a function, and then a loop within a loop – inner loop and outer loop. You will see it in action when I show you the code in Python, C++, and Java.

Let's say we want to sort a series of numbers 5, 3, 4, 1, and 2 so that they are arranged in ascending order…

The sorting begins the first iteration by comparing the first two values. If the first value is greater than the second, the algorithm pushes the first value to the index of the second value.

First Iteration of the Sorting

Step 1: In the case of 5, 3, 4, 1, and 2, 5 is greater than 3. So 5 takes the position of 3 and the numbers become 3, 5, 4, 1, and 2.

Step 2: The algorithm now has 3, 5, 4, 1, and 2 to compare, this time around, it compares the next two values, which are 5 and 4. 5 is greater than 4, so 5 takes the index of 4 and the values now become 3, 4, 5, 1, and 2.

Step 3: The algorithm now has 3, 4, 5, 1, and 2 to compare. It compares the next two values, which are 5 and 1. 5 is greater than 1, so 5 takes the index of 1 and the numbers become 3, 4, 1, 5, and 2.

Step 4: The algorithm now has 3, 4, 1, 5, and 2 to compare. It compares the next two values, which are 5 and 2. 5 is greater than 2, so 5 takes the index of 2 and the numbers become 3, 4, 1, 2, and 5.

That’s the first iteration. And the numbers are now arranged as 3, 4, 1, 2, and 5 – from the initial 5, 3, 4, 1, and 2. As you might realize, 5 should be the last number if the numbers are sorted in ascending order. This means the first iteration is really completed.

Second Iteration of the Sorting and the Rest

The algorithm starts the second iteration with the last result of 3, 4, 1, 2, and 5. This time around, 3 is smaller than 4, so no swapping happens. This means the numbers will remain the same.

The algorithm proceeds to compare 4 and 1. 4 is greater than 1, so 4 is swapped for 1 and the numbers become 3, 1, 4, 2, and 5.

The algorithm now proceeds to compare 4 and 2. 4 is greater than 2, so 4 is swapped for 2 and the numbers become 3, 1, 2, 4, and 5.

4 is now in the right place, so no swapping occurs between 4 and 5 because 4 is smaller than 5.

That’s how the algorithm continues to compare the numbers until they are arranged in ascending order of 1, 2, 3, 4, and 5.

Python Code Example of Bubble Sort Algorithm

Here’s a code example showing the implementation of the bubble sort algorithm in Python:

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in ascending order:  [1, 2, 3, 4, 5]

To make the sorting appear in descending order, just replace the greater than symbol (>) with lesser than (<):

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] < arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in descending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in descending order:  [5, 4, 3, 2, 1]

Here’s a version of the code where I added comments to so you can know what’s going on:

# Define a function to create the sorting and pass in an array as the parameter
def bubble_sort(arr):
    # Get the length of the array
    arr_len = len(arr)
    # Loop through the array to access the elements in it, including the last one - outer loop
    for i in range(arr_len-1):
        # declare a flag variable to check if a swap has occured - for optimization
        flag = 0
        # create a loop to compare each element of the array till the last one
        for j in range(0, arr_len-i-1):
            # compare 2 adjacent elements and sort them in ascending order
            if arr[j] > arr[j+1]:
                # Swap the elements if they are not in the right order
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                # break out of the loop at 0
                if flag == 0:
                    break
    # return value must be in the outer loop block
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in ascending order:  [1, 2, 3, 4, 5]

Java Code Example of Bubble Sort Algorithm

To implement the bubble sort algorithm in Java, you have to write more code than you did with Python.

That’s why I added comments to let you know about the steps as they are executed:

import java.util.Arrays;

class Main {
  static void bubbleSort(int array[]) {
    int size = array.length;
    // loop over each element of the array to access them
    for (int i = 0; i < size - 1; i++)
      // compare the elements of the array with a loop
      for (int j = 0; j < size - i - 1; j++)
        // compare two adjacent elements in the array
        if (array[j] > array[j + 1]) {
          // Swap if the elements aren't in the right order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
    int[] data = { 5, 3, 4, 1, 2 };
    // call the method using class name
    Main.bubbleSort(data);

    System.out.println("Array sorted with bubble sort: ");
    System.out.println(Arrays.toString(data));
  }
}

// Output: Array sorted with bubble sort: [1, 2, 3, 4, 5]

C++ Code Example of Bubble Sort Algorithm

Like I did for Java, I also added comments to the implementation of the bubble sort algorithm in C++ because it’s more verbose than that of Python and Java:

#include <iostream>

using namespace std;

// create a function to execute bubble sort
void bubble_sort(int array[], int size) {
  // loop over each element of the array to access them - outer loop
  for (int step = 0; step < (size-1); ++step) {
    // check if swapping occurs
    int swapped = 0;
    // loop over each element of the array to compare them - inner loop
    for (int i = 0; i < (size-step-1); ++i) {
     // compare 2 adjacent elements and sort them in ascending order
      if (array[i] > array[i + 1]) {

        //Swap the elements if they are not in the right order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;

        swapped = 1;
      }
    }

    // break out of the loop if no swapping occurs anymore
    if (swapped == 0)
      break;
  }
}

// print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {5, 3, 4, 1, 2};
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);

  // call the function   
  bubble_sort(data, size);

  cout << "Array sorted with bubble sort: \n";
  printArray(data, size);
}

// Output: Array sorted with bubble sort: 1  2  3  4  5

Final Thoughts

I won’t say the implementation of the bubble sort algorithm is either simple or hard. For an experienced programmer, it’s not hard, but for a beginner, it could be intimidating at first.

However, to really understand how the algorithm works, you need to know that:

• you need to write a function to pass the data [or array] into
• you need to write an outer loop to access the elements
• you need to write an inner loop to compare the elements
• you need to call the function and pass in the data (array)

I hope this article helps you understand the bubble sort algorithm and how to implement it.

Thank you for reading.

In C++, you can store them in arrays, structures, vectors, strings and so on. While these data structures have their distinctive features, we'll focus mainly on the various methods of initializing vectors.

Before that, let's talk briefly about vectors and what makes them stand out when dealing with data collections in C++.

What are Vectors in C++?

Unlike arrays in C++ where the memory allocated to the collection is static, vectors let us create more dynamic data structures.

Here's an array in C++:

#include <iostream>
using namespace std;

int main() {
    string names[2] = {"Jane", "John"};
    cout << names[1];
    // John
}

The array in the code above was created and allocated space enough to contain only two items. Attempting to assign new values through a new index would throw an error our way.

With vectors, things are a bit different. We don't have to specify the vector's capacity when it's defined. Under the hood, the vector's allocated memory changes as the size of the vector changes.

Syntax for Vectors in C++

Declaring a vector is different from initializing it. Declaring a vector means creating a new vector while initializations involves passing items into the vector.

Here's what the syntax looks like:

vector <data_type> vector_name

Every new vector must be declared starting with the vector keyword. This is followed by angle brackets which contain the the type of data the vector can accept like strings, integers, and so on. Lastly, the vector name - we can call this whatever we want.

Note that you must put include <vector> at the top of your file to be able to use vectors.

How to Initialize a Vector in C++

In this section, we'll go over the different ways of initializing a vector in C++. We'll divide them into sub-sections with some examples for each sub-section.

Let's start with the most basic.

How to Initialize a Vector in C++ Using the push_back() Method

push_back() is one out of the many methods you can use to interact with vectors in C++. It takes in the new item to be passed in as a parameter. This allows us to push new items to the last index of a vector.

Here's an example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> myVector;

    myVector.push_back(5);
    myVector.push_back(10);
    myVector.push_back(15);

    for (int x : myVector)
        cout << x << " ";
        // 5 10 15 
}

In the code above, we created an empty vector: vector<int> myVector;.

Using the push_back(), we passed in three new numbers to the vector.

We the looped through these new numbers and logged them out to the console.

How to Initialize a Vector When Declaring the Vector in C++

Just like arrays, we can assign values to a vector when it is being declared.

Here's an example:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> myVector{ 5, 10, 15 };

    for (int x : myVector)
        cout << x << " ";
        // 5 10 15 
}

In this example, both declaration and initialization were done at the same time.

At the point of declaring the vector, we passed in three numbers and then looped through and printed them out.

You'll notice that I put int between the angle brackets. This is to show that the data the vector will hold is specifically integers.

How to Initialize a Vector From an Array in C++

In this section, we'll first create and initialize an array. Then we'll copy all the items in the array into our vector using two vector methods – begin() and end().

Let's see how that works.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int myArray[] = { 5, 10, 15 };

    vector<int> myVector(begin(myArray), end(myArray));


    for (int x : myVector)
        cout << x << " ";
        // 5 10 15 
}

We can also initialize a vector from another vector using the same methods above. You'll have to define the first vector then use the begin() and end() methods to copy its values into the second vector.

How to Initialize a Vector by Specifying the Size and Value in C++

We can specify the size and items of a vector during its declaration. This is mainly in situations where the vector is required to have a specific value all through.

Here's an example:

#include <iostream>
#include <vector>
using namespace std;

int main() {

  int num_of_items = 5; 

  vector<int> myVector(num_of_items, 2); 

      for (int x : myVector)
        cout << x << " ";
//         2 2 2 2 2 
}

In the code above, we first defined a variable and passed a value of 5 to it. This acts as the maximum number of values the vector will have.

We then declared our vector: vector myVector(num_of_items, 2);. The first parameter is the maximum number of items variable while the second parameter is the actual item to be stored in the vector.

We looped through and logged out the items in the vector. We got 2 printed five times.

How to Initialize a Vector Using a Constructor in C++

We can also initialize vectors in constructors. We can make the values to be a bit dynamic. This way, we don't have to hardcode the vector's items.

Here's an example:

#include <iostream>
#include <vector>
using namespace std;

class Vector {
    vector<int> myVec;

public:
    Vector(vector<int> newVector) {
        myVec = newVector;
    }

    void print() {
        for (int i = 0; i < myVec.size(); i++)
            cout << myVec[i] << " ";
    }

};

int main() {
    vector<int> vec;

    vec.push_back(5);
    vec.push_back(10);
    vec.push_back(15);

    Vector vect(vec);
    vect.print();
    // 5 10 15 
}

Let's break the code down.

class Vector {
    vector<int> myVec;

public:
    Vector(vector<int> newVector) {
        myVec = newVector;
    }

    void print() {
        for (int i = 0; i < myVec.size(); i++)
            cout << myVec[i] << " ";
    }

};

We created a class called Vector. Then we created a vector variable called myVec.

After that, we defined our constructor. The constructor has two methods – one that takes in an initialized vector and another that prints out the items in the vector.

int main() {
    vector<int> vec;

    vec.push_back(5);
    vec.push_back(10);
    vec.push_back(15);

    Vector vect(vec);
    vect.print();
    // 5 10 15 
}

Lastly, as you can see in the code above, we created a new vector and pushed in new items to it. We then went on to log these items to the console.

The logic in main was created in the Vector class which also has a constructor.

Conclusion

In this article, we talked about vectors in C++.

We started by differentiating arrays and vectors. Arrays have a static size while vectors are more dynamic and can expand as items are added.

We then went over a few methods which we can use to initialize a vector in C++ with examples for each section.

Happy coding!