Comparing modern C++ and Rust in terms of safety and performance

C++ and Rust are two popular programming languages that offer a balance between performance and safety. While C++ has been around for decades and is widely used in many applications, Rust is a relatively new language that has gained popularity for its safety features. In this post, we will compare the safety and performance of modern C++ and Rust.

Safety

Null Pointers:

One of the most common errors in C++ is null pointer dereferencing. A null pointer is a pointer that does not point to a valid memory location. Dereferencing a null pointer can result in a segmentation fault, which can crash the program. In C++, it is the responsibility of the programmer to ensure that pointers are not null before dereferencing them.

Rust, on the other hand, has a built-in option type that ensures that a value is either present or absent. This eliminates the need for null pointers. For example, consider the following C++ code:

int* ptr = nullptr;
*ptr = 42;

This code will crash with a segmentation fault, because the pointer ptr is null. In Rust, we would write this code as follows:

let mut opt = None; 
opt = Some(42);

In this case, opt is an option type that is either Some with a value or None. If we try to access opt when it is None, Rust will throw a runtime error. This eliminates the possibility of null pointer dereferencing.

Data Races:

Another common error in concurrent programming is data races. A data race occurs when two or more threads access the same memory location simultaneously, and at least one of the accesses is a write. This can result in undefined behavior, including incorrect results or crashes.

C++ has a number of synchronization primitives that can be used to prevent data races, such as mutexes and condition variables. However, it is the responsibility of the programmer to ensure that these primitives are used correctly. In Rust, the ownership and borrowing system ensures that only one thread can modify a value at a time, preventing data races. For example, consider the following C++ code:

#include <thread>
#include <iostream>

int x = 0;
void increment() 
{
  for (int i = 0; i < 1000000; i++) 
  { x++; } 
} 

int main() 
{
  std::thread t1(increment);
  std::thread t2(increment);
  t1.join();
  t2.join();
  std::cout << x << std::endl; 
}

In this code, we have two threads that increment the variable x simultaneously. This can result in a data race, because both threads are modifying the same memory location. In Rust, we can use the ownership and borrowing system to prevent this kind of error:

use std::sync::Mutex;

let x = Mutex::new(0);

let t1 = std::thread::spawn(|| {
    for _ in 0..1000000 {
        let mut x = x.lock().unwrap();
        *x += 1;
    }
});

let t2 = std::thread::spawn(|| {
    for _ in 0..1000000 {
        let mut x = x.lock().unwrap();
        *x += 1;
    }
});

t1.join().unwrap();
t2.join().unwrap();

println!("{}", *x.lock().unwrap());

In this code, we use a mutex to ensure that only one thread can modify x at a time. This prevents data races and ensures that the output is correct.

Performance:

Compilation Time: One area where C++ has traditionally been faster than Rust is in compilation time. C++ compilers have been optimized for decades to compile large code bases quickly. However, Rust has been improving its compilation times with recent releases.

For example, consider compiling the following C++ code:

#include <iostream>

int main() {
    std::cout << "Hello, world!" << std::endl;
    return 0;
}

Using the Clang compiler on a MacBook Pro with a 2.6 GHz Intel Core i7 processor, this code takes about 0.5 seconds to compile. In comparison, compiling the equivalent Rust code:

fn main() {
    println!("Hello, world!");
}

Using the Rust compiler takes about 0.8 seconds. While C++ is faster in this example, Rust is improving its compilation times and is expected to become more competitive in the future.

Execution Time:

When it comes to execution time, C++ and Rust are both high-performance languages that can be used to write fast, low-level code. However, the specific performance characteristics of each language can vary depending on the task at hand.

For example, consider the following C++ code that calculates the sum of all integers from 1 to 1 billion:

#include <iostream>

int main() {
    long long sum = 0;
    for (int i = 1; i <= 1000000000; i++) {
        sum += i;
    }
    std::cout << sum << std::endl;
    return 0;
}

Using the Clang compiler on a MacBook Pro with a 2.6 GHz Intel Core i7 processor, this code takes about 5 seconds to execute. In comparison, the equivalent Rust code:

fn main() {
    let mut sum = 0;
    for i in 1..=1000000000 {
        sum += i;
    }
    println!("{}", sum);
}

Using the Rust compiler takes about 6 seconds to execute on the same machine. In this case, C++ is slightly faster than Rust, but the difference is not significant.

Memory Usage:

Another important factor to consider when comparing performance is memory usage. C++ and Rust both provide low-level control over memory, which can be beneficial for performance. However, this also means that the programmer is responsible for managing memory and avoiding memory leaks.

For example, consider the following C++ code that creates a large array of integers:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr(100000000);
    std::cout << arr.size() << std::endl;
    return 0;
}

This code creates a vector of 100 million integers, which takes up about 400 MB of memory. In comparison, the equivalent Rust code:

fn main() {
    let arr = vec![0; 100000000];
    println!("{}", arr.len());
}

Using the Rust compiler takes up about 400 MB of memory. In this case, C++ and Rust have similar memory usage.

Conclusion

Both C++ and Rust offer a balance between performance and safety, but Rust’s ownership and borrowing system gives it an edge in terms of safety. Rust’s memory safety features make it less prone to common programming errors like null pointer dereferencing, data races, and memory leaks.

In terms of performance, both C++ and Rust are high-performance languages, but Rust’s memory safety features and zero-cost abstractions give it an advantage over C++. Rust’s efficient concurrency also makes it well-suited for high-performance and parallel computing.

Ultimately, the choice between C++ and Rust depends on the specific needs of your project. If you need low-level memory management and direct hardware access, C++ may be the better choice. If you prioritize safety and memory efficiency, Rust may be the way to go.

Parsing a Simple XML Document using C++

TinyXml is an excellent choice for applications that need to do just a bit of XML processing. Its source distribution is small, it’s easy to build and integrate with projects, and it has a very simple interface. It also has a very permissive license. Its main limitations are that it doesn’t understand XML Namespaces, can’t validate against a DTD or schema, and can’t parse XML documents containing an internal DTD. If you need to use any of these features, or any of the XML-related technologies such as XPath or XSLT, you should use the other libraries.
The TinyXml parser produces a representation of an XML document as a tree whose nodes represent the elements, text, comments and other components of an XML document. The root of the tree represents the XML document itself. This type of representation
of a hierarchical document as a tree is known as a Document Object Model (DOM). The TinyXml DOM is similar to the one designed by the World Wide Web Consortium (W3C), although it does not conform to the W3C specification.
In keeping with the minimalist spirit of TinyXml, the TinyXml DOM is simpler than the W3C DOM, but also less powerful. The nodes in the tree representing an XML document can be accessed through the interface TiXmlNode, which provides methods to access a node’s parent, to enumerate its child nodes, and to remove child nodes or insert additional child nodes. Each node is actually an instance of a more derived type; for example, the root of the tree is an instance of TiXmlDocument, nodes representing elements are instances TiXmlElement, and nodes representing text are instances of TiXmlText. The type of a TiXmlNode can be determined by calling its Type( ) method; once you knowthe type of a node, you can obtain a representation of the node as a more derived type by calling one of the convenience methods such as toDocument( ), toElement( ) and toText( ).

These derived types contain additional methods appropriate to the type of node they represent. It’s noweasy to understand example code. First, the function textValue( ) extracts the text content from an element that contains only text, such as name, species, or dateOfBirth. It does this by first checking that an element has only one child, and that the child is a text node. It then obtains the child’s text by calling the Value( ) method, which returns the textual content of a text node or comment node, the tag name of an element node, and the filename of a root node.
Next, the function nodeToContact( ) takes a node corresponding to a veterinarian or trainer element and constructs a Contact object from the values of its name and phone attributes, which it retrieves using the Attribute( ) method. Similarly, the function nodeToAnimal( ) takes a node corresponding to an animal element and constructs an Animal object. It does this by iterating over the node’s children using the NextSiblingElement( ) method, extracting the data contained in each element, and setting the corresponding property of the Animal object. The data is extracted using the function textValue( ) for the elements name, species, and dateOfBirth and the function nodeToContact( ) for the elements veterinarian and trainer.

In the main function, I first construct a TiXmlDocument object corresponding to the file animals.xml and parse it using the LoadFile( ) method. I then obtain a TiXmlElement corresponding to the document root by calling the RootElement( ) method. Next, I iterate over the children of the root element, constructing an Animal object from each animal element using the function nodeToAnimal( ). Finally, I iterate over the collection of Animal objects, writing them to standard output. One feature of TinyXml that is not illustrated in code expamle is the SaveFile( ) method of TiXmlDocument, which writes the document represented by a TiXmlDocument
to a file. This allows you to parse an XML document, modify it using the DOM interface, and save the modified document. You can even create a TiXmlDocument from scratch and save it to disk:
// Create a document hello.xml, consisting
// of a single “hello” element
TiXmlDocument doc;
TiXmlElement root(“hello”);
doc.InsertEndChild(root);
doc.SaveFile(“hello.xml”);

Use the TinyXml library. First, define an object of type TiXmlDocument and call its LoadFile( ) method, passing the pathname of your XML document as its argument. If LoadFile( ) returns true, your document has been successfully parsed. If parsing was successful, call the RootElement( ) method to obtain a pointer to an object of type TiXmlElement representing the document root. This object has a hierarchical structure that reflects the structure of your XML document; by traversing this structure, you can extract information about the document and use this information to create a collection of C++ objects.
For example, suppose you have an XML document animals.xml representing a collection of circus animals, as shown in first sample code. The document root is named animalList and has a number of child animal elements each representing an animal owned by the Feldman Family Circus. Suppose you also have a C++ class named Animal, and you want to construct a std::vector of Animals corresponding to the animals listed in the document.

<?xml version="1.0" encoding="UTF-8"?>
<!-- Feldman Family Circus Animals -->
<animalList>
<animal>
<name>Herby</name>
<species>elephant</species>
<dateOfBirth>1992-04-23
<veterinarian name="Dr. Hal Brown" phone="(801)595-9627"/>
<trainer name="Bob Fisk" phone="(801)881-2260"/>
</animal>
<animal>
<name>Sheldon</name>
<species>parrot</species>
<dateOfBirth>1998-09-30</dateOfBirth>
<veterinarian name="Dr. Kevin Wilson" phone="(801)466-6498"/>
<trainer name="Eli Wendel" phone="(801)929-2506"/>
</animal>
<animal>
<name>Dippy</name>
<species>penguin</species>
<dateOfBirth>2001-06-08</dateOfBirth>
<veterinarian name="Dr. Barbara Swayne" phone="(801)459-7746"/>
<trainer name="Ben Waxman" phone="(801)882-3549"/>
</animal>
<!--<span class="hiddenSpellError" pre=""-->animalList>

 

Code sample shows how the definition of the class Animal might look. Animal has five data members corresponding to an animal’s name, species, date of birth, veterinarian, and trainer. An animal’s name and species are represented as std::strings,
its date of birth is represented as a boost::gregorian::date from Boost.Date_Time, and its veterinarian and trainer are represented as instances of the class Contact, also defined in both code examples shows how to use TinyXml to parse the document animals.xml, traverse the parsed document, and populate a std::vector of Animals using data extracted from the document.

The header animal.hpp:

#ifndef ANIMALS_HPP_INCLUDED
#define ANIMALS_HPP_INCLUDED
#include <ostream>
#include <string>
#include <stdexcept> // runtime_error
#include gregorian/gregorian.hpp>
#include <boost/regex.hpp>
// Represents a veterinarian or trainer
class Contact

{
public:

Contact( ) { }
Contact(const std::string& name, const std::string& phone)
: name_(name)
{
setPhone(phone);
}
std::string name( ) const { return name_; }
std::string phone( ) const { return phone_; }
void setName(const std::string& name) { name_ = name; }
void setPhone(const std::string& phone)
{
using namespace std;
using namespace boost;
// Use Boost.Regex to verify that phone
// has the form (ddd)ddd-dddd
static regex pattern("\\([0-9]{3}\\)[0-9]{3}-[0-9]{4}");
if (!regex_match(phone, pattern)) {
throw runtime_error(string("bad phone number:") + phone);
}
phone_ = phone;
}
private:
std::string name_;
std::string phone_;
};

// (for completeness, you should also define operator!=)
bool operator==(const Contact& lhs, const Contact& rhs)
{
return lhs.name() == rhs.name() && lhs.phone() == rhs.phone();
}
// Writes a Contact to an ostream
std::ostream& operator<<(std::ostream& out, const Contact& contact)
{
out << contact.name( ) << " " << contact.phone( );
return out;
}
// Represents an animal
class Animal

 {
public:
// Default constructs an Animal; this is
// the constructor you'll use most
Animal( ) { }
// Constructs an Animal with the given properties;
Animal( const std::string& name,
const std::string& species,
const std::string& dob,
const Contact& vet,
const Contact& trainer )
: name_(name),
species_(species),
vet_(vet),
trainer_(trainer)
{
setDateOfBirth(dob);
}
// Getters
std::string name( ) const { return name_; }
std::string species( ) const { return species_; }
boost::gregorian::date dateOfBirth( ) const { return dob_; }
Contact veterinarian( ) const { return vet_; }
Contact trainer( ) const { return trainer_; }
// Setters
void setName(const std::string& name) { name_ = name; }
void setSpecies(const std::string& species) { species_ = species; }
void setDateOfBirth(const std::string& dob)
{
dob_ = boost::gregorian::from_string(dob);
}
void setVeterinarian(const Contact& vet) { vet_ = vet; }
void setTrainer(const Contact& trainer) { trainer_ = trainer; }
private:
std::string name_;
std::string species_;
boost::gregorian::date dob_;
Contact vet_;
Contact trainer_;
};

// (for completeness, you should also define operator!=)
bool operator==(const Animal& lhs, const Animal& rhs)
{
return lhs.name() == rhs.name() &&
lhs.species() == rhs.species() &&
lhs.dateOfBirth() == rhs.dateOfBirth() &&
lhs.veterinarian() == rhs.veterinarian() &&
lhs.trainer() == rhs.trainer();
}
// Writes an Animal to an ostream
std::ostream& operator<<(std::ostream& out, const Animal& animal)
{
out << "Animal {\n"
<< " name=" << animal.name( ) << ";\n"
<< " species=" << animal.species( ) << ";\n"
<< " date-of-birth=" << animal.dateOfBirth( ) << ";\n"

<< " veterinarian=" << animal.veterinarian( ) << ";\n"
<< " trainer=" << animal.trainer( ) << ";\n"
<< "}";
return out;
}
#endif // #ifndef ANIMALS_HPP_INCLUDED

 

 

Parsing animals.xml with TinyXml:

#include <exception>
#include  // cout
#include <stdexcept> // runtime_error
#include <cstdlib> // EXIT_FAILURE
#include  // strcmp
#include <vector>
#include <tinyxml.h>
#include "animal.hpp"
using namespace std;
// Extracts the content of an XML element that contains only text
const char* textValue(TiXmlElement* e)
{
TiXmlNode* first = e->FirstChild( );
if ( first != 0 &&
first == e->LastChild( ) &&
first->Type( ) == TiXmlNode::TEXT )
{
// the element e has a single child, of type TEXT;
// return the child's
return first->Value( );
} else {
throw runtime_error(string("bad ") + e->Value( ) + " element");
}
}
// Constructs a Contact from a "veterinarian" or "trainer" element
Contact nodeToContact(TiXmlElement* contact)
{
using namespace std;
const char *name, *phone;
if ( contact->FirstChild( ) == 0 &&
(name = contact->Attribute("name")) &&
(phone = contact->Attribute("phone")) )
{
// The element contact is childless and has "name"
// and "phone" attributes; use these values to
// construct a Contact
return Contact(name, phone);
} else {
throw runtime_error(string("bad ") + contact->Value( ) + " element");

}
}
// Constructs an Animal from an "animal" element
Animal nodeToAnimal(TiXmlElement* animal)
{
using namespace std;
// Verify that animal corresponds to an "animal" element
if (strcmp(animal->Value( ), "animal") != 0) {
throw runtime_error(string("bad animal: ") + animal ->Value( ));
}
Animal result; // Return value
TiXmlElement* element = animal->FirstChildElement( );
// Read name
if (element && strcmp(element->Value( ), "name") == 0) {
// The first child element of animal is a "name"
// element; use its text value to set the name of result
result.setName(textValue(element));
} else {
throw runtime_error("no name attribute");
}
// Read species
element = element->NextSiblingElement( );
if (element && strcmp(element->Value( ), "species") == 0) {
// The second child element of animal is a "species"
// element; use its text value to set the species of result
result.setSpecies(textValue(element));
} else {
throw runtime_error("no species attribute");
}
// Read date of birth
element = element->NextSiblingElement( );
if (element && strcmp(element->Value( ), "dateOfBirth") == 0) {
// The third child element of animal is a "dateOfBirth"
// element; use its text value to set the date of birth
// of result
result.setDateOfBirth(textValue(element));
} else {
throw runtime_error("no dateOfBirth attribute");
}
// Read veterinarian
element = element->NextSiblingElement( );
if (strcmp(element->Value( ), "veterinarian") == 0) {
// The fourth child element of animal is a "veterinarian"
// element; use it to construct a Contact object and
// set result's veterinarian

result.setVeterinarian(nodeToContact(element));
} else {
throw runtime_error("no veterinarian attribute");
}
// Read trainer
element = element->NextSiblingElement( );
if (strcmp(element->Value( ), "trainer") == 0) {
// The fifth child element of animal is a "trainer"
// element; use it to construct a Contact object and
// set result's trainer
result.setTrainer(nodeToContact(element));
} else {
throw runtime_error("no trainer attribute");
}
// Check that there are no more children
element = element->NextSiblingElement( );
if (element != 0) {
throw runtime_error(
string("unexpected element:") +
element->Value( )
);
}
return result;
}

Main Program:

int main( )
{
using namespace std;
try {
vector animalList;
// Parse "animals.xml"
TiXmlDocument doc("animals.xml");
if (!doc.LoadFile( ))
throw runtime_error("bad parse");
// Verify that root is an animal-list
TiXmlElement* root = doc.RootElement( );
if (strcmp(root->Value( ), "animalList") != 0) {
throw runtime_error(string("bad root: ") + root->Value( ));
}
// Traverse children of root, populating the list
// of animals
for ( TiXmlElement* animal = root->FirstChildElement( );
animal;
animal = animal->NextSiblingElement( ) )

{
animalList.push_back(nodeToAnimal(animal));
}
// Print the animals' names
for ( vector::size_type i = 0,
n = animalList.size( );
i < n;
++i )
{
cout << animalList[i] << "\n";
}
} catch (const exception& e) {
cout << e.what( ) << "\n";
return EXIT_FAILURE;
}
}

Related articles

• XML Processing with XmlPullParser (androidstudies.wordpress.com)
• Parsing XML in Groovy using XmlSlurper (java.dzone.com)
• Validating XML documents with XSD correctly (stackoverflow.com)
• xmlutils 0.91 (pypi.python.org)
• Converting XElement to XmlElement for XSLT transformation ASP.NET C# (stackoverflow.com)
• Oxygen XML Editor 14.0 (x86/x64) (fagivece.wordpress.com)

 

“The Best Programming Advice I Ever Got” with Andrei Alexandrescu | | InformIT

“The Best Programming Advice I Ever Got” with Andrei Alexandrescu | | InformIT.

learning how to learn is more important than learning anything else….

Creating a Thread using C++ Boost Lib.

Creating a thread is deceptively simple. All you have to do is create a thread object on the stack or the heap, and pass it a functor that tells it where it can begin working. For this discussion, a “thread” is actually two things. First, it’s an object of the class thread, which is a C++ object in the conventional sense. When I am referring to this object, I will say “thread object.” Then there is the thread of execution, which is an operating system thread that is represented by the thread object. When I say “thread” , I mean the operating system thread. Let’s get right to the code in the example. The thread constructor takes a functor (or function pointer) that takes no arguments and returns void. Look at this line from below code,

boost::thread myThread(threadFun);
This creates the myThread object on the stack, which represents a new operating system thread that begins executing threadFun. At that point, the code in threadFun and the code in main are, at least in theory, running in parallel. They may not exactly be running in parallel, of course, because your machine may have only one processor, in which case this is impossible (recent processor architectures have made this not quite true, but I’ll ignore dual-core or above processors and the like for now). If you have only one processor, then the operating system will give each thread you create a slice of time in the run state before it is suspended. Because these slices of time can be of varying sizes, you can never be guaranteed which thread will reach a particular point first.
This is the aspect of multithreaded programming that makes it difficult: multithreaded program state is nondeterministic. The same multithreaded program, run multiple times, with the same inputs, can produce different output. Coordinating resources used by multiple threads is the subject of my next post.
After creating myThread, the main thread continues, at least for a moment, until it reaches the next line:
boost::thread::yield( );
This puts the current thread (in this case the main thread) in a sleep state, which means the operating system will switch to another thread or another process using some operating-system-specific policy. yield is a way of telling the operating system that the current thread wants to give up the rest of its slice of time. Meanwhile, the newthread is executing threadFun. When threadFun is done, the child thread goes away. Note that the thread object doesn’t go away, because it’s still a C++ object that’s in scope. This is an important distinction.
The thread object is something that exists on the heap or the stack, and works just like any other C++ object. When the calling code exits scope, any stack thread objects are destroyed and, alternatively, when the caller calls delete on a thread*, the corresponding heap thread object disappears. But thread objects are just proxies for the actual operating system threads, and when they are destroyed the operating system threads aren’t guaranteed to go away. They merely become detached, meaning that they cannot later be rejoined. This is not a bad thing. Threads use resources, and in any (well-designed) multithreaded application, access to such resources (objects, sockets, files, rawmemory, and so on) is controlled with mutexes, which are objects used for serializing access to something among multiple threads.

If an operating system thread is killed, it will not release its locks or deallocate its resources, similarly to how killing a process does not give it a chance to flush its buffers or release operating system resources properly. Simply ending a thread when you think it ought to be finished is like pulling a ladder out from under a painter when his time is up.
Thus, we have the join member function. As in below code, you can call join to wait for a child thread to finish. join is a polite way of telling the thread that you are going to wait until it’s done working:
myThread.join( );
The thread that calls join goes into a wait state until the thread represented by myThread is finished. If it never finishes, join never returns. join is the best way to wait for a child thread to finish. You may notice that if you put something meaningful in threadFun, but comment out the use of join, the thread doesn’t finish its work. Try this out by putting a loop or some long operation in threadFun. This is because when the operating system destroys a process, all of its child threads go with it, whether they’re done or not. Without the call to join, main doesn’t wait for its child thread: it exits, and the operating system thread is destroyed.

If you need to create several threads, consider grouping them with a thread_group object. A thread_group object can manage threads in a couple of ways. First, you can call add_thread with a pointer to a thread object, and that object will be added to the group. Here’s a sample:
boost::thread_group grp;
boost::thread* p = new boost::thread(threadFun);
grp.add_thread(p);
// do something…
grp.remove_thread(p)

When grp’s destructor is called, it will delete each of the thread pointers that were added with add_thread. For this reason, you can only add pointers to heap thread objects to a thread_group. Remove a thread by calling remove_thread and passing in the thread object’s address (remove_thread finds the corresponding thread object in the group by comparing the pointer values, not by comparing the objects they point to). remove_thread will remove the pointer to that thread from the group, but you are still responsible for delete-ing it. You can also add a thread to a group without having to create it yourself by calling create_thread, which (like a thread object) takes a functor as an argument and begins executing it in a new operating system thread. For example, to spawn two threads in a group, do this:
boost::thread_group grp;
grp.create_thread(threadFun);
grp.create_thread(threadFun); // Now there are two threads in grp
grp.join_all( ); // Wait for all threads to finish
Whether you add threads to the group with create_thread or add_thread, you can call join_all to wait for all of the threads in the group to complete. Calling join_all is the same as calling join on each of the threads in the group: when all of the threads in the group have completed their work join_all returns.
Creating a thread object allows a separate thread of execution to begin. Doing it with the Boost Threads library is deceptively easy, though, so design carefully.

#include <iostream>
#include <boost/thread/thread.hpp>
#include <boost/thread/xtime.hpp>
struct MyThreadFunc

{
void operator( )( )

{
// Do something long-running...
}
} threadFun;
int main( )

{
boost::thread myThread(threadFun); // Create a thread that starts
// running threadFun

boost::thread::yield( ); // Give up the main thread's timeslice
// so the child thread can get some work
// done.
// Go do some other work...
myThread.join( ); // The current (i.e., main) thread will wait
// for myThread to finish before it returns

}

Related articles

• SINGLETON in Multithreaded Environment (aishwaryavaishno.wordpress.com)
• Synchronising Multithreaded Integration Tests revisited (java.dzone.com)
• Working With Threads (androidstudies.wordpress.com)
• Adventures in Parallel Universe Part 1 (lastsector.wordpress.com)

 

Some advice for college freshmen

I don’t know the author but this seems a very good advise for fresh Graduates.

Strong skill of one or more good languages like C++, Java and C#:

Must have strong skills with control structures. Don’t mess up if you’re asked to print out triangle or other shaped piles of ‘x’s with loops.
Must have strong skills with recursion. You must know how to transform a looped task into a recursive one and vice versa, for example: multiplication using addition recursively.
If your language is C/C++, you must know how to play with pointers and references.
Understand pass by value and reference.
Clearly understand scopes and memory allocation, de-allocation. Know when an object is destroyed and when to destroy.
Know the usage of all operators including bit-wise ones.
In-depth knowledge of OOP:
Only being able to write classes and doing encapsulation and inheritance is not what you should call good OOP.
Clearly understand how function overloading, overriding, polymorphism works.
Clearly understand how constructor/destructor (if any) works with inheritance.
Clearly know the difference and use of Interfaces and Abstract classes.
Know how to overload operators. Why and how copy constructor is defined/used.
Know common data structures:
At least know the common data structures like stack, queue, linked list, doubly linked list (know circular version of all of them) and trees.
Be a skilled implementer of any of those, have clear concept of how push, pop, add, delete, peek etc method works on those data structures.
Know most common algorithms well:
You don’t need to memorize pseudo codes line by line but you need to have clear concept of most common algorithms of sorting(bubble, quick, merge, heap, bucket, etc), searching (including DFS, BFS), etc.
As a fresher you must know their time and space complexities, pitfalls and improvements (if any).
General computing concepts:
Know processes and threads, how are they related to each other, how to program them, etc.
Understand TCP/IP: Don’t think it’s only the network administrator’s task to understand TCP/IP. All programmers ever doing any network or web programming should have clear TCP/IP concepts and understanding.
Be skilled in debugging in IDEs:
Be skilled in any of Visual Studio/Visual Studio.Net, Eclipse, Netbeans, KDevelop, etc.
Know how to debug your code.
Have basic knowledge of Software Engineering and SDLC.

General Advise:
Start with C++ or Java, avoid starting with scripting languages:
If you’re learning programming for the first time, avoid starting with scripting or loosely typed languages like: PHP, ASP, Perl, etc or Visual Basic. It may destroy your understanding of program execution, data types, memory allocation, etc.
Start with C++ or Java. If you want to me to be specific, start with C++, you’ll love it for the rest of your life.. 🙂 It’ll be easier for you to learn (almost) any other language (like: C#, PHP, ASP, etc).
If you ask, do you need to know C to start with C++? Or should you learn C first and then C++? C definitely helps a lot for learning C++ but it’s not mandatory to start with C.
If you want to be a good programmer, keep on coding at least 20 hours a week for the next 4 years :). Never stop learning new technologies that are coming out everyday. Know some of the many languages/technologies but be master of one. Know at least one language very well.

Related articles

• 10 Reasons to Learn Java Programming Language and Why Java is Best (javarevisited.blogspot.com)
• Busting KDevelop myths (scummos.blogspot.com)
• How to represent OOP concepts in algorithms in a standard way? (cs.stackexchange.com)
• 7 Habits Of Successful College Freshmen (howtolearn.com)

Sorting Localized Strings

Sorting becomes more complicated when you’re working in different local language strings, and the standard library solves this problem. The facet collate provides a member function compare that works like strcmp: it returns -1 if the first string is less than the second, 0 if they are equal, and 1 if the first string is greater than the second. Unlike strcmp, collate::compare uses the character semantics of the target locale.
Below code presents the function localeLessThan, which returns true if the first argument is less than the second according to the global locale. The most important part of the function is the call to compare:
col.compare(pb1, // Pointer to the first char
pb1 + s1.size( ), // Pointer to one past the last char
pb2,
pb2 + s2.size( ))
Depending on the execution character set of your implementation, below code may return the results I showed earlier or not. But if you want to ensure string comparison works in a locale-specific manner, you should use collate::compare. Of course, the standard does not require an implementation to support any locales other than “C,” so be sure to test for all the locales you support.

The locale class has built-in support for comparing characters in a given locale by overriding operator. You can use an instance of the locale class as your comparison functor when you call any standard function that takes a functor for comparison.

#include <iostream>
#include <locale>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool localeLessThan (const string& s1, const string& s2)
{
const collate<char>& col = use_facet<collate<char> >(locale( )); // Use the global locale
const char* pb1 = s1.data( );
const char* pb2 = s2.data( );
return (col.compare(pb1, pb1 + s1.size( ), pb2, pb2 + s2.size( )) < 0);
}

int main( )
{
// Create two strings, one with a German character
string s1 = "diät";
string s2 = "dich";
vector<string> v;
v.push_back(s1);
v.push_back(s2);

// Sort without giving a locale, which will sort according to the current global locale's rules.
sort(v.begin( ), v.end( ));
for (vector<string>::const_iterator p = v.begin( ); p != v.end( ); ++p)
cout << *p << endl;

// Set the global locale to German, and then sort
locale::global(locale("german"));
sort(v.begin( ), v.end( ), localeLessThan);

for (vector<string>::const_iterator p = v.begin( );
p != v.end( ); ++p)
cout << *p << endl;
}

The first sort follows ASCII sorting convention, and therefore the output looks like
this:
dich
diät

The second sort uses the proper ordering according to German semantics, and it is just the opposite:
diät
dich

Related articles

• Performing Arithmetic on Bitsets in C++ (alikhuram.wordpress.com)
• Binary Search Tree template Class (BST) (alikhuram.wordpress.com)
• Representing Large Fixed-Width Integers in C++ (alikhuram.wordpress.com)
• Implementing Fixed-Point Numbers in C++ (alikhuram.wordpress.com)
• Template Compare iterator (stackoverflow.com)
• Go 1.1 performance improvements (dave.cheney.net)
• Updates and responses to reader feedback (rachelbythebay.com)
• GotW #3 Solution: Using the Standard Library (or, Temporaries Revisited) (herbsutter.com)

Hardcoding a Unicode String in C++

Hard coding a Unicode string is mostly a matter of deciding how you want to enter the string in your source editor. C++ provides a wide-character type, wchar_t, which can store Unicode strings. The exact implementation of wchar_t is implementation defined, but it is often UTF-32. The class wstring, defined in , is a sequence of wchar_ts, just like the string class is a sequence of chars. (Strictly speaking, of course, wstring is a typedef for basic_string<wchar_t>).
The easiest way to enter Unicode characters is to use the L prefix to a string literal, as stated in below code:
wstring ws1 = L”Infinity: \u2210″; // Use the code itself
wstring ws2 = L”Euro: “; // Or just type it in
Now, you can write these wide-character strings to a wide-character stream, like this:
wcout << ws1 << endl; // wcout is the wide char version of cout
This goes for files, too:
wofstream out(“tmp\\unicode.txt”);
out << ws2 << endl;
The trickiest part of dealing with different character encodings isn’t embedding the right characters in your source files, it’s knowing what kind of character data you are getting back from a database, HTTP request, user input, and so on, and this is beyond the realm of the C++ standard. The C++ standard does not require a particular encoding, rather that the character encoding used by your operating system to store source files can be anything, as long as it supports at least the 96 characters used by the C++ language. For characters that are not part of this character set, called the basic source character set, the standard indicates that they must be available by using the \uXXXX or \UXXXXXXXX escape sequences, where each X is a hexadecimal digit.

Do this by hard coding the string with a prefix of L and typing the character into your source editor as you would any other string, or use the hexadecimal number that represents the Unicode character you’re after. Below code shows how to do it both ways.

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main( )

{
// Create some strings with Unicode characters
wstring ws1 = L"Infinity: \u221E";
wstring ws2 = L"Euro: _";
wchar_t w[] = L"Infinity: \u221E";
wofstream out("tmp\\unicode.txt");
out << ws2 << endl;
wcout << ws2 << endl;

}

Related articles

• Unicode Twitter Usernames (higg.im)
• Unicode text processing (3.3) (kenmxu.wordpress.com)
• Convert number from Unicode to natural integer representation C#.NET (stackoverflow.com)

 

Implementing Fixed-Point Numbers in C++

A fixed-point number, like a floating-point number, is an approximate representation of a real number. A floating-point number is stored as a mantissa (m), and an exponent (e), to form the equation m * be, where b is some constant. A fixed-point number is almost the same but the exponent is also a constant. This constant is passed to the basic_fixed_real in below class template as a template parameter.
By representing e as a constant, it allows fixed-point numbers to be represented internally as integers and for the arithmetic operations on them to be performed using integer arithmetic. This can often improve the speed of basic arithmetic operations
especially addition and subtraction. Fixed-point representations are less flexible than floating-point numbers, as they can only represent a narrow range of values. The fixed_real type in below function has a range that can only represent values from –2,097,151 to +2,097,151 with a precision of 1/1,024.
Implementing addition and subtraction of fixed-point numbers is straightforward enough: I simply add or subtract the underlying representation. To perform division and multiplication, I need an extra step of shifting the mantissa left or right to adjust for the binary point.

Below class template provides the implementation of a fixed-point real number, where the number of places to the right of the binary point is a template parameter. For instance basic_fixed_real<10> has 10 binary digits to the right of the binary point, allowing it to represent numbers up to a precision of 1/1,024.

#include <iostream>
using namespace std;

template<int E>
struct BasicFixedReal
{
typedef BasicFixedReal self;
static const int factor = 1 << (E - 1);
BasicFixedReal( ) : m(0) { }
BasicFixedReal(double d) : m(static_cast(d * factor)) { }
self& operator+=(const self& x) { m += x.m; return *this; }
self& operator-=(const self& x) { m -= x.m; return *this; }
self& operator*=(const self& x) { m *= x.m; m >>= E; return *this; }
self& operator/=(const self& x) { m /= x.m; m *= factor; return *this; }
self& operator*=(int x) { m *= x; return *this; }
self& operator/=(int x) { m /= x; return *this; }
self operator-( ) { return self(-m); }
double toDouble( ) const { return double(m) / factor; }
// friend functions
friend self operator+(self x, const self& y) { return x += y; }
friend self operator-(self x, const self& y) { return x -= y; }
friend self operator*(self x, const self& y) { return x *= y; }
friend self operator/(self x, const self& y) { return x /= y; }
// comparison operators
friend bool operator==(const self& x, const self& y) { return x.m == y.m; }
friend bool operator!=(const self& x, const self& y) { return x.m != y.m; }
friend bool operator>(const self& x, const self& y) { return x.m > y.m; }
friend bool operator<(const self& x, const self& y) { return x.m < y.m; }
friend bool operator>=(const self& x, const self& y) { return x.m >= y.m; }
friend bool operator<=(const self& x, const self& y) { return x.m <= y.m; }
private:
int m;
};
typedef BasicFixedReal<10> FixedReal;
int main( ) {
FixedReal x(0);
for (int i=0; i < 100; ++i) {

x += FixedReal(0.0625);
}
cout << x.toDouble( ) << endl;

}

The program outputs:
6.25

Related articles

• Representing Large Fixed-Width Integers in C++ (alikhuram.wordpress.com)
• Performing Arithmetic on Bitsets in C++ (alikhuram.wordpress.com)
• Binary Search Tree template Class (BST) (alikhuram.wordpress.com)

 

Performing Arithmetic on Bitsets in C++

The bitset class template comes with basic operations for manipulating sets of bits but doesn’t provide any arithmetic or comparison operations. This is because the library can’t safely assume what kind of numerical type a programmer might expect an arbitrary set of bits to represent.The functions below treat a bitset as a representation of an unsigned integer type, and provide you with functions for adding, subtracting, multiplying, dividing, and comparing them. These functions can provide a basis for writing custom-sized integer types. I did not use the most efficient algorithms I could for below function. Instead I chose the simplest possible algorithms because they are more easily understood. A much more efficient implementation would use similar algorithms, but would operate on words rather than single bits.

The functions below provide functions that allow arithmetic and comparison of bitset class template from the header as if it represents an unsigned integer.

#include <stdexcept>
#include <bitset>
bool fullAdder(bool b1, bool b2, bool& carry)

{
bool sum = (b1 ^ b2) ^ carry;
carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
return sum;
}
bool fullSubtractor(bool b1, bool b2, bool& borrow)

{
bool diff;
if (borrow)

{
diff = !(b1 ^ b2);
borrow = !b1 || (b1 && b2);
}
else

{
diff = b1 ^ b2;
borrow = !b1 && b2;
}
return diff;
}
template<unsigned int N>
bool bitsetLtEq(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--)

{
if (x[i] && !y[i]) return false;
if (!x[i] && y[i]) return true;
}
return true;
}

template<unsigned int N>
bool bitsetLt(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--) {
if (x[i] && !y[i]) return false;
if (!x[i] && y[i]) return true;
}
return false;
}
template<unsigned int N>
bool bitsetGtEq(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--) {
if (x[i] && !y[i]) return true;
if (!x[i] && y[i]) return false;
}
return true;
}
template<unsigned int N>
bool bitsetGt(const std::bitset& x, const std::bitset& y)
{
for (int i=N-1; i >= 0; i--)

{
if (x[i] && !y[i]) return true;
if (!x[i] && y[i]) return false;
}
return false;
}
template<unsigned int N>
void bitsetAdd(std::bitset& x, const std::bitset& y)
{
bool carry = false;
for (int i = 0; i < N; i++)

{
x[i] = fullAdder(x[i], y[i], carry);
}
}
template<unsigned int N>
void bitsetSubtract(std::bitset& x, const std::bitset& y)

{
bool borrow = false;
for (int i = 0; i < N; i++)

{
if (borrow)

{
if (x[i])

{
x[i] = y[i];
borrow = y[i];
}
else

{
x[i] = !y[i];
borrow = true;
}

}
else

{
if (x[i])

{
x[i] = !y[i];
borrow = false;
}
else

{
x[i] = y[i];
borrow = y[i];
}
}
}
}
template<unsigned int N>
void bitsetMultiply(std::bitset& x, const std::bitset& y)
{
std::bitset tmp = x;
x.reset( );
// we want to minimize the number of times we shift and add
if (tmp.count( ) < y.count( ))

{
for (int i=0; i < N; i++)
if (tmp[i]) bitsetAdd(x, y << i);
}
else

{
for (int i=0; i < N; i++)
if (y[i]) bitsetAdd(x, tmp << i);
}
}
template<unsigned int N>
void bitsetDivide(std::bitset x, std::bitset y,
std::bitset<N>& q, std::bitset<N>& r)
{
if (y.none( ))

{
throw std::domain_error("division by zero undefined");
}
q.reset( );
r.reset( );
if (x.none( ))

{
return;
}
if (x == y)

{
q[0] = 1;
return;
}
r = x;
if (bitsetLt(x, y))

{
return;
}

// count significant digits in divisor and dividend
unsigned int sig_x;
for (int i=N-1; i>=0; i--)

{
sig_x = i;
if (x[i]) break;
}
unsigned int sig_y;
for (int i=N-1; i>=0; i--)

{
sig_y = i;
if (y[i]) break;
}
// align the divisor with the dividend
unsigned int n = (sig_x - sig_y);
y <<= n;
// make sure the loop executes the right number of times
n += 1;
// long division algorithm, shift, and subtract
while (n--)
{
// shift the quotient to the left
if (bitsetLtEq(y, r))
{
// add a new digit to quotient
q[n] = true;
bitsetSubtract(r, y);
}
// shift the divisor to the right
y >>= 1;
}
}

Using the bitset_arithmetic.hpp functions:

#include "bitset_arithmetic.hpp"
#include <bitset>
#include <iostream>
#include <string>
using namespace std;
int main( )

{
bitset<10> bits1(string("100010001"));
bitset<10> bits2(string("000000011"));
bitsetAdd(bits1, bits2);
cout << bits1.to_string<char, char_traits<char="">, allocator >( ) << endl;
}

The program produces the following output:
0100010100

Related articles

• Binary Search Tree template Class (BST) (alikhuram.wordpress.com)
• More algorithms (aandrew99.wordpress.com)
• How I can improve my algorithmic coding skills? (thejatinbatra.wordpress.com)

 

Computing the Fast Fourier Transform Algorithm in C++

The Fourier transform is an important equation for spectral analysis, and is required frequently in engineering and scientific applications. The FFT is an algorithm for computing a DFT that operates in N log2(N) complexity versus the expected N2 complexity of a naive implementation of a DFT. The FFT achieves such an impressive speed-up by removing redundant computations.

Finding a good FFT implementation written in idiomatic C++ (i.e., C++ that isn’t mechanically ported from old Fortran or C algorithms) and that isn’t severely restricted by a license is very hard. The code in Example below is based on public domain code that can be found on the digital signal processing newswgoup on usenet (comp.dsp). A big advantage of an idiomatic C++ solution over the more common C-style FFT implementations is that the standard library provides the complex template that significantly reduces the amount of code needed. The fft( ) function in below, was written to be as simple as possible rather than focusing on efficiency.

Solution:
The code below provides a basic implementation of the FFT.

#include <iostream>
#include <complex>
#include <cmath>
#include <iterator>
using namespace std;

unsigned int bitReverse(unsigned int x, int log2n)

{
int n = 0;
int mask = 0x1;
for (int i=0; i < log2n; i++)

{
n <<= 1;
n |= (x & 1);
x >>= 1;
}
return n;
}
const double PI = 3.1415926536;
template<class Iter_T>
void fft(Iter_T a, Iter_T b, int log2n)
{
typedef typename iterator_traits<iter_t>::value_type complex;
const complex J(0, 1);
int n = 1 << log2n;
for (unsigned int i=0; i < n; ++i) {
b[bitReverse(i, log2n)] = a[i];
}

for (int s = 1; s <= log2n; ++s)

{
int m = 1 << s;
int m2 = m >> 1;
complex w(1, 0);
complex wm = exp(-J * (PI / m2));
for (int j=0; j < m2; ++j)

{
for (int k=j; k < n; k += m)

{
complex t = w * b[k + m2];
complex u = b[k];
b[k] = u + t;
b[k + m2] = u - t;
}
w *= wm;
}
}
}
int main( )

{
typedef complex cx;
cx a[] = { cx(0,0), cx(1,1), cx(3,3), cx(4,4),
cx(4, 4), cx(3, 3), cx(1,1), cx(0,0) };
cx b[8];
fft(a, b, 3);
for (int i=0; i<8; ++i)
cout << b[i] << "\n";

}

The program  produces the following output:
(16,16)
(-4.82843,-11.6569)
(0,0)
(-0.343146,0.828427)
(0,0)
(0.828427,-0.343146)
(0,0)
(-11.6569,-4.82843)

Related articles

• FFT-less $O(n\log n)$ algorithm for pairwise sums (cs.stackexchange.com)
• Image interpolation with the fast Fourier transform (eliteraspberries.com)
• Retrotechtacular: The Fourier Series (hackaday.com)
• Speeding up MR Image Reconstruction with GeneRalized Autocalibrating Partially Acquisitions (GRAPPA) (elekslabs.com)