#include <sstream>
#include <string>
#include <iostream>
template< typename T > inline std::string to_string( const T& v )
{
std::ostringstream stm ;
return (stm << v) ? stm.str() : "error" ;
}
int main()
{
double value = 1.2345 ;
std::string str_value = to_string(value) ;
// c++0x
// std::string str_value = lexical_cast<std::string>(value) ;
std::cout << value << '\t' << str_value << '\n' ;
}this article should contain all the information that you need: http://www.ddj.com/cpp/184403638;jsessionid=S0L5ADAGUG4VKQSNDLRSKH0CJUNN2JVN?pgno=4 take note of the date it was written; the references to Microsoft C++ are to the now obsolete VC++ 6.0 and not to the current 8.0 version, which has a complete rewrite of the standard c++ library (based on Dinkumware).
mostUsed is a const. use a const_iterator. also a prefix increment instead of a postfix (efficiency)
for ( map<string,int>::const_iterator word = mostUsed.begin() ;
word != mostUsed.end() ; ++word ) { /*...*/no. i really meant even without gcc 4.3
i would use something like a std::vector< boost::any >
or a std::list< boost::variant<int,double,std::string> >
both of which are typesafe. and i would get the same functionality.
i also would not write functions that took several dozens of arguments; so even the overloaded template technique would be quite adequate for my limited needs.
> There are no compilers that support it
the output that i posted is with the code compiled by gcc 4.3 today; they are not my visualization of how it would look like in 2020.
> we still have to resort to stdarg.h to get variable argument functions
you may have to. i do not. even without gcc 4.3.
all my attempts at generating the functions using boost.preprocessor have resulted in code that was difficult to read and difficult to debug. (i really do not know how to debug preprocessor code other than by looking at the generated cpp output. and none of the versions i tried ended up being very readable).
but there is good news. c++ programmers will never have to use the unsafe and error-prone <cstdarg> ; c++0x has a solution. using variadic templates, we can write a typesafe function taking an arbitrary number of arguments of arbitrary types. http://en.wikipedia.org/wiki/C++0x#Variadic_templates
here is how you would write largest_of a variable number of values in c++0x.
#include <iostream>
#include <string>
// compile with gcc 4.3 with the -std=c++0x switch
template< typename T > inline
const T& largest_of( const T& a, const T& b )
{ return a>b ? a : b ; }
template< typename T, typename ...REST > inline
const T& largest_of( const T& first, const REST&... rest... )
{ return largest_of( first, largest_of( rest... ) ) ; }
int main()
{
std::cout << largest_of( 1, 9, 2, 8, 3, 7, 4, 6, 5 ) << '\n' ;
std::cout << largest_of( 5.3, 8.9, -3.2, 17.8, 4.2, 7.0 )
<< '\n' ;
const std::string s1("abc"), s2("2345"),
s3("vufuk"), s4("ffyfyu") ;
std::cout << largest_of( s1, s2, s3, s4 ) << '\n' ;
}
/**
>g++43 -Wall -std=c++0x -pedantic -Werror largest_of.cc && ./a.out
9
17.8
vufuk
*/> What if he wants 50 arguments, do you want to write 50 templates ?
no. i would strongly discourage him from trying to write functions which need more than seven or eight arguments.
> One function -- an infinite (almost) number of arguments
with the template: One function -- an infinite (almost) number of types.
and completely typesafe.
> and you don't have to screw around writing millions of templates or overloaded functions.
with the template: you don't have to screw around breaking your code each time (i suppose you would say millions of times) a new type needs to be supportd.
> You should be glad he didn't use the boost libraries. lolz
yes, you should be glad. i did considor using the boost preporocessor metaprogramming library http://www.boost.org/libs/preprocessor/doc/index.html to generate the overloaded max functions. but dropped the idea as i thought it may confuse many people.
> just how would that help the OP create a function that takes a variable number of arguments
you can call max with anything between 2 to 8 arguments; that is a variable number in my book. in any case, the C++ standard recommends some minimum values for such things as the maximum number of arguments for a function(256), the maximum nesting level of compound statements (256) etc. compilers can exceed these, but variable number of arguments does have an upper limit, no matter what technique you use. in my example, the upper limit is 8 (a reasonable value according to me. others may have different idea of what would be a reasonable value for an upper limit on number of arguments to be passed to a function. and they can create more overloads of max if they want).
> the arguments are all the same data type
yes, the OP wanted all arguments to be double values. and finding the largest implies that all arguments must support comparisons between them.
> I want to make a program with a max function taking any number of type double and returns the greatest of them
for a small number of arguments (upto about seven or so), you could use overloaded function names.
#include <iostream>
#include <algorithm>
template< typename T > inline
const T& max( const T& a, const T& b, const T& c )
{ return std::max( std::max(a,b), c ) ; }
template< typename T > inline
const T& max( const T& a, const T& b, const T& c, const T& d )
{ return std::max( std::max(a,b), std::max(c,d) ) ; }
template< typename T > inline
const T& max( const T& a, const T& b, const T& c,
const T& d, const T& e )
{ return std::max( std::max(a,b), max(c,d,e) ) ; }
template< typename T > inline
const T& max( const T& a, const T& b, const T& c,
const T& d, const T& e, const T& f )
{ return std::max( max(a,b,c), max(d,e,f) ) ; }
template< typename T > inline
const T& max( const T& a, const T& b, const T& c, const T& d,
const T& e, const T& f, const T& g )
{ return std::max( max(a,b,c,d), max(e,f,g) ) ; }
template< typename T > inline
const T& max( const T& a, const T& b, const T& c, const T& d,
const T& e, const T& f, const T& g, const T& h )
{ return std::max( max(a,b,c,d), max(e,f,g,h) ) ; }
int main()
{ …here are a few utilities in bsd ports.
>cat /usr/ports/textproc/rtfreader/pkg-descr
RTF is the Microsoft Richtext Format, a more portable, mostly-ASCII
formatting language that is exported by word processors like MS Word.
These files generally have the extension .rtf, but occassionally have
.doc extensions as well. This parser is from the Microsoft spec,
"ported" to Unix systems.
WWW: http://www.fiction.net/blong/programs/#rtf
>cat /usr/ports/textproc/rtf2html/pkg-descr
A simple rtf2html converter. If no file is specified rtf2html reads from
standard input.
- ehaupt
ehaupt@critical.ch
>cat /usr/ports/textproc/rtfx/pkg-descr
rtfx converts RTF files into a generic XML format. It majors on keeping
meta data like style names, etc... rather than every bit of formatting.
This makes it handy for converting RTF documents into a custom XML
format (using XSL or an additional processing step).
RTF features supported: page breaks, section breaks, style names,
lists (various types), tables, footnotes, info block, bold, italic,
underline, super/sub script, hidden text, strike out, text color, fonts.
Author: Nielsen <nielsen at memberwebs.com>
WWW: http://memberwebs.com/nielsen/software/rtfx/
>cat /usr/ports/textproc/unrtf/pkg-descr
UnRTF is a command-line converter from RTF (Rich Text) to HTML, LaTeX,
PostScript, plain text, and text with VT100 codes. When converting to HTML, it
supports tables, fonts, embedded images, hyperlinks, paragraph alignment, and
more. All other conversions are "alpha" i.e. being newly developed.
WWW: http://www.gnu.org/software/unrtf/unrtf.html
>cat /usr/ports/print/rtf2latex/pkg-descr
rtf2LaTeX is a …
ok, here is a (somewhat similiar) example.
#include <iostream>
class time_of_day // hh:mm:ss
{
public :
time_of_day( int hr, int min, int sec ) ;
bool equals( time_of_day that ) const ;
time_of_day advance_by_secs( int secs ) const ;
int hour() const { return seconds_since_midnight / (60*60) ; }
// etc
private: int seconds_since_midnight ;
};
time_of_day::time_of_day( int hr, int min, int sec )
{
// validate hr(0-23), min(0-59), sec(0-59)
seconds_since_midnight = hr * 60 * 60 + min * 60 + sec ;
}
bool time_of_day::equals( time_of_day that ) const
{
// called as: time_of_day_one.equals( time_of_day_two )
// equals is a binary operation; compares two
// time_of_day variables for equivalence.
// one of them is the time_of_day on which the function
// is called (time_of_day_one); identified by the this pointer
// the other (time_of_day_two) is available as the arg 'that'
return /* this-> */ seconds_since_midnight ==
that.seconds_since_midnight ;
}
time_of_day time_of_day::advance_by_secs( int secs ) const
{
enum { SECS_PER_DAY = 24*60*60 };
time_of_day result = *this ; // make a copy
result.seconds_since_midnight += secs ;
// this is just to correct for overflow or underflow
// could ignore this for now and focus on the rest.
while( result.seconds_since_midnight < 0 )
result.seconds_since_midnight += SECS_PER_DAY ;
if( result.seconds_since_midnight >= SECS_PER_DAY )
result.seconds_since_midnight %= SECS_PER_DAY ;
return result ;
}
int main()
{
int hr = 10, min=32, sec=45 ;
time_of_day tod_one( hr, min, sec ) ;
// now tod_one's member variable seconds_since_midnight
// has safely stored the value computed …why don't you use this hint that your instructor has given you? it seems to be the simplest way to implement TMoney:
> Hint: we would suggest storing the whole amount as an amount of cents. In this case you will
> keep $1.20 as 120 and you will use division by 100 (amount/100) to get the number of dollars
> and modulo operator % (amount % 100) to retrieve amount of cents.
and avoid floating point altogether; for calculations, for input, for everything.
> It doesn't seem like I can just use t.add(), or t.times() just like that. How will the methods know what to work on?
the method TMoney::add should take an argument (amount to be added), multiply should also take an argument (the multiplier). so your code would look like t = t.add(t1), or t = t.times(3) etc. these are there in the code you posted originally. a const correct version of which would be
{
// ...
bool greater( TMoney b) const ;
bool equals (TMoney b) const ;
TMoney add(TMoney b) const ;
TMoney times (int i) const ;
// etc.
};> I'm never using that header file in my entire life again.
that is a wise decision.
> While we are at it, tell me since which year was it deprecated
it is not merely deprecated; it has been removed from the standard (c++98).
compilers still ship with the header though (to support legacy code).
since you are on a windows machine, you could download cygwin which has a more modern version of gcc. http://www.cygwin.com
> BTW the code you gave will generate errors.
yes, it would. modify as
cout << "decimal: " << 30 << " hex: " << hex << 30 << " shifted left by 1 gives decimal: "
<< dec << (30 << 1) << " hex: " << hex << (30 << 1) << endl << dec ;> for using c++ with DJGPP
a. yes you have to use gcc on the command line (with a -X c++ switch in some cases).
b. for using c++ headers, see http://www.delorie.com/djgpp/v2faq/faq8_3.html
and you may have to use pre-standard headers <iostream.h> etc.
you really should not be using a pre-standard c++ compiler. anything released after about 2000 or so would be more or less ok.
> I don't have a g++ compiler
if you have gcc (the gnu compiler collection), you also have g++ (it's c++ compiler)
use it from the same command line where you earlier used gcc.
> Do you all think if it's because I'm not passing any flags like in cl.exe /EHsc?
no.
> You just need to make situations to learn how to implement them, and enjoy the joys of programming.
do not look at language facilities like a mountaineer looks at mount everest. you will not enjoy the joys of programming very much. to learn how to implement them, you could use code like what you have written
cout << "5 times 2 is " << (5 << 1) << endl
<< "20 divided by 4 is " << (20 >> 2) << endl;or even better,
cout << "decimal: " << 30 << " hex: " << hex << 30 << " shifted left by 1 gives decimal: "
dec << (30 << 1) << " hex: " << hex << (30 << 1) << endl << dec ;to compile c++ code, use g++ (not gcc). eg.
>g++ -Wall -std=c++98 -pedantic -Werror expre_Shift_Operators.cpp -o expre_Shift_Operators.exe> I'm still a bit confused as where to implement them
nowhere, unless you encounter a situation where you absolutely cannot do without them.
> intl were using floatl floatl members were using intl how to solve this !
to declare the floatl members using intl, a declaration of intl would suffice.
to define them, a definition of intl is required.
so do things in this order:
a. declare the classes first.
b. define the classes (which have declarations of their members)
c. define the members.
for example:
//********* header b.h ***************
#ifndef _B_H_INCLUDED_
#define _B_H_INCLUDED_
struct A ;
// A has been declared; we can now declare (not yet define) functions using A
struct B
{
inline int b_fun( const A& a ) ;
int bm ;
A* a ;
friend inline int b_friend( B& b, const A& a ) ;
};
#endif // _B_H_INCLUDED_
//////////////////////////////////////////////////////////////////
//********* header a.h ***************
#ifndef _A_H_INCLUDED_
#define _A_H_INCLUDED_
struct B ;
struct A
{
inline int a_fun( const B& b ) ;
int am ;
friend inline int a_friend( A& a, const B& b ) ;
};
#endif // _A_H_INCLUDED_
/////////////////////////////////////////////////////////////////////
//********* header anything_else.h ***************
#ifndef _ANYTHING_ELSE_H_INCLUDED_
#define _ANYTHING_ELSE_H_INCLUDED_
#include "a.h"
#include "b.h"
// A and B have been defined; we can now define functions using A and B
int A::a_fun( const B& b ) { return am += b.bm ; }
int B::b_fun( const A& a ) { return bm += a.am ; }
int a_friend( A& a, const B& b ) { return a.am += b.bm ; }
int b_friend( B& b, const A& a ) { …> functions are defined in 5 different headers
what do these look like?
> a header allheaders.h which include all the header files
in what order?
if MyControl is a polymorphic type:
// ....
try
{
MyControl& control = dynamic_cast<(MyControl&>( mControl ) ;
control.DoSomething();
}
catch( const std::bad_cast& )
{
// TODO: cast failed; handle it
}
// ...if not:
// ....
MyControl& control = static_cast<(MyControl&>( mControl ) ;
// it is the programmer's (this means your) responsibility to make sure
// that this cast is correct.
control.DoSomething();
// ...your original code was fine *except* for that it did not take care of end of file correctly.
while(fin)
{
ch=fin.get(); // this may fail; if it does
// ch will get the coerced value of char_traits<char>::eof()
while(ch==' ')
{
if(count==0)
fout.put(ch);
ch=fin.get(); // this too may fail
// ch will again get the coerced value of
// char_traits<char>::eof() which may or may not be == ' '
count++;
}
fout.put(ch);
count=0;
}> while(fin) is running endlessly ..
in general, when reading an entire file, it is a good idea to embed the input statement inside the while loop's condition. this would eliminate a lot of subtle errors. and the loop will exit once eof is reached. eg.
#include <fstream>
int main()
{
std::ifstream in( "in.txt" ) ;
std::ofstream out( "out.txt" ) ;
char ch ;
bool last_was_space = false ;
while( in.get(ch ) )
{
if( ch != ' ' )
{
out.put(ch) ;
last_was_space = false ;
}
else if( !last_was_space )
{
last_was_space = true ;
out.put(ch) ;
}
}
}note: this will remove extra spaces; but will not take care of tab characters.
you could also
a. make the function const-correct
b. use a size_t instead of an int for the size
size_t smallestIndex( const int arr[], size_t size)
{
size_t smallestIndex=0;
int temp=arr[0];
for(size_t i=1;i<size;i++)
{
if(arr[i]<temp)
{
smallestIndex = i;
temp=arr[i];
}
}
return smallestIndex;
}> ... but getline can't be used with integers ...
it is easier to process each element in your image as a char rather than an int. eg.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cassert>
#include <iterator>
using namespace std;
struct replace_chars
{
string operator() ( const string& str ) const
{
string result = str ;
for( size_t i=0 ; i<result.size() ; ++i )
{
switch( result[i] )
{
case '0' : result[i] = ' ' ; break ;
case '1' : result[i] = '-' ; break ;
case '2' : result[i] = '=' ; break ;
case '3' : result[i] = 'O' ; break ;
// etc
}
}
return result ;
}
};
int main()
{
string filename ;
getline( cin, filename ) ;
ifstream file( filename.c_str() ) ;
size_t rows, cols ;
file >> rows >> cols >> ws ; // skip over white spaces
assert( rows>0 && cols>0 ) ;
vector< string > image ;
const string digits = "0123456789" ;
string line ;
while( getline( file, line ) && ( image.size() < rows ) )
{
assert( line.size() == cols ) ;
assert( line.find_first_not_of(digits) == string::npos ) ;
image.push_back( line ) ;
}
assert( image.size() == rows ) ;
transform( image.begin(), image.end(),
ostream_iterator<string>(cout,"\n"),
replace_chars() ) ;
}remove the #include of the resource script from your main.cpp
//main.cpp
#include <windows.h>
#include "resource.h"
//#include "Untitled.rc"
// ...#include <iostream>
using namespace std;
int main()
{
int counter = 0 ;
int sum = 0 ;
const int limit = 7 ;
int num_days = 0 ;
while( counter < limit )
{
int number ;
cin >> number ;
if (number > 0)
{
sum = sum + number;
num_days = num_days + 1;
}
counter = counter + 1 ;
}
cout << "The total minutes excersized is " << sum << endl;
if( num_days > 0 )
{
cout << "The average minutes excersized per day during this week is "
<< double(sum) / counter << endl;
cout << "The number of days excercised is " << num_days << endl;
}
}
/**
>c++ exersize.cc && ./a.out
1 0 2 3 4 0 5
The total minutes excersized is 15
The average minutes excersized per day during this week is 2.14286
The number of days excercised is 5
*/you need to accept seven integers from the user; so you need to move cin >> number; to inside the while loop that executes seven times.
counter is initially zero; so to execute the loop seven times, you should write while (counter < 7) // not <=
in addition, this expression sum / counter will do integer division; ie. if sum ==23 and counter==7, the result would be 3, not 3.28. you could either make sum a double or write double(sum) / counter to get the fractional part.
it is also a good idea to get into the habit of initializing a variable at the point of definition; this will protect you from silly errors (using uninitialized variables) and later, when you deal with more complex types, help you write more efficient code. ie. not
int counter;
int sum;
int limit;
limit = 7;
sum = 0;
counter = 0;but
int counter = 0 ;
int sum = 0 ;
int limit = 7 ;also, since limit is a constant, declare it as such eg const int limit = 7 ; or enum { limit = 7 } ; how you write code later is going to be determined to a large extent by the habits you form in the early days; forming good habits now (some people call this programming hygiene) would serve you well in the future,
perhaps this would clarify (not different, but the types involved are simpler and therefore the example is easier to follow).
void foobar( int a, int b ) {}
int main()
{
int a = 78 ;
int foo( int(a) ) ; // is this the declaration (of a function foo)
// or the definition of an int foo?
int(*pfn)(int) = &foo ; // it is a declaration!
int bar( (int(a)) ) ; // can't be the declaration (of a function bar)
int* pi = &bar ; // so, must be the definition of an int bar
// reason (int(a)) is an expression because of parantheses;
// for example
foobar( a, bar ) ; // ok
// foobar( (a, bar) ) ; // error, too few arguments to function foobar
// because (a,bar) is *a single* expression
}
int foo( int(a) )
{
return a+6 ;
}there are several threads in comp.std.c++ which discuss why the language rules are framed this way, what would have been the alternatives etc. here is one of them http://groups.google.com/group/comp.std.c++/browse_thread/thread/57b52b0a1a40a9ad
the code that you posted originally will not compile (line 16 has a typo).
> the last set of statements {also compiles} but it prints this � character...
the most likely cause is that the iterator pos == coll.end() when you dereferenced it.
> ........increasing the capacity that the buffer can hold
lookup std::basic_ios<>::rdbuf and std::basic_streambuf<>::pubsetbuf
> .........by "removing any ties" that the ostream object has
calling std::basic_ios<>::tie(0) will remove any tie.
class GBook
{
// ...
void inputGrades( int& ,int&, int& );
// ....
void displayReport( int course_number ) ;
// ...
};
// ...
void GBook::inputGrades( int& x1, int& x2, int& x3 )
{
// ...
}
// ...
void GBook::displayReport( int course_number )
{
setCourseNo( course_number );
displayMsg();
int x1, x2, x3 ;
inputGrades(x1,x2,x3);
MaxValue = max(x1,x2,x3);
cout << "max: " << MaxValue << '\n' ;
}
// ...
int main()
{
GBook book;
int cn ;
cout << "course no.: " ;
cin >> cn ;
book.displayReport( cn ) ;
}sending data:
// ...
HWND window = ::FindWindow( 0, L"app B's window title" ) ;
if( ::IsWindow(window) )
{
TCHAR message[] = L"Hello World" ;
COPYDATASTRUCT data = { 0, sizeof(message), message } ;
::SendMessage( window, WM_COPYDATA,
WPARAM( 0 /* your window's handle */ ),
LPARAM( &data ) ) ;
}
//...receiving data:
from your code it appears that you are using MFC;
a. in your CMainFrame (the top window) class (mainfrm.h) add,
class CMainFrame : public CFrameWnd
{
// ...
afx_msg LRESULT OnCopyData(WPARAM, LPARAM); // *** add this ***
// ...
};b. in mainfrm.cpp, add a mesage map entry
BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
// ... other message map entries
ON_MESSAGE( WM_COPYDATA, OnCopyData ) // *** add this ***
END_MESSAGE_MAP()c. in mainfrm.cpp, implement the message handler
LRESULT CMainFrame::OnCopyData( WPARAM wParam, LPARAM lParam )
{
COPYDATASTRUCT* pcds = (COPYDATASTRUCT*)lParam ;
// use the data
// eg.
::AfxMessageBox( LPCTSTR(pcds->lpData) ) ;
// if you want to keep the data for later use, you must
// allocate memory yourself and do a deep copy of the data
// ...
return 0 ;
}use :: SendMessage to a window of application B. and you *must* use a WM_COPYDATA message. eg.
// ...
HWND window = ::FindWindow( 0, L"app B's window title" ) ;
if( IsWindow(window) )
{
TCHAR message[] = L"Hello World" ;
COPYDATASTRUCT data = { 0, sizeof(message), message } ;
::SendMessage( window, WM_COPYDATA, 0 /* your window's handle */, &data ) ;
}>> I don't get it.
!!
#include <iostream>
int main()
{
int N ;
std::cout << "Enter Number:" ;
std::cin >> N ;
if( N < 1 || N > 10 ) /* ... */ ;
else std::cout << N * (N+1) / 2 << '\n' ;
}1 + 2 + 3 + ... + (N-1) + N == N * (N+1) / 2
for M>1, M + (M+1) + ... + (N-1) + N == N * (N+1) / 2 - M * (M-1) / 2
> I dont know how to do that ...
i suppose you have not learned about arrays yet. in which case, use your original idea
/*obtain variable nextDigit
(the first digit in the binary number, then the next and so on.)*/
oneDigit=getchar();of reading one digit at a time. eg.
#include <stdio.h>
#include <limits.h>
int main()
{
const int MAXBITS = sizeof(int) * CHAR_BIT ;
unsigned int value = 0 ;
int n = 0 ;
printf("Please enter a binary number\n");
for( ; n<MAXBITS ; ++n )
{
int ch = getchar() ;
if( (ch=='0') || (ch=='1') )
{
int bit = ch - '0' ;
value = value*2 + bit ;
}
else break ;
}
printf( "\nvalue: %u\n", value ) ;
return 0;
}int ch = getchar() ; // reads a char literal '0', '1' etc.
// the integer contains the code point for the literal (depends on the charset)
// to convert it to an integer digit with value 0, 1 etc.
if( isdigit(ch) )
{
int digit = ch - '0' ;
/* use digit */
}// ...
for( int i = 1 ; i < 10 ; ++i )
for( int j = 0 ; j < 10 ; ++j )
for( int k = 0 ; k < 10 ; ++k )
for( int m = 0 ; m < 10 ; ++m )
{
int number = i*1000 + j*100 + k*10 + m ;
int first2_plus_last2 = i*10 + j + k*10 + m ;
if( first2_plus_last2 * first2_plus_last2 == number ) /* ... */ ;
}
for( int i = 0 ; i < 10 ; ++i )
for( int j = 0 ; j < 10 ; ++j )
for( int k = 0 ; k < 10 ; ++k )
for( int m = 0 ; m < 10 ; ++m )
{
int number = i*1000 + j*100 + k*10 + m ;
if( number < 10 ) continue ;
int sum_cubes = i*i*i + j*j*j + k*k*k + m*m*m ;
if( sum_cubes == number ) /* ... */ ;
}
//...modify as follows.
# ....
# ....
$(PROGRAM): $(OBJECTS)
$(LD) -o $(PROGRAM) $(OBJECTS)
$(STRUCTURE_OBJECTS): %.o : %.cpp %.h.gch
$(CC) $(CFLAGS) -o $@ -c $<
main.o : main.cpp $(PRECOMPILED)
$(CC) $(CFLAGS) -o main.o -c main.cpp
$(PRECOMPILED): %.h.gch : %.h
$(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"
#...
#...>> yes but i don't get output ... but ...
that must be because of the way you wrote the command in the make file. could tell you what is happening if you post the contents of your makefile. your makefile may contain something like this (this was there in an earlier version which you posted; it gave make errors and you must have modified it since then):
$(STRUCTURE_OBJECTS): %.o : %.c %.h.gch
$(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers">> but if i understand what you are telling i should only get this::: g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp...correct?
correct. if the compilation of LeftistHeap.cpp fails, the error is catastrophic and make should fail.
>> the merge operation takes 0 seconds....although if i print the initials and the final structure everything seems to be ok....any idea why this is happening?
the resolution of the libc clock is 7.8125 millisecs (on my machine). creating a heap of one million elements involves
a. dynamic allocation and initialization of one million nodes (this is what we optimized by means of a pool allocator)
b. creation of two million temporary heap objects (N + N/2 + N/4 + ... + 2 + 1)
c. two million pushes ino the queue
d. one million calls to merge (half the number of pushes)
e. two million pops from the queue
and all this takes 12 clock ticks or so. this is C++, not java.
the advantage of using leftist heaps is because of their ability to merge quickly; in O(log N) time. so merging two leftist heaps containing one million elements will (recursively) call merge about 25 times or so (on the average).
it is no surprise that the time taken is not measurable using the libc clock.
you could instrument your code (or use a profiler) to verify that these are the call counts.
>> ... in the end LD equals g++, right?...
usually yes, for C++ programmers. g++ invokes ld (unless invoked with the -c switch). but this may not always be what you require. for example, you may want to use g++ to compile your code on a solaris machine, but want to link with the native solaris (unix) ld instead of the gnu ld. defining LD seperately would aid portability. also, if the linker is invoked via a compiler-driver, passing switches to the linker is somewhat awkward: eg. g++ -std=c++98 -Wall -Wl, --print-map -Wl, --cref foo.cc bar.cc >> the makefile above doesn't work.... i get this error...
the makefile is written with the assumption that source files have a .c suffix. the source files you use have a .cpp suffix. the substitution (.c to .h) is failing.
>> i can't fix it because, i don't understand .. automatic variables
play around with the following toy makefile; that should give you a basic understanding of using variables in makefiles.
PROGRAM := zoo
SOURCE_SUFFIX ?= .cpp
HEADER_SUFFIX ?= .h
OBJECT_SUFFIX := .o
PRECOMPILED_SUFFIX := $(HEADER_SUFFIX).gch
ANIMALS = puma tiger meercat zebra
MAIN := main
ANIMAL_SOURCES = $(foreach ANIMAL,$(ANIMALS),$(ANIMAL)$(SOURCE_SUFFIX))
SOURCES = $(ANIMAL_SOURCES) $(MAIN)$(SOURCE_SUFFIX)
HEADERS = $(ANIMAL_SOURCES:$(SOURCE_SUFFIX)=$(HEADER_SUFFIX))
ANIMAL_OBJECTS = $(ANIMAL_SOURCES:$(SOURCE_SUFFIX)=$(OBJECT_SUFFIX))
OBJECTS = $(SOURCES:$(SOURCE_SUFFIX)=$(OBJECT_SUFFIX))
PRECOMPILED = $(HEADERS:$(HEADER_SUFFIX)=$(PRECOMPILED_SUFFIX))
CC = g++
PROCESSOR ?= pentium4
OPTIMIZE ?= -O3
override CFLAGS += -Wall -std=c++98 $(OPTIMIZE) -march=$(PROCESSOR)
the_target : one two three four three two
@echo
@echo automatic variables
@echo -------------------
@echo rule \'$@ : …>> noticed that you erased the part where i deleted the precompiled header file "LeftistHeap.h.gch", shouldn't i delete it?
it was an oversight. if you want to use precompiled headers, it would be a good idea to make sure that they are recreated as and when required. eg.
CC = g++
CFLAGS = -Wall -std=c++98 -O3
LD = $(CC)
PROGRAM = zoo
ANIMALS = puma.c tiger.c meerkat.c zebra.c
SOURCES = $(ANIMALS) main.c
HEADERS = $(ANIMALS:.c=.h)
ANIMAL_OBJECTS = $(ANIMALS:.c=.o)
OBJECTS = $(SOURCES:.c=.o)
PRECOMPILED = $(HEADERS:.h=.h.gch)
$(PROGRAM) : $(OBJECTS)
$(LD) -o $(PROGRAM) $(OBJECTS)
main.o : main.c $(PRECOMPILED)
$(CC) $(CFLAGS) -o main.o -c main.c
$(ANIMAL_OBJECTS): %.o : %.c %.h.gch
$(CC) $(CFLAGS) -o $@ -c $<
$(PRECOMPILED): %.h.gch : %.h
$(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"
.PHONY : clean
clean :
rm -f $(OBJECTS) $(PRECOMPILED) $(PROGRAM)>> i think i will try desktopBSD first chance i get...
you could try out both DesktopBSD and PC-BSD and see which one suits you better; both are FreeBSDs. PC-BSD has the larger user base, the community is very active and does seem to have more momentum at the moment. DesktopBSD is closer to FreeBSD; stable, light on resources and fast. for a comparison between the two from a newbie perspective, see: http://www.dailykos.com/story/2007/7/5/63728/62134.
>> i changed the initial simple makefile i had to this:
the gmake makefile symtax for rules is:
target : (optional) prerequisies
<tab>command1
<tab>command2
#more commandstarget and prerequisites are *files*. when you type gmake (linux aliases make to gmake) at the shell prompt without args, it looks for the default rule in the makefile (which is the first non-phony target). in your example, the default rule (after variable substitution) is:
priority_queue : main.o LeftistHeap.o # target : prerequisies
<tab>g++ -o project main.o LeftistHeap.o -O3 # commandit does not find the target file (priority_queue) and therefore executes the command in the default shell.
you should change the rule in the makefile to
$(NAME) : $(OBJS)
<tab>$(CC) -o $(NAME) $(OBJS) -O3and you will get the correct (expected) behaviour.
it would also be a good idea to modify the second rule to
.PHONY : clean # do not get confused by an actual file called clean
clean : # clean is a 'phony' target
<tab>rm -f $(NAME) $(objs)this will prevent gmake from going mad if there happens to be a file called clean in the current directory.
>> so pc-bsd is just a wrap for freebsd?
DesktopBSD http://www.desktopbsd.net/index.php?id=37 is a customized FreeBSD installation that consists of the DesktopBSD Tools and a collection of configuration files and software for desktop use.
PC-BSD is technically a "fork" of FreeBSD; it offers all the basic FreeBSD features, but also introduces …
>> the output of valgrind i posted before...what does it mean?
this is what the valgrind manual says:
Warning: set address range perms: large range <number>
Diagnostic message, mostly for benefit of the Valgrind developers, to do with memory permissions.
for a user, if the <number> keeps steadily going up (as in our case), typically indicates that the heap memory usage by the process is increasing (the heap grows from lower addresses upwards, the stack grows from higher addresses downwards). and if there are no leaks, the culprit is usually fragmentation.
>> to learn how to use gdb or valgrind ... i have to read the manual, or is there an alternative {and easier!} way?
i can't think of a better way than reading these manuals in front of a machine where you try things out as you read them. the manuals for both these tools are pretty good.
>> these are the tools you use for this job right?
no. i did not use gdb at all. used top to look at process memory usage and then valgrind.massif to profile the heap (checked fragmentation). once i realized that the heap fragmentation seemed to be the problem, the rest of the investigation was carried out by:
a. replacing the vector with a c style array with static storage duration and test the program.
b. replace boost.pool with an (incomplete minimal) pool allocator that i wrote and test the program.
…
#ifndef MINIMAL_POOL_H
#define MINIMAL_POOL_H
#include <cstddef>
#include <boost/utility.hpp>
template< size_t N > struct block_t // N == size of each allocated block
{
union
{
char data[N] ; // user data : block is allocated
block_t* next_free ; // for linked list of free blocks : block is free
};
};
// N == size of each allocated block
template< size_t N, size_t ALIGN = 4 > struct chunk_t
{
enum { BLOCK_SIZE = ((N+ALIGN-1)/ALIGN)*ALIGN }; // align on ALIGN byte boundary
enum { ALLOC_GRANULARITY = 1024*1024 }; // amout of memory alloc'ed at one time
enum { BLOCKS_PER_CHUNK = ( ALLOC_GRANULARITY - sizeof(chunk_t*) ) / BLOCK_SIZE };
typedef block_t<BLOCK_SIZE> block_type ;
block_type blocks[BLOCKS_PER_CHUNK] ; // sub-allocate out of this
chunk_t* next_chunk ; // to keep linked list of chunks
};
template< size_t N, size_t ALIGN = 4 > struct minimal_allocator : private boost::noncopyable
{
typedef chunk_t<N,ALIGN> chunk ;
typedef typename chunk::block_type block ;
minimal_allocator() : first_chunk(0), first_free(0) {}
inline ~minimal_allocator() ;
inline void* allocate() ;
inline void free_all_blocks() ;
private:
inline void allocate_chunk() ;
chunk* first_chunk ;
block* first_free ;
};
// release all chunks
template< size_t N, size_t ALIGN >
minimal_allocator<N,ALIGN>::~minimal_allocator()
{
chunk* pc = first_chunk ;
while( pc != 0 )
{
first_chunk = first_chunk->next_chunk ;
delete pc ;
pc = first_chunk ;
}
}
template< size_t N, size_t ALIGN >
void minimal_allocator<N,ALIGN>::allocate_chunk()
{
chunk* pc = new chunk ;
// add all blocks in this chunk to list of free blocks
for( size_t i = 0 ; i<(chunk::BLOCKS_PER_CHUNK-1) ; ++i )
pc->blocks[i].next_free = pc->blocks + i+1 ;
pc->blocks[chunk::BLOCKS_PER_CHUNK-1].next_free = first_free ;
first_free = pc->blocks ;
// add this chunk to list of chunks
pc->next_chunk = first_chunk ;
first_chunk = pc ;
}
template< size_t N, size_t ALIGN >
void* minimal_allocator<N,ALIGN>::allocate()
{
if( !first_free ) allocate_chunk() ;
block* pb = first_free ;
first_free = first_free->next_free ;
return pb ;
}
// mark all blocks as free blocks
template< size_t N, size_t ALIGN >
void minimal_allocator<N,ALIGN>::free_all_blocks()
{
chunk* pc = first_chunk ;
first_free = pc ? pc->blocks : 0 ;
while( pc != 0 )
{
// add all blocks in this chunk to list of free blocks
for( size_t i = 0 ; i<(chunk::BLOCKS_PER_CHUNK-1) ; ++i )
pc->blocks[i].next_free = pc->blocks + i+1 ;
pc->blocks[chunk::BLOCKS_PER_CHUNK-1].next_free =
pc->next_chunk ? pc->next_chunk->blocks : 0 ;
pc = pc->next_chunk ;
}
}
#endif // MINIMAL_POOL_H>> I use ubuntu, because it is easy to set up everything and get a working system ie codecs, development,...
true enough. and only windows has better support for all kinds of hardware. i guess that is why it is popular.
>> In my old pc{P3 800mhz}, i have installed freeBSD. When i become more savvy, i want to migrate it to my "good" pc...but for now i relatively new and noob to the whole unix stuff...
true again. freebsd is primarily a unix server, not ideal for someone very new to unix. you might try using pc-bsd; i'm told that it is very easy to set up. http://www.pcbsd.org/?p=learnhome
and dru lavigne thinks that it is easier to set up than kubuntu. http://blogs.ittoolbox.com/unix/bsd/archives/kubuntu-vs-pcbsd-18431
freebsd will run quite well on a P3 800mhz machine. it is quite a "good" machine to run freebsd on for personal use.
>> i must admit i have never heard before for fragented heap... i strikes me weird though that noone has experience it before... I mean, ok maybe you don't try everyday to allocate-deallocate 1million elements 15 times...but still.....
try googling for 'fragmentation memory' and see how many results come up. like this one: http://www.cs.utk.edu/~huangj/cs360/360/notes/Fragmentation/lecture.html
ok. did a few more investigations. the memory allocation for the vector and that of boost::pool<> appear to interract unfavourably with each other, resulting in heap fragmentation. to avoid this, the following change was also made in main.cpp (in addition to the earlier change: call destructor/constructor sequence of node_pool to deallocate all memory).
//For vector randomization
vector<int> vec ;
vec.reserve(HOW_MANY_ELEMENTS) ;
generate_n( back_inserter(vec), size_t(HOW_MANY_ELEMENTS), generator ) ;changed to
static vector<int> vec(HOW_MANY_ELEMENTS) ;
generate_n( vec.begin(), size_t(HOW_MANY_ELEMENTS), generator ) ;and the problems disappeared. i ran it with 1 million elements for 128 iterations. as would be expected, the performance improved marginally (because of better cache locality) after the first few iterations and then remained steady. here is an extract of the results. complete results are in the attached tar.bz2 file.
>g++ -std=c++98 -Wall -I/usr/local/include -O3 -funroll-loops -march=pentium4 main.cpp LeftistHeap.cpp && ./a.out
#############################################
Start of Data-Structure Testing
Priority Queue
# elements: 1000000
#############################################
Initialize 0... end of init 0 time taken: 101.562 ms
Initialize 1... end of init 1 time taken: 101.562 ms
Initialize 2... end of init 2 time taken: 101.562 ms
Initialize 3... end of init 3 time taken: 93.750 ms
Initialize 4... end of init 4 time taken: 93.750 ms
Initialize 5... end of init 5 time taken: 93.750 ms
Initialize 6... end of init 6 time taken: 85.937 ms
Initialize 7... end of init 7 time taken: 93.750 ms
Initialize 8... end of init 8 time taken: 93.750 ms
Initialize 9... end of init …