Posts by vijayan121

A fast (very fast) implementation of the Sieve of Atkin: http://cr.yp.to/primegen.html

The less well known Sieve of Sundaram:

#include <vector>
#include <algorithm>
#include <iostream>

// sieve of sundaram (naive implementation)
std::vector<int> generate_primes( int N ) 
{
    const int M = N / 2 ;
    std::vector<bool> sieve( M, true ) ;
    for( int i = 1 ; i < M ; ++i )
    {
        const int L = (M-i) / ( 2*i + 1 ) ;
        for( int j = i ; j <= L ; ++j )
            sieve[ i + j + 2*i*j ] = false ;
    }

    std::vector<int> primes ;
    primes.push_back(2) ;
    for( int i = 1 ; i < M ; ++i ) 
        if( sieve[i] ) primes.push_back( i*2 + 1 ) ;
    return primes ;
}

int main()
{
    std::vector<int> primes = generate_primes(100) ;
    std::for_each( primes.begin(), primes.end(), 
                   [] ( int n ) { std::cout << n << ' ' ; } ) ; // C++1x
    std::cout << '\n' ;
}

And the exotic visual sieve: http://plus.maths.org/issue47/features/kirk/index.html

My understanding is that in C++ there are much more elegant ways of handling this.

There are. For instance, using a polymorphic call wrapper.
std::function (C++1x), std::tr1::function (C++98 with tr1 extensions) or boost::function (vanilla C++98).

For example C++98 with boost:

#include <boost/function.hpp>
#include <boost/bind.hpp>
#include <iostream>

struct NewtonRaphson
{
    typedef boost::function< double( double& ) > function_t ;

    void set_it( function_t fun ) { function = fun ; }

    double call_it( double& arg ) { return function(arg) ; }

    function_t function ;
};

float free_fun( double& d )
{ std::cout << "::freefun( " << d << " ) => " ; return d += 1.0 ; }

struct function_object
{
  long double operator() ( double& d ) const
  { std::cout << "::function object( " << d << " ) => " ; return d += 2.0 ; }
};

struct asolver
{
    double compute( double& d ) const
    { std::cout << "asolver::compute( " << d << " ) => " ; return d += 3.0 ; }
};

int main()
{
    NewtonRaphson nr ;
    double d = 10.5 ;

    nr.set_it( free_fun ) ;
    std::cout << nr.call_it(d) << '\n' ;

    nr.set_it( function_object() ) ;
    std::cout << nr.call_it(d) << '\n' ;

    asolver solver ;
    nr.set_it( boost::bind( &asolver::compute, solver, _1 ) ) ;
    std::cout << nr.call_it(d) << '\n' ;
}

It is not shown in the snippet, but you could also wrap a lambda function.

What is the integer or double equivalent of the NULL...The computer checks the particular index in the array to know if it contains a value or not.

What we are talking about here is the null in the relational database world; the SQL NULL, which essentially says that "this information is missing" or "no information has been stored for this".

For example, "What was the int that the user entered as input?"
78 - the user entered 78
-3 - the user entered -3
0 - the user entered 0
null - we do not know. This information was never entered, or if it was entered, it was not stored anywhere.

The double (floating point) equivalent of the SQL NULL could probably be a NaN http://en.wikipedia.org/wiki/NaN

For int, there is no equivalent "not an int". We would have to create a user-defined type to represent that. For example:

#include <stdexcept>

struct int_or_null
{
   int_or_null() : nothing(true) {}
   int_or_null( int i ) : something(i), nothing(false) {}

   bool is_null() const { return nothing ; }
   operator bool() const { return !nothing && something ; }

   int_or_null& operator= ( int i ) { something = i ; nothing = false ; return *this ; }
   int_or_null& make_null() { nothing = true ; return *this ; }

   // comparison operators for null are similar to those for NaN
   bool operator== ( const int_or_null& that ) const
   { return nothing ? false : !that.nothing && something==that.something ; }
   // …

Here is the PowerBASIC program I’m trying to implement and match as close as possible speed wise in either C or C++. It’ll do this 2MB buffer thing in 0.078 seconds (78 ticks) on my old laptop…

This is how I would translate the PowerBASIC code to C++

#include <string>
#include <algorithm>
#include <iostream>

// BEWARE OF DOG. SLIPPERY WHEN WET.

int main()
{
    enum { K = 7, N = 2*1024*1024, N1 = N + N/7, BLOCKSZ = 90, M = N1 + 2*N1/BLOCKSZ, TAIL = 4000 } ;
    const char* const crnl = "\r\n" ;
    typedef std::string::size_type size_type ;
    typedef std::string::iterator iterator ;

    // create a string containing N ' '
    std::string str( N, ' ' ) ;

    // replace every Kth ' ' with a 'P'
    for( size_type i = K-1 ; i < N ; i += K ) str[i] = 'P' ;

    // replace every 'P' with a 'PU'

    // we could do this in quadratic time by:
    // for( size_type i = K ; i < N1 ; i += K+1 ) str.insert( str.begin()+i, 'U' ) ;

    // however, by using some temporary memory, we can do it in linear time by:
    {
        std::string temp ;
        temp.reserve(N1) ;
        iterator i = str.begin() + K ;
        const iterator end = str.end() - K ;
        for(  ; i < end ; i += K )
        {
            temp.insert( temp.end(), i, i+K ) ;
            temp += 'U' ;
        }
        temp.insert( temp.end(), i, str.end() ) ; // copy …

If the requirement is that each derived class should have no knowledge of the relative ordering of objects of that class with respect to objects of the other derived classes (any such knowledge should be localized to that part of the program where one needs to sort these objects), a non-intrusive technique has to be used. Since these are polymorphic types, you can create a predicate for the sort using RTTI. eg. to sort on type,

struct base { virtual ~base() {} /* ... */ };
struct A : base { /* ... */ } ;
struct B : base { /* ... */ } ;
struct C : base { /* ... */ } ;
struct D : A { /* ... */ } ;

struct compare_types
{
    bool operator() ( const base* first, const base* second ) const
    {
        static const std::type_info* tinfo[] = { &typeid(A), &typeid(B), &typeid(C), &typeid(D) } ;
        enum { N = sizeof(tinfo)/sizeof(*tinfo) } ;

        // check for nullptr elided
        int a = 0 ; for( ; a < N ; ++a ) if( typeid(*first) == *tinfo[a] ) break ;
        int b = 0 ; for( ; b < N ; ++b ) if( typeid(*second) == *tinfo[b] ) break ;

        return a < b ;
    }
};

void foo( std::vector<base*>& sequence )
{
    // ...
    std::sort( sequence.begin(), sequence.end(), compare_types() ) ;
    // ...
}

So far, with c++, all I know how to do is create a super class called Object and make both the Sphere and Plane classes inherit from the Object class. The problem is, when I loop through my scene objects and call the findIntersection method, I get an error saying that the Object class doesn't have a method called findIntersection. So how do I pass the findIntersection call on to the Sphere or Plane?

First, unlike in Java, non-static member functions in C++ classes are not run-time polymorphic by default. Only functions declared as virtual are bound at run-time. So the base class should be something like

class Object
{
   // ....

   public :
      // ideally findIntersection would be 'pure', but ignore that nicety for now
      virtual float findIntersection( const Ray& ray ) const { return 0 ; }

      // a virtual destructor is mandatory in C++ for any class having a virtual function
      virtual ~Object() {}

   // ....
} ;

And then we can have derived classes which override Object::findIntersection.

class Sphere : public Object
{
   public :
      virtual float findIntersection( const Ray& ray ) const
      {
          float intersection ;

          // ...

          return intersection ;
      }
};

Second, In Java class Y { ... void foo( Object x ) { ... } ... } ; x is a reference to an object. C++ does not work that way; the default in C++ is value semantics. x doesn't refer to an object somewhere, you could say that x …

Would you agree that although the void* mimics the Java interface most closely, the best C++ base would use templates?

Yes.

Also, you may want to keep this in mind. The way iterators are thought about in Java is fundamentally different from the way we use iterators in C++. Both privide an abstract mechanism to access the elements of a sequence one by one, but they use different concepts. A Java Iterator is an interface to a container; a single Java iterator knows about the entire range it traverses. A C++ iterator is an abstraction to identify one element of a sequence; it can move forward in the sequence, but has no idea about the range. In C++, we use a pair of iterators to denote a range.

Another (conceptually less important) difference is that a Java Iterator 'points' to the 'empty space' between elements of a sequence, while a C++ iterator directly 'points' to an element. The C++ iterator can be used like a pointer to an object.

A second area where the differences between the two languages is large is in resource management and error handling. Java uses the try-finally construct whereas C++ uses RAII proper.

I did some research on void* etc and the derived class would then be using templates to cast the pointer. I also note that in 'The C++ Programming Language' Stroustrup describes the use of void* in templates.

AFAIK, the use of a template specialization for void* as a …

Let us say that we have a full 3-ary tree as follows:

[B]root[/B] 0
                                           |
                  -------------------------------------------------
                  |                        |                      |
                [B]alpha[/B] 1                   [B]beta[/B] 2                 [B]gamma[/B] 3
                  |                        |                      |
        --------------------     --------------------     --------------------
        |         |        |     |         |        |     |         |         |
      [B]delta[/B] 4  [B]epsilon[/B] 5  [B]zeta[/B]   [B]eta[/B]      [B]theta[/B]    [B]iota[/B]  [B]kappa[/B]    [B]lambda[/B]      [B]mu[/B]
        |
--------------------
|        |         |
[B]nu[/B]       [B]xi[/B]      [B]omicron[/B]

A two dimensional array representation of this tree (in the manner required) could be:

row 0: root, alpha, delta, nu
row 1: root, alpha, delta, xi
row 2: root, alpha, delta, omicron
row 3: root, alpha, epsilon, null
row 4: root, alpha, zeta, null
row 5: root, beta, eta, null
row 6: root, beta, theta, null
row 7: root, beta, iota, null
row 8: root, gamma, kappa, null
row 9: root, gamma, lambda, null
row 10: root, gamma, mu, null

If the full tree is a complete tree (every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible), a one dimensional array representation is possible. For the complete 3-ary tree above:

root, alpha, beta, gamma, delta, epsilon, zeta, eta, theta, iota, kappa, lambda, mu, nu, xi, omicron
  0     1     2      3      4       5       6    7     8      9     10     11    12  13  14    15

The position of the children of node at position p would be p*3+1, p*3+2, p*3+3
The position of the …

I don't want others to edit my strings. It appears there's no easy solution for this, as I don't want any internet connection or such methods

Here's one (stand alone, without network etc.) way to do it; this might help to get you started. It assumes that all you are seeking is 'security through obscurity' (steganography), rather than cryptography proper.

the hex conversion seems to be the easist way to prevent noobs from touching the actual strings

Yes. Other than by using cryptographic techniques, you cannot stop a determined expert hacker.

a. Create a header file with declarations of identifiers for string literals to be used in the program; for example mystrings.h

extern const char* const url ;
extern const char* const message ;
// ...

b. Create a text file containing the string literals. The example assumes that these literals start with the char sequence (" and end with ") . For brevity, it is assumed that these char sequences are not present anywhere else (in comments, in quoted strings, etc.). For example, mystrings.p

#include "mystrings.h"

const char* const url = ("http://www2.research.att.com/~bs/C++0xFAQ.html") ;

const char* const message = ("hello world!") ;

// ...

c. Write a program to read such a file and generate a C++ file containing equivalent obfuscated strings. Again, for brevity, all error handling is elided and a toy obfuscation algorithm is used. obfuscate.cc

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

std::string obfuscate( const std::string& str …

Please post the code for void MainWindow::on_btnStart_clicked() . It is around line 31 of mainwindow.cpp

From the error message, you are trying to copy an object of type Producer somewhere in that function and a copy constructor for Producer can not be synthesized (because the base class copy constructor is private).

First create a user defined type to represent 23 zero bits and 1 one bit.

#include <cstdint> // C++1X (or <stdint.h> for C99)
struct pattern
{
    enum { NBYTES = 3 } ;
    std::uint8_t bytes[NBYTES] ; // 3 x 8 bits == 24 bits
};

Then provide mechanisms to read such a variable from an input stream and to compare two such variables for equality.

std::istream& operator>> ( std::istream& stm, pattern& p )
{ return stm.read( reinterpret_cast<char*>( p.bytes ), pattern::NBYTES ) ; }

bool operator== ( const pattern& first, const pattern& second )
{ return std::equal( first.bytes, first.bytes + pattern::NBYTES, second.bytes ) ; }

Finally, write the function to return a "yes" or a "no"

const char* find_pattern( const char* path_to_file )
{
    std::ifstream file( path_to_file, std::ios::binary ) ;
    std::istream_iterator<pattern> begin(file), end ;
    static const pattern search_pattern = { { 0, 0, 1 } } ; // 23 zero bits and 1 one bit
    return std::find( begin, end, search_pattern ) == end ? "no" : "yes" ;
}

The problem as I saw it was how to return the unknown 'Object'

The Java programmer's Object is the C or C++ programmers void*.
If a Java method returns an Object, you need to cast it to the correct type before you can do something useful with it.

The closest C++ equivalent would be:

#include <stdexcept>

struct Iterator
{
    virtual ~Iterator() throw() {} // required in C++ (for well-defined behaviour)

    virtual void first() throw() = 0 ;
    virtual void last() throw() = 0 ;
    virtual void next() throw() = 0 ;
    virtual void previous() throw() = 0 ;

    virtual bool isDone() const throw() =  0 ;

    virtual void* current() const throw(std::out_of_range) = 0 ;
};

Is there any way to use something like get/getline without providing an argument for storage variable?

If the type involved has default or trivial initialization, you could write such a function yourself. For example:

template< typename T > inline
T get( std::istream& stm ) throw (std::runtime_error)
{
    T temp ;
    if( !( stm >> temp ) ) throw std::runtime_error( "bad stream input" ) ;
    return temp ;
}

And then:

try { std::cout << get<int>( std::cin ) << '\n' ; }
    catch( const std::runtime_error& ) { std::cerr << "error in input\n" ; }

But it doesn't buy you much over:

int i ; if( std::cin >> i ) std::cout << i << '\n' ;
    else std::cerr << "error in input\n" ;

that shuffles the array and is straight-forward and pretty easy to implement, so that's a good solution.

It is straight-forward and pretty easy to implement, but it is not a correct solution.

There are N! ways of arranging a sequence of N elements. A random shuffle should yield uniformly distributed results; that is, the probability of any particular ordering is 1/N!. There are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but do not in fact produce a uniform distribution over the N! possible orderings. It is easy to write the random shuffle naively and get it wrong.

The Art of Computer Programming, Vol. 2, section 3.4.2 “Random sampling and shuffling”, Knuth describes two (correct) algorithms:

a. If the number of items to sort is small, then simply put all possible orderings in a table and select one ordering at random. In this particular case the table would need 12! rows.

b. “Algorithm P” which Knuth attributes to Moses and Oakford (1963), but is now known to have been anticipated by Fisher and Yates (1938); the 'Fisher–Yates shuffle' http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

always selecting j from the entire range of valid array indexes on every iteration also produces a result which is biased, albeit less obviously so. This can be seen from the fact that doing so yields n^n distinct possible sequences of swaps, whereas there are only n! possible permutations of an n-element array. Since n^n can never …

but I am not sure the Input/Output chapter covers everything I will need to know.

Any reasonable book should cover all that you need about file i/o for this task. Basically, you just need to be know how to read and write bytes (or sequences of bytes). Dictionary<int, int> would be std::map<int,int> ; read up on std::map<>.

An array of bytes would be byte[] a std::vector<unsigned char> (preferably) or just a plain C-style array; read up on std::vector<>

Why did you choose inline here

is_prime() is a small (code size) function that is called millions of times.
See: http://en.wikipedia.org/wiki/Inline_expansion

and why do you return n>1 && primes[n] ?

primes is a vector of bools where primes[n] == true if and only if n is prime.
For example, primes[13] == true and primes[18] == false n>1 && primes[n] => if n is greater than one (to take care of negative n), and primes[n] is true, then n is prime.

Why did you enumerate AMAX, BMAX, and NMAX? Why not just do make_primes(241001) ?

The idea was to make the code a bit more easy to modify; for example if the problem statement changed from
the current n² + an + b, where |a| < 1000 and |b| < 1000 to, say, n² + an + b, where |a| < 500 and |b| < 20000 .

Of course I messed up by writing

for( int a = -999 ; a < 1000 ; ++a )
{
    for( int b = -999 ; b < 1000 ; ++b )

instead of

for( int a = 1 - AMAX ; a < AMAX ; ++a )
{
    for( int b = 1 - BMAX ; b < BMAX ; ++b )

Why do you call make_primes and pass such a large value?

It is the largest value (plus one) that the quadratric n² + an + b, where |a| <= AMAX and …

Anyone got any useful optimization tips?

for (vector<int>::const_iterator it = primes.begin(); *it < check + 1; ++it) performs a linear search in O(N) time where N == primes.size()

As the primes are in sorted order, you can reduce the time to O(log N) by doing a binary search.

Better still, you can do this in O(1) (constant time) by indexing into the vector.

For example:

#include <vector>
#include <cassert>
#include <iostream>

std::vector<bool> make_primes( std::size_t N ) // primes < N
{
   std::vector<bool> sieve( N, true ) ;
   sieve[0] = sieve[1] = false ;

   for( std::size_t i = 2; i*i < N ; ++i ) if( sieve[i] )
      for( std::size_t j = i + i ; j < N ; j += i ) sieve[j] = false ;

   return sieve ;
}

inline bool is_prime( int n, const std::vector<bool>& primes )
{ return n>1 && primes[n] ; }

int main ()
{
    enum { AMAX = 1000, BMAX = 1000, NMAX = 200 } ;
    const std::vector<bool>& primes = make_primes( NMAX*NMAX + AMAX*NMAX + BMAX + 1 ) ;

    int max_axb = 0 ;
    int max_n = 0;

    for( int a = -999 ; a < 1000 ; ++a )
    {
        for( int b = -999 ; b < 1000 ; ++b )
        {
            int n = 0 ;
            while( is_prime( n*n + a*n + b, primes ) ) ++n ;
            if( n > max_n )
            {
                max_n = n ;
                max_axb = a * b …

> Considering quadratics of the form:

> n² + an + b, where |a| < 1000 and |b| < 1000

> Find the product of the coefficients, a and b, for the quadratic expression that
> produces the maximum number of primes for consecutive values of n, starting with n = 0.

>> ... I found out that b always needs to be prime ...

This assumption does not appear to be correct. Counter-examples are easy to find:

1. with n == 7, a == 2, n² + an == 49 + 14 == 63, n² + an + b is prime

for b in [ -58, -56, -52, -50, -46, ..., -10, -4, +4, +8, +10, +16, +20, ... ]

2. with n == 5, a == -4, n² + an == 25 - 20 == 5, n² + an + b is prime

for b in [ -3, -2, 0, +2, +6, +8, +12, +14, +18, +24, ..... ]

sizeof( char* )

//This doesn`t workbecause of const problem...

template <int p>    
bool FComapare (Node *lId, Node* rId) ;

Here, p must be a constant known at compile-time.

for (int i = 0;i < partNum; ++i)
{
    //This doesn`t workbecause of  const problem...
    set<Node *, bool (*)(Node*,Node*) > f(&FComapare<i>);
    m_F.push_back(f);
}

Because i is not a constant.

can I happily assume that the C++ language will handle that detail correctly without my intervention?

Yes. The implementation is responsible for setting the vtable pointer correctly during construction.

Just make sure that you do not treat C++ objects as 'raw bits'. For example:

struct A
{
    virtual ~A() {}

    A() { std::memset( this, 0, sizeof(A) ) ; /* NO! */ }

    A( const A& that ) { std::memcpy( this, &that, sizeof(A) ) ; /* NO! */ }

    A& operator= ( const A& that )
    { std::memcpy( this, &that, sizeof(A) ) ; /* NO! */ return *this ; }

    void write( std::ostream& stm ) const
    { stm.write( reinterpret_cast<const char*>(this), sizeof(A) ) ; /* NO! */ }

    void read( std::istream& stm )
    { stm.read( reinterpret_cast<char*>(this), sizeof(A) ) ; /* NO! */ }


    int i ;
    long l ;
    char c[128] ;
};

You may want to have a look at Lippman's 'Inside the C++ Object Model' http://www.amazon.com/Inside-Object-Model-Stanley-Lippman/dp/0201834545

When the loop

while(getline(ErrorFile,line))
{
}

exits, the stream is in a failed/eof state. When a stream is in an error state, all operations on the stream will fail. You need to first clear the error state before you do anything more with the stream.

For example, in the following snippet,

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
#include <iomanip>

int main()
{
    std::ifstream file( __FILE__, std::ios::in|std::ios::out) ;
    std::vector< std::streampos > pos ;
    std::string line ;
    pos.push_back( file.tellg() ) ;
    while( std::getline( file, line ) ) pos.push_back( file.tellg() ) ;

    file.clear() ; // clear the failed/eof state of the stream

    std::reverse( pos.begin(), pos.end() ) ;

    {
        // seek, get and print the last line
        if( std::getline( file.seekg( pos[0] ), line ) )
            std::cout << std::setw(5) << pos[0] << ": " << line << '\n' ;
        file.clear() ; // and again clear the failed/eof state of the stream

        // seek, get and print remaining lines (in reverse order)
        for( std::size_t i = 1 ; i < pos.size() ; ++i )
        {
            std::getline( file.seekg( pos[i] ), line ) ;
            std::cout << std::setw(5) << pos[i] << ": " << line << '\n' ;
        }
    }
}
////////////////////////////////////////////////////////////////////////////////

, no output will be generated if you comment out line 16.

As you are trying to read from a file being continuously appended to by another program, it would be prudent to just close the file each time you reach eof. And then reopen it just before the …

I think we must creat every operator for this class like: +, -, *, /, %, pow(x,y),...

Just two would suffice.

struct INT
{
    INT() {}
    INT( int value ) : builtin_int(value) {}

    operator int& () { return builtin_int ; }
    operator int () const { return builtin_int ; }

    int builtin_int ;
};

The trailing const on a non-static member function means that the abstract (logical, externally visible) state of the object pointed to by this will not be changed by this member function. Where possible, the compiler enforces this rule. However, the const specifier does not promise that the physical state ("raw bits") of the object will never change.

struct mystring
{
    private:

      int len ; // number of chars in the mystring; part of it's logical state

      char* p ; // points to the (first char of) the actual chars of the mystring
                // every char in this buffer forms part of the logical state
                // if we allocate a new buffer, copy the contents of the current buffer
                // into the new buffer, and then modify p to point to the new buffer,
                // the logical state of mystring does not change
    public:

      // ... mystring member functions

      // *** compile-time error - attempt to change the const object *this
      void foo() const { ++len ; }

      // fine by the compiler - no attempt to change the member p
      // see: http://www.parashift.com/c++-faq-lite/const-correctness.html#faq-18.15
      // *** but it is a logical error - changes the logical state of a const object
      void bar() const { if(len>0) p[0] = 'a' ; }

      // fine  - it is ok to change a different (non-const) object
      void baz() const { mystring another ; ++another.len ; /* ... */ }

      // fine  - mutable members are never const;
      // they do not …

Does any of you guys know where I can learn C++? What's the best website you know

Perhaps you would want to consider learning to use C++ in the most effective way along with learning C++. Rather than join a whole generation of programmers who started to learn the most primitive level at which one can use C++, and then continued to program for ever at that level, I would suggest a 'top-down' approach where you learn the language, the library and learn by using these to solve programming problems.

I don't know of a web resource that teaches C++ this way; perhaps you could invest in buying one first C++ book and then look at the web for additional resources. Koenig and Moo's "Accelerated C++ - Practical Programming by Example" http://www.acceleratedcpp.com/ is a good first introduction to C++.

A good book (freely available on the web) that teaches C++ in the traditional way - starting at low-level C-like aspects and then moving on to higher abstractions - is Eckel's "Thinking in C++" http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html

Some other resources you may find useful:
"C++ Annotations" from University of Groningen http://www.icce.rug.nl/documents/cplusplus/
Informit's C++ Reference Guide http://www.informit.com/guides/content.aspx?g=cplusplus
Tutorials etc at cplusplus.com http://www.cplusplus.com/

A couple of newsgroups where people learning C++ can ask questions or seek clarifications on doubts and expect to get good answers:
alt.comp.lang.learn.c-c++ http://groups.google.com/group/alt.comp.lang.learn.c-c++/about
comp.lang.c++ http://groups.google.com/group/comp.lang.c++/about

Unix tee is a filter which reads from stdin and in addition to piping the input to stdout also copies it into a file.

In C++, we can generalize the idea to a reusable component. Create a user-defined ostream that can send its output to two output streams. tee is then just a special case; read input from stdin and send output to stdout and a std::ofstream.

#include <iostream>

template < typename CHAR_TYPE,
           typename TRAITS_TYPE = std::char_traits<CHAR_TYPE> >
struct basic_teebuf : public std::basic_streambuf< CHAR_TYPE, TRAITS_TYPE >
{
    typedef std::basic_streambuf< CHAR_TYPE, TRAITS_TYPE > streambuf_type ;
    typedef typename TRAITS_TYPE::int_type int_type ;

    basic_teebuf( streambuf_type* buff_a, streambuf_type* buff_b )
            : first(buff_a), second(buff_b) {}

    protected:
        virtual int_type overflow( int_type c )
        {
            const int_type eof = TRAITS_TYPE::eof() ;
            if( TRAITS_TYPE::eq_int_type( c, eof ) )
                return TRAITS_TYPE::not_eof(c) ;
            else
            {
                const CHAR_TYPE ch = TRAITS_TYPE::to_char_type(c) ;
                if( TRAITS_TYPE::eq_int_type( first->sputc(ch), eof ) ||
                    TRAITS_TYPE::eq_int_type( second->sputc(ch), eof ) )
                        return eof ;
                else return c ;
            }
        }

        virtual int sync()
        { return !first->pubsync() && !second->pubsync() ? 0 : -1 ; }

    private:
        streambuf_type* first ;
        streambuf_type* second ;
};

template < typename CHAR_TYPE,
           typename TRAITS_TYPE = std::char_traits<CHAR_TYPE> >
struct basic_teestream : public std::basic_ostream< CHAR_TYPE, TRAITS_TYPE >
{
    typedef std::basic_ostream< CHAR_TYPE, TRAITS_TYPE > stream_type ;
    typedef basic_teebuf< CHAR_TYPE, TRAITS_TYPE > streambuff_type ;

    basic_teestream( stream_type& first, stream_type& second )
         : stream_type( &stmbuf ), stmbuf( first.rdbuf(), second.rdbuf() ) {}

    private: streambuff_type stmbuf ;
};

typedef basic_teebuf<char> teebuf ;
typedef basic_teestream<char> teestream ;

A dumbed down (no error handling, …

An example may help.

Code that does not use RAII:

struct M
{
    M() ; // may throw! 
    // ...
};

struct A
{
    A( const char* s, const char* path ) ;
    ~A() ; // required

    // ...
        
    private:
       char* cstr ;
       FILE* file ;
       M* ptr_m ;

       void init() ; // may throw!
};

A::A( const char* s, const char* path ) :
       cstr( new char[std::strlen(+1)] ),
       file( std::fopen( path, "r+t" ) ),
       ptr_m( new M ) // *** what happens if M::M() throws?
                      // cstr won't be deleted, file won't be closed
{
    std::strcpy( cstr, s ) ;
    init() ; // *** what happens if init() throws?
             // ptr_m and cstr won't be deleted, file won't be closed
}

A::~A()
{
    delete ptr_m ;
    std::fclose(file) ;
    delete [] cstr ;
}

// etc.

Code that uses RAII:

struct M
{
    M() ; // may throw!
    // ... 
};

struct A
{
    A( const char* s, const char* path ) ;
    // no need to write destructor

    // ...
    
    private:
       std::string str ;
       std::ifstream file ;
       std::tr1::unique_ptr<M> ptr_m ;

       void init() ; // may throw!
};

A::A( const char* s, const char* path ) :
       str(s), file( path, std::ios::in|std::ios::out ),
       ptr_m( new M ) // *** don't care if M::M() throws;
                      // destructors of file and str will be executed 
{
    init() ; // *** don't care if init() throws;
             // destructors of ptr_m, file and str will be executed 
}

// etc

Only half! Why?

That it is half is a clue, isn't it?
Answer: rounding error

Let f1 be a particular representable floating point number, and f2 be the next representable floating point number. If the IEEE-754 rounding method (round to nearest, ties to even) is used (as almost every current implementation does), then

f1 + delta yields f2 if delta == (f2-f1)/2

See: http://docs.sun.com/source/806-3568/ncg_goldberg.html#689

#include <boost/regex.hpp>
#include <string>
#include <boost/lexical_cast.hpp>

using namespace std;

double scrape( const std::string& base, const std::string& match )
{
    boost::regex re(match);
    boost::smatch matches;

    // while( boost::regex_search( start, base.end(), matches, re ) )
    if( boost::regex_search( base, matches, re ) )
    {
        std::string value( matches[1].first, matches[1].second );
        return boost::lexical_cast<double>(value) ;
    }
    else return 0.0 ;
}

There are no simple answers. http://www.parashift.com/c++-faq-lite/inline-functions.html#faq-9.3

In my experience, a good function to inline is one
i. which has a stable (unlikely to change) implementation.
ii. which is frequently called (the program spends a signifanct portion of its time in calling and executing the function).
iii. which has a code size comparable to the code size required to set up the activation record and call the function.

The compiler or the linker is in no position to make a judgement about i.

Unless an implementation has a good profile-guided optimizer, and the developer profiles the unoptimized program in a production environment, and makes the profiling information available to such a compiler, it is in no position to make a judgment about ii.

In reality, determining correctly if it is beneficial to inline a function requires knowledge that the compiler or linker does not have at build-time. A function that is worthwhile to inline when running on a processor with say a 4 MB processor cache and 4 GB memory (with no other serous load other than the program in question), may be harmful to inline if
i. You take it to a machine with a 2 MB processor cache and 2 GB of memory.
ii. The same 4 MB cache / 4 GB memory machine has several other programs also running simultaneously, and making demands on memory.

In general, the rules I follow are:
i. …

e2 was wrong. 7.38.....

Not really; it would be something like that. 7.389056...

In 1 + x/1! + x^2/2! + X^3/3! + ..... + x^n/n! + x^(n+1)/(n+1)! + ..... ,
just as n! == (n-1)! * n , x^n == x^(n-1) * n .
We can eliminate the computation of pow() for each term.

double x ; std::cout << "x? " && std::cin >> x ;

    double err ; std::cout << "error tolerence? " && std::cin >> err ;

    double ex = 0.0 ;
    double term = 1.0 ;

    for( int n = 1 ; term > err ; ++n )
    {
        ex += term ;
        term *= x / n ;
    }

i don't really understand it).

i would still like to know why i can create a 4 million 1D array but i can't create
a 4 million 2D array????????

For a dynamically allocated array, eg. new[] T[N] the new expression yields a pointer to the first element of the array. ie. T* ptr_first_element = new T[N] ; slong (*newarray)[limitsqr] = new slong[limitsqr][limitsqr] ; is equivalent to

typedef slong[limitsqr] array_type ;
array_type* newarray = new array_type[limitsqr] ;

We are creating an array with dynamic storage duration where each element is an array; the pointer to the first element is therefore a pointer to an array.

> Are there any library to solve this problem?

There are many libraries:
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries

char exe_name[ MAX_PATH ] ;
GetModuleFileNameA( GetModuleHandle(0), exe_name, MAX_PATH ) ;

http://msdn.microsoft.com/en-us/library/ms683197%28VS.85%29.aspx

Write comparison operators for operator< and operator== for the struct. eg.

struct A
{
    int x, y, z ;

    inline bool operator< ( const A& that ) const ;

    inline bool operator== ( const A& that ) const
    { return (x==that.x) && (y==that.y) && (z==that.z) ; }
};

bool A::operator< ( const A& that ) const
{
    if( x < that.x ) return true ;
    else
    {
        if( x > that.x ) return false ;
        if( y < that.y ) return true ;
        else
        {
            if( y > that.y ) return false ;
            return z < that.z ;
        }
    }
}

Use std::sort to sort the vector and then std::unique to move duplicates to the end of the sequence. Finally, use std::vector<>::erase to remove the duplicate elements from the vector.

void remove_dups( std::vector<A>& seq )
{
    std::sort( seq.begin(), seq.end() ) ;
    seq.erase( std::unique( seq.begin(), seq.end() ), seq.end() ) ;
}

If you feel at home with templates, you might want to have a look at boost::multi_index<>. http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/index.html

For example, a multi_index with two ordered non_unique keys would look something like this:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
using namespace ::boost ;
using namespace ::boost::multi_index ;
using namespace std ;

struct A
{
    A( int i, const char* n, double d ) : id(i), _name(n), _data(d) {}

    const int id ; // non-unique key
    const string& name() const { return _name ; } // non-unique key

    // tags for lookup
    struct by_id {} ;
    struct by_name {} ;

    private :
        string _name ;
        double _data ;
        // ...

        friend inline ostream& operator<< ( ostream& stm, const A& a )
        {
            return stm << "{ " << a.id << ", " << a.name()
                       << ", " << a._data << " }" ;
        }
} ;

typedef multi_index_container
    <

        A,

        indexed_by<
                 ordered_non_unique< tag<A::by_id>,
                        BOOST_MULTI_INDEX_MEMBER( A, const int, id ) >,

                 ordered_non_unique< tag<A::by_name>,
                    BOOST_MULTI_INDEX_CONST_MEM_FUN( A, const string&, name ) >
                  >

    > dual_key_multimap ;

template< typename TAG, typename MULTI_INDEX_CNTR > inline
void print( MULTI_INDEX_CNTR& multi_index_cntr, ostream& stm = cout )
{
    typename MULTI_INDEX_CNTR::template index<TAG>::type& seq =
                                     multi_index_cntr.get<TAG>() ;
    copy( seq.begin(), seq.end(),
          ostream_iterator<typename MULTI_INDEX_CNTR::value_type>(stm,"\n") ) ;
}

template< typename TAG, typename MULTI_INDEX_CNTR, typename KEY > inline
void erase_all_with_key( MULTI_INDEX_CNTR& multi_index_cntr, const KEY& key )
{
    typedef typename MULTI_INDEX_CNTR::template index<TAG>::type SEQ ;
    SEQ& seq = multi_index_cntr.get<TAG>() ;
    seq.erase( seq.lower_bound(key), seq.upper_bound(key) ) ; …

Either overload operator< for node or write a binary predicate to compare nodes. eg.

struct compare_cost
{
    bool operator() ( const node& a, const node& b ) const
    { return a.cost < b.cost ; }
};

If you just need a priority queue, just use std::priority_queue<> std::priority_queue< node, std::deque<node>, compare_cost > node_pq ; If you really need to keep a sorted sequence at all times (expensive), use a sequence container and the std::lower_bound algorithm.

void insert_ordered( std::list<node>& seq, const node& item )
{
    seq.insert( std::lower_bound( seq.begin(), seq.end(),
                                  item, compare_cost() ), item ) ;
}

Templating allows me to fill that vector with anything, not just classes derived from Node, which could screw things up. As such, this seems like a sloppy and potentially error-prone workaround.

Use SFINAE to restrict the types to just Node or derived classes of Node.

Also, in the example, AddValues() returns an int, whereas AddBetterValues() returns a double. My Node's Print() function is virtual, as that makes sense, but there will be cases that require me to define new functions for classes derived from the Node class which have no relationship to the existing ones: If I add a vector of values to the BetterNode class for example.

My main aim was just to reduce the amount of code I have to duplicate, by putting things common to all nodes in the base Node class, and likewise for the Base class.

For AddValues() to be polymorphic, the function must have the same name (but different implementations) in different classes. To make it (compile-time) polymorphic on the result type (int in one case and double in the other), have the node and its derived classes announce the type of the result.

An elided example (using boost::enable_if and boost::type_traits):

#include <boost/utility.hpp>
#include <boost/type_traits.hpp>
#include <iostream>

using boost::is_base_of ;
using boost::enable_if ;

struct node
{
    typedef int value_type ;

    explicit node( int i ) : v(i) {}

    value_type value() const { return v ; }

    int v ;
} ;

// generalization of base<T>; declared, not defined
template< typename T, …

Change std::stringstream& to std::ostream& in the overloaded operator and you would be ok.

class A 
{ 
public: 
	int num; 
	A(int x) : num(x) {}; 
	friend std::ostream& operator<<( std::ostream& stream, const A& someobject );
};

std::ostream& operator<<( std::ostream& stream, const A& someobject )
{
	stream << someobject.num;
	return stream;
};

Why is this so? Because in:

std::stringstream stream1;
stream1 << "Hello world! " << a1;

stream1 << "Hello world! " returns a std::ostream&

> That is the whole problem - I am not allowed to #include <vector> in any header file

You don't have to #include <vector> in any header file, you just have to declare std::vector<> in the header.

1. Declare std::vector<> in Myclass.h
2. #include <vector> (define std::vector<>) in MyClass.cc and MyDerivedClass.cc
3. provide a protected accessor to the vector for the benefit of derived class authors.

///////// MyClass.h ////////////

namespace std
{
    template < typename T > struct allocator ;
    template < typename T, typename A > class vector ;
}

class MyClass
{
    // ...

    private:
       struct impl ;
       impl* pimpl ; //consider using a std::tr1::unique_ptr instead of a raw pointer 

    protected:
       std::vector< double, std::allocator<double> >& vector() ;
};

///////// MyDerivedClass.h ////////////

#include "MyClass.h"

class MyDerivedClass : MyClass
{
    public:
        void DoSomething();
};

///////// MyClass.cc ////////////

#include "MyClass.h"
#include <vector>

struct MyClass::impl
{
   std::vector<double> v ;
   // ...
   // ...
};

// ...

// ...

std::vector< double, std::allocator<double> >& MyClass::vector()
{ return pimpl->v ; }

///////// MyDerivedClass.cc ////////////

#include "MyDerivedClass.h"
#include <vector>

void MyDerivedClass::DoSomething()
{
    vector().push_back(1.3);
}

You might want to have a look at this:
http://docs.google.com/viewer?a=v&q=cache:WfCn_2Gj4cgJ:h21007.www2.hp.com/portal/download/files/unprot/hpux/MakingConditionVariablesPerform.pdf+condition+variables+efficiency&hl=en&pid=bl&srcid=ADGEESgW2dGi3VpZ6x5BbxM-rdrtcwf_WDgt_P9iRGgcDSdGAZm-KyV6fgHrvyszOCi_Xi9zd6kbMysIjKCjdhkufrSoOZKFzFlki9i3Y3kSy743dc-iBJpqnXJa2nga5Nv-BzyBp6Yj&sig=AHIEtbSRCkYxw_TDCo2sb0HtxWKIHdcnKg

> The math problem is ((20+x) & 1234)=1000 as an example.

The equality may have no solution. For (A+x) & B == C, if any bit in B is 0 while the same bit in C is 1, there is no solution.
((20+x) & 1234)==1000 does not have a solution.

> needs to get both the highest possible value of x and the lowest possible value of x

For (A+x) & B == C, if there is a solution, the highest possible value for (A+x) is ~( B ^ C )
And the smallest possible value for (A+x) is C.

#include <iostream>
#include <limits>
#include <bitset>
#include <string>

int main()
{
  const unsigned long A = 20UL, B = 11247UL, C = 1000UL ;
  // find min and max values for x when ( (A+x) & B ) == C

  enum { NBITS = std::numeric_limits<unsigned long>::digits } ;
  std::bitset<NBITS> b(B), c(C) ;

  // if any bit in B is 0 when the corrosponding bit in C is 1,
  // there is no solution
  for( std::size_t i = 0 ; i < NBITS ; ++i )
      if( c[i] && !b[i] )
      {
          std::cerr << "( (" << A << "+x) & " << B << ") = " << C
                    << " has no solution.\n" ;
          return 1 ;
      }

  // if there is a solution, highest possible value of (A+x) is ~( B ^ C )
  std::bitset<NBITS> max_A_plus_x = ~( b ^ c ) …

> As far as I understand, each node in a list contains an element as well as pointers to both the following and preceding elements.
> Both an integer and a pointer to an integer are 4 bytes, so one would think that a node would use up 12 bytes,
> and therefore a list with 5M elements should use 60MB, not 118MB.

That is rather too simplistic a view.

When you allocate memory using a new, C++ guarantees that the memory pointed to will be correctly aligned for *any* complete object type whose size is no greater than the requested size.

The allocation function attempts to allocate the requested amount of storage. If it is successful, it shall return the address of the start of a block of storage whose length in bytes shall be at least as large as the requested size.
...[elided]...
The pointer returned shall be suitably aligned so that it can be converted to a pointer of any complete object type and then used to access the object or array in the storage allocated
...[elided]... - IS

For example, if the alignment requirement for an 8-byte double is 8 bytes, a 12-byte block would be aligned on an 8-byte boundary.

For performance reasons, every allocator maintains available chunks in bins, grouped by size. Because of alignment requirements, these chunk sizes are a multiple of 8 on 32-bit platforms. So a request for 12 bytes will consume …

> Is there any way of checking all elements in a queue without calling pop().

Yes, if you have used a std::queue<T> with the default std::deque<> for the second template parameter.

template< typename T > void foobar( const std::queue<T>& queue )
{
    typename std::deque<T>::const_pointer begin = &queue.front() ;
    typename std::deque<T>::const_pointer end = begin + queue.size() ;
    // [begin,end) iterates over elements of the queue. for example,
    std::copy( begin, end, std::ostream_iterator<T>( std::cout, "\n" ) ) ;
}

> can we pass arrays to functions

You couldn't pass arrays to functions in C, and couldn't pass them in C++98 either.

And you won't be able to do that in C++0x too. However, in C++0x you could pass a std::initializer_list<> to a function;
that is what someFunction({{1,2},{3,4},{5,6}}); attempts to do.

#include <iostream>
#include <vector>

template< typename SEQ > void foobar( const SEQ& s )
{
    for( auto iter = s.begin() ; iter != s.end() ; ++iter )
         std::cout << *iter << ' ' ;
    std::cout << '\n' ;
}

template< typename T > void foobar( const std::initializer_list<T>& a )
{
    for( auto iter = a.begin() ; iter != a.end() ; ++iter )
         std::cout << *iter + 10 << ' ' ;
    std::cout << '\n' ;
}

struct A { int a ; int b ; } ;

struct B { B( int x ) : b(x) {} private: int b ; } ;

struct C
{
  A aa[2] ;
  B bbb[3] ;
  operator int() const { return aa[0].a ; }
} ;

int main()
{
    foobar( { 0, 1, 2, 3, 4, 5 } ) ;

    std::vector<int> seq{ 0, 1, 2, 3, 4, 5 } ;
    foobar( seq ) ;

    foobar( { C{ { {1,2}, {3,4} }, {5,6,7} },
              C{ { {7,8}, {9,0} }, {1,2,3} },
              C{ { {4,5}, {6,7} }, {8,9,0} } } ) ;
}

> i am not understanding about ,Preprocessor,Compiler ,linker , Loader ,CPU

If you are just starting out, don't bother all that much about the gory details of what these different entities are right now. Just get a rough idea of what #include means, write the first hello world program, compile it and get it running, write a few more simple programs and so on. In due course of time, as you program, you would get to understand each of these.

Here is a simple tutorial: (simple, but just use it to get a rough idea; don't even try to digest all of it before you have written a few programs)
http://www.redantigua.com/c-compiler-behind-the-scenes-index.html

Something you could look at after a while: http://www.tenouk.com/ModuleW.html

AFAIK, the main advantage of nested functions in languages that have them is to provide support for closures. http://en.wikipedia.org/wiki/Closure_%28computer_science%29

Closures typically appear in languages that allow functions to be first-class values, in other words, such languages allow functions to be passed as arguments, returned from function calls, bound to variable names, etc., just like simpler types such as strings and integers. - Wiki

C++ already had function objects, which look like functions but are really first class values, they can be stored, mutated, passed as arguments and returned and bound to variable names. And therefore C++ already had a mechanism for supporting closures - several libraries eg. Boost::bind, Boost::spirit, Boost::phoenix do exploit closures extensively.

To define a function object, the programmer has to go outside the current scope, and these names cannot be declared close to their first (and often only) use. Lambda functions have been added in C++0x to increase the expressive power and ease of use of the language - anything that could be done using lambda functions could also be done using function objects, albeit in a more verbose manner.

In C, gcc has had an extension which provides limited support for nested functions and closures for quite some time now. http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html One can only call these functions (with closures) as long as the containing stack frame is alive:

If you try to call the nested function through its address after the containing function has exited, all hell will break …

Typically it doesn't, unless you force it to. For example:

> g++44 -Wall -std=c++98 -pedantic -Werror -fomit-frame-pointer -fstrict-aliasing -fconserve-stack  -fno-defer-pop

The frame of a function is transient, and the memory is reclaimed as soon as the function returns. It could also cause most debuggers to stumble.

> which kinds of constructors can be applied during compile time ?

None in C++98; though constructors can be elided as in the case of RV optimization.

Objects constructed via the the constexpr mechanism in C++0x.
http://www2.research.att.com/~bs/C++0xFAQ.html#constexpr

class Test{
     public:
      Test()=default;
      Test(char in1,char in2):char1(in1),char2(in2){}
      char char1;
     private:
      char char2;
    };
    Test obj={'a','b'};//invalid in c++0x

It is valid in C++0x.
The final proposal is here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2640.pdf