<$BlogRSDUrl$>

Thursday, July 13, 2006

STL


INTRO
-----------

Containers
----------
onedimensional array of T §16.3
doublylinked list of T §17.2.2
doubleended queue of T §17.2.3
queue of T §17.3.2
stack of T §17.3.1
associative array of T §17.4.1
set of T §17.4.3
array of booleans §17.5.3

The associative containers map and set can be found in and respectively
The priority_queue is declared in .


General Utilities
-----------------
operators and pairs §17.1.4, §17.4.1.2
function objects §18.4
allocators for containers §19.4.4
Cstyle date and time §s.20.5

The header also contains the auto_ptr template that is primarily used to smooth the
interaction between pointers and exceptions.

Iterators
----------
iterators and iterator support
Iterators provide the mechanism to make standard algorithms generic over the standard containers and similar types (§2.7.2,

Algorithms
----------
general algorithms
bsearch() qsort()

A typical general algorithm can be applied to any sequence (§3.8, §18.3) of any type of elements.
The C standard library functions bsearch() and qsort() apply to builtin arrays with elements of
types without userdefined copy constructors and destructors only (§7.7).

Diagnostics
-----------
exception class §14.10
standard exceptions §14.10
assert macro §24.3.7.2
Cstyle error handling

Strings
-------
string of T Chapter 20
character classification §20.4.2
widecharacter classification §20.4.2
Cstyle string functions §20.4.1
Cstyle widecharacter string functions §20.4
Cstyle string functions

The header declares the strlen(), strcpy(), etc., family of functions. The
declares atof() and atoi() that convert Cstyle strings to numeric values.

Input/Output
---------------

forward declarations of I/O facilities §21.1
standard iostream objects and operations §21.2.1
iostream bases §21.2.1
stream buffers §21.6
input stream template §21.3.1
output stream template §21.2.1
manipulators §21.4.6.2
streams to/from strings §21.5.3
character classification functions §20.4.2
streams to/from files §21.5.1
printf() family of I/O §21.8
printf()­style I/O of wide characters §21.8

Manipulators are objects used to manipulate the state of a stream (e.g., changing the format of
floatingpoint output) by applying them to the stream.

Localization
-------------
represent cultural differences §21.7
represent cultural differences Cstyle

Language Support
-------------------
numeric limits §22.2
Cstyle numeric scalarlimit macros §22.2.1
Cstyle numeric floatingpoint limit macros §22.2.1
dynamic memory management §16.1.3
runtime type identification support §15.4.1
exceptionhandling support §14.10
C library language support §6.2.1
variablelength function argument lists §7.6
Cstyle stack unwinding §s.18.7
program termination §9.4.1.1
system clock §s.18.7
Cstyle signal handling §s.18.7

Numerics
---------
< complex> complex numbers and operations §22.5
< valarray> numeric vectors and operations §22.4
< numeric> generalized numeric operations §22.6
< cmath> standard mathematical functions §22.3
< cstdlib> Cstyle random numbers

For historical reasons, abs(), fabs(), and div() are found in rather than in
with the rest of the mathematical functions (§22.3).

The base() function returns an iterator corresponding to the reverse iter.

The members front() and back() return references to the first and last element, respectively.
They are most useful where these elements are known to exist and in code where these elements are
of particular interest. A vector used as a stack (§16.3.5) is an obvious example. Note that front()
returns a reference to the element to which begin() returns an iterator. I often think of front() as
the first element and begin() as a pointer to the first element. The correspondence between
back() and end() is less simple: back() is the last element and end() points to the lastplusone
element position.

If a type does not have a default constructor, it is not possible to create a vector with elements
of that type without explicitly providing the value of each element. For Example :-

class Num{ / / infinite precision
public:
Num(long) ;
// no default constructor
};

vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok


class Num{ / / infinite precision
public:
Num(long) ;
/ / no default constructor
/ / ...
};
vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok

class Num{ / / infinite precision
public:
Num(long) ;
/ / no default constructor
/ / ...
};
vector v1(1000) ; / / error: no default Num
vector v2(1000,Num(0)) ; / / ok

The copy constructor and the copyassignment operators copy the elements of a vector. For a
vector with many elements, that can be an expensive operation, so vectors are typically passed by
reference.

vector v(10,´x´) ; / / v.size()==10, each element has the value ’x’
v.assign(5,´a´) ; / / v.size()==5, each element has the value ’a’

When an algorithm returns an iterator, that iterator is of
the same type as one of its inputs. In particular, an algorithm’s arguments control whether it
returns a const_ iterator or a nonconst
iterator. For example:
void f(list& li, const list& ls)
{
list: :iterator p = find(li.begin() ,li.end() ,42) ;
list: :const_ iterator q = find(ls.begin() ,ls.end() ,"Ring") ;
}


Non Modifying Algos
-----------------------
for_each() Do operation for each element in a sequence.
find() Find first occurrence of a value in a sequence.
find_if() Find first match of a predicate in a sequence.
find_first_of() Find a value from one sequence in another.
adjacent_find() Find an adjacent pair of values.
count() Count occurrences of a value in a sequence.
count_if() Count matches of a predicate in a sequence.
mismatch() Find the first elements for which two sequences differ.
equal() True if the elements of two sequences are pairwise equal.
search() Find the first occurrence of a sequence as a subsequence.
find_end() Find the last occurrence of a sequence as a subsequence.
search_n() Find the nth occurrence of a value in a sequence. _


Modifying Algos
-------------------
transform() Apply an operation to every element in a sequence.
copy() Copy a sequence starting with its first element.
copy_backward() Copy a sequence starting with its last element.
swap() Swap two elements.
iter_swap() Swap two elements pointed to by iterators.
swap_ranges() Swap elements of two sequences.
replace() Replace elements with a given value.
replace_if() Replace elements matching a predicate.
replace_copy() Copy sequence replacing elements with a given value.
replace_copy_if() Copy sequence replacing elements matching a predicate.
fill() Replace every element with a given value.
fill_n() Replace first n elements with a given value.
generate() Replace every element with the result of an operation.
remove_copy() Copy a sequence removing elements with a given value.
remove_copy_if() Copy a sequence removing elements matching a predicate.
unique() Remove equal adjacent elements.
unique_copy() Copy a sequence removing equal adjacent elements.
reverse() Reverse the order of elements.
reverse_copy() Copy a sequence into reverse order.
rotate() Rotate elements.
rotate_copy() Copy a sequence into a rotated sequence.
random_shuffle() Move elements into a uniform distribution.
generate_n() Replace first n elements with the result of an operation.
remove() Remove elements with a given value.
remove_if() Remove elements matching a predicate.

Sorted Sequences
-----------------
sort() Sort with good average efficiency.
stable_sort() Sort maintaining order of equal elements.
partial_sort() Get the first part of sequence into order.
partial_sort_copy() Copy getting the first part of output into order.
nth_element() Put the nth element in its proper place.
lower_bound() Find the first occurrence of a value.
upper_bound() Find the first element larger than a value.
equal_range() Find a subsequence with a given value.
binary_search() Is a given value in a sorted sequence?
merge() Merge two sorted sequences.
inplace_merge() Merge two consecutive sorted subsequences.
partition() Place elements matching a predicate first.
stable_partition() Place elements matching a predicate first,preserving relative order.

Set Algorithms
---------------
includes() True if a sequence is a subsequence of another.
set_union() Construct a sorted union.
set_intersection() Construct a sorted intersection.
set_difference() Construct a sorted sequence of elements in the first but not the second sequence.
set_symmetric_difference() Construct a sorted sequence of elements in one but not both sequences.


Heap Operations
---------------
make_heap() Make sequence ready to be used as a heap.
push_heap() Add element to heap.
pop_heap() Remove element from heap.
sort_heap() Sort the heap.


Minimum and Maximum
---------------------
min() Smaller of two values.
max() Larger of two values.
min_element() Smallest value in sequence.
max_element() Largest value in sequence.
lexicographical_ compare() Lexicographically first of two sequences. _

Permutations
------------
next_permutation() Next permutation in lexicographical order.
prev_permutation() Previous permutation in lexicographical order. _


In the description of algorithms, the template parameter names are significant. In, Out, For, Bi,
and Ran mean input iterator, output iterator, forward iterator, bidirectional iterator, and randomaccess
iterator, respectively (§19.2.1). Pred means unary predicate, BinPred means binary predicate
(§18.4.2), Cmp means a comparison function (§17.1.4.1, §18.7.1), Op means unary operation,
and BinOp means binary operation (§18.4).

§18.4.4.1 A binder allows a twoargument
function object to be used as a singleargument
function by binding one argument to a value.
§18.4.4.2 A member function adapter allows a member function to be used as an argument to
algorithms.
§18.4.4.3 A pointer to function adapter allows a pointer to function to be used as an argument
to algorithms.
§18.4.4.4 A negater allows us to express the opposite of a predicate.


Collectively, these function objects are referred to as adapters. These adapters all have a common
structure relying on the function object bases unary_ function and binary_ function (§18.4.1). For
each of these adapters, a helper function is provided to take a function object as an argument and
return a suitable function object. When invoked by its operator()(), that function object will
perform the desired action. That is, an adapter is a simple form of a higherorder
function: it takes
a function argument and produces a new function from it:




Predicate??


Map??

Wednesday, July 12, 2006

Chapter11. exercise #1


using namespace std;

struct X {
int i;

// This does not utomatically convert an int to X. I was WRONG here.
X(int pi) : i(pi) {
std::cout << "i is " << pi << "\n";
}

X operator+(int j) // Adding int to class aka x+1 types... Must return another x or x&
{
cout << "j is " << j <<"\n";
return X(i+j);
}
};

struct Y {
int i;

// This does not automatically convert an X to Y. I was WRONG here.
Y(X x)
{
std::cout << "In y(x) ctor\n";
i = x.i;
}

Y operator+(X pX) // Adding x to class aka y+x types. Must return another y or y&
{
std::cout << "In y::operator+(x) with val " << pX.i << "\n";
return Y( X(i + pX.i) );
}

// Convert y to int
operator int() // Converrts y to int. Will return int even if the func sig doesn't say so..
{
return i;
}

};

extern X operator*(X pX, Y pY)
{
std::cout << "x is " << pX.i << " and y is " << pY.i << "\n";
return X(pX.i * pY.i);
}

extern int f(X pX)
{
std::cout << "In f(X)\n";
return pX.i;
}

/*
extern int f(int x)
{
std::cout << "In f(int)\n";
return x;
}
*/

X x = 1;

Y y = x;

int i = 2;



int main()

{

std::cout << "Before\n";
std::cout << "**" << i + 10; // Simple Integer Add
std::cout << "After\n";

std::cout << "Before\n";
x = x + 10; // Simple Integer Add
std::cout << "**" << x.i << "\n";
std::cout << "After\n";

std::cout << "Before\n";
//x = 10 + x; // Simple Integer Add not permitted..
std::cout << "**" << x.i << "\n";
std::cout << "After\n";

/*
std::cout << "Before\n";
y = y + 10;
std::cout << "**" << y.i << "\n";
std::cout << "After\n";
*/

/*
std::cout << "** Before\n";
//y =
10 + y;
std::cout << "**" << 10 + y << "\n";
std::cout << "After\n";
*/

//y + X(10); // y operator+(X)

//y + X(10) * y; // extern op followed by y operator+(X) ;

/*

std::cout << "Before\n";
x + y + i; // INVALID or x operator+(int) after y reduces to an int followed Anothr x operator+(int)
std::cout << "After\n";
std::cout << 106 + y; // x+y -> y + y -> y + x .. Actually it outputs an int :P
std::cout << "After\n";
*/

std::cout << "B4 x is " << x.i << " and i is " <x * x + i; // extern X operator*(X, Y) ; followed by x operator+(int) ;
std::cout << "After\n";

std::cout << "Since there is ctor conv between int and x. The following is valid\n";
f(7) ; // extern int f(X) ;


std::cout << "Since there is no conv from y to x, the following is invalid\n";
//f(y) ; // INVALID or f(y) to f(int) to f(X)


std::cout << "####### Before $$$$$$$$\n";
y + y; // y operator+(X)
std::cout << y + y << "\n";
std::cout << "GHJHHJJHJHn After *((**(()( \n";


return 0;
}



Tuesday, July 11, 2006

Operator Overloads


#include
using namespace std;

class X {
int mVal;
public:
void operator+(int) {
std::cout << " In x::operator+(int)\n";
}

X(int x) : mVal(x)
{
std::cout << "In X(int)\n";
}
};

void operator+(X,X)
{
std::cout << " In operator+(X,X)\n";
}
void operator+(X,double)
{
std::cout << " In operator+(X,double)\n";
}

void f(X a)
{
a+1; // a.operator+(1)
1+a; // ::operator+(X(1),a)
a+1.0; // ::operator+(a,1.0)
}

int main(void)
{
X x(10);
f(x);
return 0;
}

Saturday, July 08, 2006

Object Pool
===========

#include
#include
#include
using namespace std;

class Fred {
public:
static Fred* create(std::string name) throw(bad_alloc); //<-- 1
virtual void discard() throw(); //<-- 2
static bool flushPool() throw(); //<-- 3
std::string name() { return mName; }
private:
Fred(std::string name) throw(); //<-- 4
~Fred() throw(); //<-- 5
void init(std::string name) throw(); //<-- 6
Fred* nextRecycled_;
static Fred* headRecycled_;
std::string mName;
};

void Fred::init(std::string name) throw()
{
if (mName != name)
std::cout << "Old Name : " << mName << " New Name: " << name << "\n";

mName = name;
// ... //<-- 7
nextRecycled_ = NULL;
}

Fred::Fred(std::string name) throw() : mName(name)
{ init(name); }

Fred::~Fred() throw()
{ } //<-- 8

Fred* Fred::headRecycled_ = NULL;

Fred* Fred::create(std::string name) throw(bad_alloc)
{
// If there isn't any discarded entry in the list, create new one
if (headRecycled_ == NULL) {
std::cout << "Creating new Fred with name " << name << ".\n";
return new Fred(name);
}

// Recycle old entries..
Fred* p = headRecycled_;
headRecycled_ = headRecycled_->nextRecycled_;
p->init(name); // <-- 9

return p;
}

void Fred::discard() throw()
{
nextRecycled_ = headRecycled_;
headRecycled_ = this;
}

bool Fred::flushPool() throw()
{
bool stuffGotDeleted = (headRecycled_ != NULL);

// Check out this logic
while (headRecycled_ != NULL) {
std::cout << "Deleting " << headRecycled_->name() << "\n";
delete create(headRecycled_->name());
}

return stuffGotDeleted;
}

int main(void)
{
Fred* manu = Fred::create("Manu");
Fred* pooja = Fred::create("Pooja");
Fred* mummy = Fred::create("Mummy");
manu->discard();

Fred::flushPool();

return 0;
}

This page is powered by Blogger. Isn't yours?