C++ question: How many ints in my array?

Discussion in 'OT Technology' started by Joe_Cool, Oct 9, 2004.

  1. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,496
    Likes Received:
    616
    I'm working on a program with multiple source files to sort a large array of integers. The size of the array is #defined at the beginning of the main file, but the member functions are in another file. I don't want to have to #define it in both places or give my functions (or the class) an extra parameter for the array size - I'd rather have a way to calculate how many elements are in the array.

    Basically, I want in c++ what a.length does in java.

    Is this possible?
     
  2. Shibboleth

    Shibboleth teh mad Plato skillz

    Joined:
    Sep 29, 2004
    Messages:
    1,769
    Likes Received:
    0
    yes, look in to the STL (standard template library) specifically vectors.
    but you just should put the define (or better yet, use a const int) in a header file, it's common practice.
     
    Last edited: Oct 9, 2004
  3. Penguin Man

    Penguin Man Protect Your Digital Liberties

    Joined:
    Apr 27, 2002
    Messages:
    21,696
    Likes Received:
    0
    Location:
    Edmonton, AB
    Yep, a const int would be the proper way to do it really. #defines are pretty messy, they should only really be used for values that depend on the compiler (for example, if the number is different for each operating system or something).
     
  4. SL1200MK4

    SL1200MK4 New Member

    Joined:
    Sep 27, 2003
    Messages:
    1,552
    Likes Received:
    0
    Well if it's for assignment then I guess const int will be the way to go. I am assuming that you need to write your own search algorithm (quick sort / heap sort... whatever)

    However if you just want to be able to sort a large array of integers in the array, then this had been implemented in generic algorithms, which is fairly efficient.

    The "array" in C++ is very primitive. Which means that you don't get all the goodies like .length() in JAVA. There is something to adjust to. I would recommand that you get comfortable with the STL vector class...

    BUT!!! if this is for production enviroment, be careful on how you use the vector class. There are two "attributes" in java terms... size and capacity. The size if basically the length of the array. So instead of using .length(), you use .size().

    The capacity is tricky. It gives you the total amount of memories reserved for storeing the instances. So if capacity is 100, then memory space to store 100 instances (int in your case) is reserved or allocated. If you work with large amount of memory, then it''s not a bad idea to ask the vector to allocate 10000 or however amount of memory that you need. This will make inserting into the vector faster. Because it doesn't have to reallocate memory after.

    If I remember correctly, it is implemted like an arrya. So evertime when it has to increase the capacity of the vector it will need to bascially allocate more memory, copy the content, deallocate the old portion.
     
  5. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,496
    Likes Received:
    616
    It's a school assignment - just a basic sort class with 7 different sort member functions (bubble, bi-directional bubble, insertion, quick, selection, shaker, shell) and the instructor said to #define the size of the array and the range of the ints to be sorted and a timer class to tell how long each sort takes.

    And I just had to port the sort routines from java, didn't have to write them from a specification.

    The prog is done, but I'm messing around with it, counting swaps and comparisons, etc just to entertain myself, and to do that I'm changing the number of ints over and over and over. It's a pain in the ass to change it in one file, then open the other file and change it there, compile, run, change it again, go back to the original file and make whatever changes I need, etc.

    So I guess I'll check out vectors. Thanks. :)
     
  6. Shibboleth

    Shibboleth teh mad Plato skillz

    Joined:
    Sep 29, 2004
    Messages:
    1,769
    Likes Received:
    0
    vectors are sweet. You can use an STL sort algorithm on them, which in my tests is very close to a full blown customly implemented radix sort.
     
  7. SL1200MK4

    SL1200MK4 New Member

    Joined:
    Sep 27, 2003
    Messages:
    1,552
    Likes Received:
    0
    There a very good book on STL and generic algorithms.

    STL Tutorial and Reference Guid 2nd Edition by David R. Musser, Gillmer J. Derge, and Atul Saini. Published by Addison-Wesley.

    Generic algorithm provides 3 different type of sorting actually, each have different space efficiency and time efficiency along with other different properties, such as relative position of equivalent elements.

    Those are specification of the API functions, the implementation could vary. However as stated in the book, sort is intended to be implemented as quicksort, partial_sort goes with heapsort, and stable_sort with mergesort.

    In short, you might not get the most efficient implementation that's opimized for your application, but they do have O(n log n). With sort having worse case of O(n^2). Which is the bound for comparision based sorting.

    STL is definately something to take advantage of in C++.

    :bowdown:
     
  8. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    As long as the array size is declared, not a dynamically allocated array created by the new operator, you can use sizeof() to get the array size in bytes. Then simply divide by the array element size to get the number of elements.

    int array[100];

    sizeof(array) will return 400

    sizeof(array)/sizeof(int) will return 100
     
  9. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    But, the correct solution to your problem is to put global #defines in a seperate header (.h) file. Then #include that file wherever those #defines are needed.
     
  10. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,496
    Likes Received:
    616
    This is what I had tried originally, but it's returning 1 no matter the size of the array.

    Here's what I have:
    main.cpp creates a sort object s, declares the array a and fills it with random numbers, and calls sort->bubble(a).

    in sort.cpp, I have a private member function called int len(unsigned int * a).
    It gets passed an array * a and returns sizeof(array)/sizeof(unsigned int).
    each sort subroutine is a public member function of class sort, and calls len() whenever it's needed, passing a pointer to a (or a reference, I've tried both ways) whenever it's needed.

    When I do it like this, it always returns 1, and my sort functions just run 1 iteration and quit.

    I assume it's something to do with the fact that it's a pointer, but I don't know what to do to dereference it to get the size of the full array.

    :hs:

    So to get it to work well enough to turn in, I changed len() to return a #defined value temporarily, in anticipation of fixing it the way I want it. But I hate having it this way. :dunno:
     
  11. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Sizeof doesn't work with pointers that point to an array, it requires a genuine array name. It's probably not a good design choice to have your sort object try to figure out the size of an array that's passed to it. It's better to have the caller that maintains the array to explicitly tell the sort object the array size. Something like sort->bubble(a, sizeof(a)/sizeof(int));
     
  12. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,496
    Likes Received:
    616
    Boo. That sucks. :hs:
     

Share This Page