Implementing Library Algorithms

This is a discussion on Implementing Library Algorithms within the C++ Programming forums, part of the General Programming Boards category; hey guys..need some help with a project...im basically to implement the following 5 algorithms for a driver program... here are ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    46

    Implementing Library Algorithms

    hey guys..need some help with a project...im basically to implement the following 5 algorithms for a driver program...

    here are the algorithms:

    accumulate(b, e, t)

    equal(b, e, t)

    fill(b, e, t) - is to copies the value t into all the elements in the range [b, e).

    lexicographic_compare(b, e, b2, e2) - returns true if each element in the range [b, e) is less than the corresponding element in the range [b2, 2e), and false otherwise.

    min_element(b, e) - min_element(b, e) returns an iterator pointing to the smallest element in the range [b, e).

    this is what I have so far..

    Code:
    
    #ifndef GUARD_myalgorithm_h
    #define GUARD_myalgorithm_h
    
    template <class In, class Out>
    Out my_copy(In b, In e, Out d)
    {
    while (b != e)
    *d++ = *b++;
    return d;
    }
    
    template <class In, class Out>
    int my_accumulate(In b, In e, Out t)
    {
    int aaa = *t;
    while (b != e) {
    aaa = aaa + *b;
    b++;
    }
    return aaa;
    }
    
    template <class In>
    bool my_equal(In b, In e, In t)
    {
    
    return true;
    }
    
    template <class In>
    void my_fill(In b, In e, In t)
    {
    while (b != e) {
    *b = *t;
    b++;
    }
    }
    
    template <class In>
    bool my_lexicographic_compare(In b, In e, In b2, In e2)
    {
    while (b != e && b2 != e2) {
    for (b; b != e; b++)
      if (*b >= *b2)
    return false;
    if (*b < *b2)
    }
    
    template <class In>
    iter my_min_element(In b, In e)
    {
    return;
    }
    
    #endif
    can you guys go over it and see if there are mistakes, also i'm not sure how to do the min_element and equal functions so any pointers would help..thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Please indent your code.

    I suggest that you use the standard library names but enclose these function templates in your own namespace.

    EDIT:
    Consider that std::accumulate does not only work on ints.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    46
    ok i indented the code...and I also included the driver program - this should not be touched at all..

    Code:
    #ifndef GUARD_myalgorithm_h
    #define GUARD_myalgorithm_h
    
    template <class In, class Out>
    Out my_copy(In b, In e, Out d)
    {
        while (b != e) 
            *d++ = *b++;
        return d;
    }
    
    
    template <class In, class Out>
    int my_accumulate(In b, In e, Out t)
    {
        int aaa = *t;
        while (b != e) {
    	aaa = aaa + *b;
    	b++;
        }
        return aaa;
    }
    
    template <class In>
    bool my_equal(In b, In e, In t)
    {
    
        return true;
    }
    
    template <class In>
    void my_fill(In b, In e, In t)
    {
        while (b != e) {
    	*b = *t;
    	b++;
        }
    }
    
    template <class In>
    bool my_lexicographic_compare(In b, In e, In b2, In e2)
    {
        while (b != e && b2 != e2) {
    	for (b; b != e; b++)
    	    if (*b >= *b2)
    		return false;
    	if (*b < *b2)
    	    return true;
        }
    }
    template <class In>
    iter my_min_element(In b, In e)
    {
        return;
    }
    
    #endif
    program:

    Code:
    int main()
    {
        // set up some vector and list objects to use 
        int a[] = {1, 2, 3, 4};
        size_t size_a = sizeof(a)/sizeof(*a);
    
        int b[] = {5, 6, 7};
        size_t size_b = sizeof(b)/sizeof(*b);
    
        int c[] = {4, 3, 2, 3, 4};
        size_t size_c = sizeof(c)/sizeof(*c);
    
        vector<int> va(a, a + size_a);
        vector<int> vb(b, b + size_b);
        vector<int> vc(c, c + size_c);
    
        list<int> la(a, a + size_a);
        list<int> lb(b, b + size_b);
    
        // test my_accumulate 
        cout << "test my_accumulate:\n";
        cout << "  The sum of the elements in va is "
             << my_accumulate(va.begin(), va.end(), 0) << endl;
        cout << "  The sum of the elements in lb is "
             << my_accumulate(lb.begin(), lb.end(), 0) << endl;
    
        // test my_equal
        cout << "\ntest my_equal:\n";
        if (my_equal(va.begin(), va.end(), vb.begin()))
            cout << "  va and vb are equal\n";
        else
            cout << "  va and vb are not equal\n";
    
        if (my_equal(va.begin(), va.end(), va.begin()))
            cout << "  va equals itself\n";
        else
            cout << "  va and lb are not equal\n";
    
        // test my_fill
        cout << "\ntest my_fill:\n";
        cout << "  original va: " ;
        my_copy(va.begin(), va.end(), ostream_it(cout, " "));
        cout << endl;
    
        my_fill(va.begin(), va.end(), 30);
        cout << "  modified va: ";
        my_copy(va.begin(), va.end(), ostream_it(cout, " "));
        cout << endl;
    
        // test my_lexicographic_compare
        cout << "\ntest my_lexicographic_compare:\n";
    
        if (my_lexicographic_compare(la.begin(), la.end(), lb.begin(), lb.end()))
            cout << "  la is less than lb\n";
        else
            cout << "  la is not less than lb\n";
    
        if (my_lexicographic_compare(va.begin(), va.end(), vb.begin(), vb.end()))
            cout << "  va is less than vb\n";
        else
            cout << "  va is not less than vb\n";
    
        // test my_min_element
        cout << "\ntest my_min_element:\n";
        cout << "  the smallest element of vc is "
             << *my_min_element(vc.begin(), vc.end())
             << endl;
    
        return 0;
    
    }
    sorry i need to keep the my_(name) cuz the project description tells me to do it like that...

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    Download UnitTest++ and write some automated unit tests to verify your code.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Seconded, you definitely need some more unit tests!

    Nested loops for an algorithm that is O(n+m) in the standard library should ring warning bells, as should the fact that b2 is never incremened, as should the fact that not all code paths return a value.
    In short, delete my_lexicographic_compare and start it over. Also try and do it without using <=, >, or >=. You should only need < to compare the items.
    The SC++L source code can show you how it's done.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    46
    Quote Originally Posted by iMalc View Post
    Seconded, you definitely need some more unit tests!

    Nested loops for an algorithm that is O(n+m) in the standard library should ring warning bells, as should the fact that b2 is never incremened, as should the fact that not all code paths return a value.
    In short, delete my_lexicographic_compare and start it over. Also try and do it without using <=, >, or >=. You should only need < to compare the items.
    The SC++L source code can show you how it's done.
    hows this:

    Code:
    bool my_lexicographic_compare(In b, In e, In b2, In e2)
    
        while (b != e)
    	{
    	    if (*b2 < b || b2 == e2)
    		return false
    		else if (*b < *b2)
    		    return true;
    	    b++;
    	    b2++;
    	}
    return (b2 != e2);
    also i tried the my_equal:

    Code:
    {
        {
    	while (b != t)
    	    {
    		if (*b != *e)   
    		    return false;
    		++b; 
    		++e;
    	    }
    	return true;
        }
    Last edited by jewelz; 04-05-2009 at 02:01 PM.

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    46
    whats wrong with this piece of code? its giving me a compilation error saying "expected constructor, deconstructer, or type conversion before my_min_element"

    Code:
    template <class In>
    iter my_min_element(In b, In e)
    {
        iter lowest = b;
        if (b == e)
    	return e;
        while (++b != e)
    	if (*b < *lowest)
    	    lowest = b;
        return lowest;
    }
    for the lexicographical compare, its giving me an error for the second line: no match for 'operator< '
    Code:
    template <class In>
    bool my_lexicographic_compare(In b, In e, In b2, In e2)
    {
        while (b != e)
    	{
    	    if (*b2 < b || b2 == e2)
    		return false;
    		else if (*b < *b2)
    		    return true;
    	    b++;
    	    b2++;
    	}
        return (b2 != e2);
    }

  8. #8
    Registered User
    Join Date
    May 2008
    Posts
    15
    Code:
    template <class In>
    In my_min_element(In b, In e)
    {
        In lowest = b;
        if (b == e)
            return e;
        while (++b != e)
            if (*b < *lowest)
                lowest = b;
        return lowest;
    }
    
    template <class In>
    bool my_lexicographic_compare(In b, In e, In b2, In e2)
    {
        while (b != e)
        {
            if (*b2 < *b || b2 == e2)
                return false;
            else if (*b < *b2)
                return true;
            b++;
            b2++;
        }
        return (b2 != e2);
    }

  9. #9
    Registered User
    Join Date
    Jan 2009
    Posts
    46
    ok..im just getting a compilation error for just one algorithm

    Code:
    template <class In>
    void my_fill(In b, In e, In t)
    {
        while (b != e) 
           *b++ = t;
    }
    the compiler's complaint is referring to the line where my_fill is called in the main function, it is saying "there is no matching call to my_fill"
    Last edited by jewelz; 04-05-2009 at 09:23 PM.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by jewelz View Post
    ok..im just getting a compilation error for just one algorithm

    Code:
    template <class In>
    void my_fill(In b, In e, In t)
    {
        while (b != e) 
           *b++ = t;
    }
    the compiler's complaint is referring to the line where my_fill is called in the main function, it is saying "there is no matching call to my_fill"
    That's because you're telling it that b, e, and t are all the same type. Unless you were to try and fill the container with iterators to that type of container, then it isn't going to work.
    You need to either have two template types for that function, or use something like typename In::value_type t.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What's an import library?
    By chiefmonkey in forum C++ Programming
    Replies: 1
    Last Post: 06-19-2009, 05:00 PM
  2. Property Set Library (PSL) - Announcement
    By vultur_gryphus in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 05-29-2008, 06:04 AM
  3. Makefile for a library
    By sirmoreno in forum Linux Programming
    Replies: 5
    Last Post: 06-04-2006, 04:52 AM
  4. very weird .h problem
    By royuco77 in forum C++ Programming
    Replies: 1
    Last Post: 09-11-2005, 07:55 AM
  5. Implementing the MD5 encryption library in C
    By Weed4Me in forum C Programming
    Replies: 12
    Last Post: 11-09-2001, 02:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21