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)

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)

 

Binary Search Tree template Class (BST)

Let’s see the code of the binary search tree (BST). This is a continuation of another article where I have explained the BST in detail. Please review that article as well. (link is below) We put the interface in the .h file. We also have the state variable in addition to the public and private methods of the class in it. In the public methods, the user of the class calls with their objects.

Here is the code of the program. BinarySearchTree.h file.

/* This file contains the declaration of binary node and the binary search tree */

#ifndef BINARY_SEARCH_TREE_H_
#define BINARY_SEARCH_TREE_H_

#include <iostream.h>     // For NULL

// Binary node and forward declaration
template <class EType> class BinarySearchTree;

template <class EType> class BinaryNode
{
EType element; BinaryNode *left; BinaryNode *right;
BinaryNode( const EType & theElement, BinaryNode *lt, BinaryNode *rt ) : element( theElement ), left( lt ), right( rt ) { }

friend class BinarySearchTree<EType>;
};

// BinarySearchTree class

CONSTRUCTION:  with  ITEM_NOT_FOUND  object  used  to signal  failed finds

// ******************PUBLIC  OPERATIONS*********************
// void insert( x )     --> Insert x
// void remove( x )     --> Remove x
// EType find( x )   --> Return item that matches x
// EType findMin( )  --> Return smallest item
// EType findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )     --> Remove all items
// void printTree( )     --> Print tree in sorted order

template <class EType> class BinarySearchTree
{
public:
BinarySearchTree( const EType & notFound ); BinarySearchTree( const BinarySearchTree & rhs );
~BinarySearchTree( );

const EType & findMin( ) const;
const EType & findMax( ) const;
const EType & find( const EType & x ) const;
bool isEmpty( ) const;
void printTree( ) const;

void makeEmpty( );
void insert( const EType & x );
void remove( const EType & x );

const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private:
BinaryNode<EType> *root;
const EType ITEM_NOT_FOUND;

const EType & elementAt( BinaryNode<EType> *t ) const;

void insert( const EType & x, BinaryNode<EType> * & t ) const;
void remove( const EType & x, BinaryNode<EType> * & t ) const;
BinaryNode<EType> * findMin( BinaryNode<EType> *t ) const;
BinaryNode<EType> * findMax( BinaryNode<EType> *t ) const;
BinaryNode<EType>  *  find(  const  EType  &  x,  BinaryNode<EType>  *t  ) const;

void makeEmpty( BinaryNode<EType> * & t ) const;
void printTree( BinaryNode<EType> *t ) const; BinaryNode<EType> * clone( BinaryNode<EType> *t ) const;
};
#include "BinarySearchTree.cpp"
#endif

/*BinarySearchTree.cpp  file.*/

/* This file contains the implementation of the binary search tree */

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

/**
* Construct the tree.
*/
template <class EType> BinarySearchTree<EType>::BinarySearchTree(const EType & notFound) : ITEM_NOT_FOUND( notFound), root( NULL )
{
}

/**
* Copy constructor.
*/

template<classEType>BinarySearchTree<EType>::BinarySearchTree(const BinarySearchTree<EType> & rhs )
:root( NULL ), ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
*this = rhs;
}

/**
* Destructor for the tree.
*/
template<classEType>BinarySearchTree<EType>::~BinarySearchTree ()
{
makeEmpty( );
}

/**
* Insert x into the tree; duplicates are ignored.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x )
{
insert( x, root );
}

/**
* Remove x from the tree. Nothing is done if x is not found.
*/
template <class EType> void BinarySearchTree<EType>::remove(  const EType & x )
{
remove( x, root );
}

/**
* Find the smallest item in the tree.
* Return smallest item or ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMin() const
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* Return the largest item of ITEM_NOT_FOUND if empty.
*/
template <class EType> const EType & BinarySearchTree<EType>::findMax() const
{
return elementAt( findMax( root ) );
}

/**
* Find item x in the tree.
* Return the matching item or ITEM_NOT_FOUND if not found.
*/
template <class EType>const EType & BinarySearchTree<EType>::find( const EType & x ) const
{
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty()
{
makeEmpty( root );
}

/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
template <class EType> bool BinarySearchTree<EType>::isEmpty( ) const
{
return root == NULL;
}

/**
* Print the tree contents in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree() const
{
if( isEmpty( ) )
cout << "Empty tree" << endl;
else
printTree( root );
}

/**
* Deep copy.
*/
template <class EType> const BinarySearchTree<EType> & BinarySearchTree<EType>::operator=( const BinarySearchTree<EType> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}

/**
* Internal method to get element field in node t.
* Return the element field or ITEM_NOT_FOUND if t is NULL.
*/
template <class EType> const EType & BinarySearchTree<EType>::elementAt(BinaryNode<EType>*t) const
{
if( t == NULL )
return ITEM_NOT_FOUND;
else
return t->element;
}

/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the tree.

* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::insert( const EType & x, BinaryNode<EType> * & t ) const
{
if( t == NULL )
t = new BinaryNode<EType>( x, NULL, NULL );
else if( x < t->element )
insert( x, t->left ); else if( t->element < x ) insert( x, t->right );
else
;  // Duplicate; do nothing
}

/**
* Internal method to remove from a subtree.
* x is the item to remove.
* t is the node that roots the tree.
* Set the new root.
*/
template <class EType> void BinarySearchTree<EType>::remove(const EType & x, BinaryNode<EType>
* & t ) const
{
if( t == NULL )
return;   // Item not found; do nothing
if( x < t->element )
remove( x, t->left );
else if( t->element < x )
remove( x, t->right );
else if( t->left != NULL && t->right != NULL ) // Two children
{
t->element = findMin( t->right )->element;
remove( t->element, t->right );
}
else
{
BinaryNode<EType> *nodeToDelete = t;
t = ( t->left!= NULL ) ? t->left : t->right;
delete nodeToDelete;
}
}

/**
* Internal method to find the smallest item in a subtree t.
* Return node containing the smallest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMin( BinaryNode<EType>*t) const
{
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}

/**
* Internal method to find the largest item in a subtree t.
* Return node containing the largest item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::findMax( BinaryNode<EType> *t ) const
{
if( t != NULL )
while( t->right != NULL )
{
t = t->right;
}
return t;
}

/**
* Internal method to find an item in a subtree.
* x is item to search for.
* t is the node that roots the tree.
* Return node containing the matched item.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::
find( const EType & x, BinaryNode<EType> *t ) const
{
if( t == NULL )
return NULL;
else if( x < t->element )
return find( x, t->left );
else if( t->element < x )
return find( x, t->right );
else
return t;     // Match
}
/****** NONRECURSIVE VERSION*************************
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::find( const EType & x, BinaryNode<EType> *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return t;     // Match

return NULL;   // No match
}
*****************************************************/

/**
* Internal method to make subtree empty.
*/
template <class EType> void BinarySearchTree<EType>::makeEmpty( BinaryNode<EType> * & t ) const
{
if( t != NULL )
{
makeEmpty( t->left ); makeEmpty( t->right ); delete t;
}
t = NULL;
}

/**
* Internal method to print a subtree rooted at t in sorted order.
*/
template <class EType> void BinarySearchTree<EType>::printTree( BinaryNode<EType> *t ) const
{
if( t != NULL )
{
printTree( t->left );
cout << t->element << endl;
printTree( t->right );
}
}

/**
* Internal method to clone subtree.
*/
template <class EType> BinaryNode<EType> * BinarySearchTree<EType>::clone(  BinaryNode<EType> * t ) const
{
if( t == NULL )
return NULL;
else
return  new  BinaryNode<EType>(  t->element,  clone(  t->left  ),  clone(  t->right ) );
}