tags:

views:

246

answers:

8

Let's say I have an array of ints and I want to call a function to remove the smallest and largest values. By remove I mean that if my initial array was 7 elements in length, the new array has 5 elements. The order of the remaining elements does not matter. I've come up with some ways to do it, but I'm not sure which one is the C++ "way" of doing it, if that makes sense.

What I have now is that I use std::sort to sort my array and then I use a for loop to copy the results starting from the second element and stopping at the second-to last element into a new array with the appropriate size. How should I return the array though?

I can't return the newly created array because it's a local variable to the function. I could pass the new array as an argument to the function, but isn't that more of an older, C-style way of doing this? I could also use std::vector, but then I'd have to wrap the array in a vector and then unwrap it (the numbers need to remain in an array of ints). Seems like overkill, doesn't it?

I'm coming from a Python background and I just want to know what's the more appropriate way to do this in C++.

+7  A: 

Forget about arrays and use std::vector<int> instead.

using std::vector;

vector<int> WithoutHiLo(vector<int> orig)
{
     std::sort(orig.begin(), orig.end());
     vector<int> newVec = vector(orig.size());
     std:copy(&orig[1], &orig[orig.size()-1], &newVec[0]);
     return newVec;
}

UPDATE (per comment):

vector<int> WithoutHiLo(vector<int> orig)
{
     std::sort(orig.begin(), orig.end());
     return vector(&orig[1], &orig[orig.size()-1]);
}

If you really need an array for input:

vector<int> WithoutHiLo(int orig[], int size)
{
     std::sort(&orig[0], &orig[size]);
     vector<int> newVec = vector(size);
     std:copy(&orig[1], &orig[size-1], &newVec[0]);
     return newVec;
}
James Curran
Couldn't you use the vector begin/end iterator constructor to build it instead of using std::copy? Seems that would be better.
Zan Lynx
@Zan: Good point (I've been doing too much C# lately, and forget these things...)
James Curran
One other nitpicky thing I just noticed. Should throw a std::out_of_range or similar if size < 2. :)
Zan Lynx
@Zan: Yes, but some things should be left as an exercise for the student.. ;-)
James Curran
Why sort? That's unnecessarily inefficient when a linear search will do.
GMan
-1. "Forget about arrays" You know, all the benefits of std::vector aren't free - there is overhead and extra memory involved. And you don't need to sort. And you could modify vector in place without another one (swap minimum/maximum with last two values, then resize the vector with size() - 2). And you return vector by value, which may involve copy constructor. Bad advice, IMO, no matter how you look at it...
SigTerm
@SigTerm: I agree with everything but the last part. NRVO eliminates that overhead.
GMan
@SigTerm: You're wrong. std::vector isn't free- but there's std::array for the stack. No decent compiler will invoke the copy constructor here. While it's true that the function could perhaps be optimized further, fundamentally it's a far, far better function than taking an int orig[].
DeadMG
A: 

Using the STL vector to wrap your array of ints really doesn't make sense, as you said, and because you need to retain the array data structure, you might just as well not venture outside of that data structure.

Edit: Removed my non-answer from before and added sample code.

I've added some code below to demonstrate a way that doesn't involve the STL vector, but you're more than welcome to pursue that.

//Other stuff here...
int test[] = {5, 4, 3, 2, 1};
JunkFunc(test);
//whatever else your program needs to do afterward...

void CFlirPumpDlg::JunkFunc(int *arr)
{
int junkArr[] = {1, 2, 3, 4, 5};
    //The above array is just dummy data; removing the high/low would go here
memcpy(arr, &junkArr, sizeof(junkArr));
}
Rich Hoffman
Why would you use an array over a vector?
iconiK
How are pointers "the" way to do things in C++? I can do a lot of stuff without touching a pointer.
iconiK
C has no references; C++ has those.
iconiK
He didn't want to use a vector since he had a requirement of maintaining the array of ints. That's why you'd use that.
Rich Hoffman
You've got me on the references. I misspoke.
Rich Hoffman
Of course you can do things without pointers, but they are very powerful and very useful. I haven't touched a piece of C++ in years (since High School computer science) that doesn't use pointers.
Rich Hoffman
All edited and removed my non-answer.
Rich Hoffman
+1  A: 

This is more of STL type of way.

std::vector<int> vec; 
//populate your vector
vec.erase (max_element(vec.begin(), vec.end()) );
vec.erase (min_element(vec.begin(), vec.end()) );

But complexity is linear, so maybe not the best if faster removal is required.

DumbCoder
Kind of inefficient though. Or at least not as good as it could be.
Zan Lynx
@Zan, that is why I have mentioned the rider. And I would really love to know how it is inefficient compared to what i.e. not the copying around done by the vector and time complexity ? :)
DumbCoder
Because it scans the array twice and memmoves twice.
Zan Lynx
+1  A: 

Sorting isn't necessary. And what if the int array has either a duplicate min or max? Chopping off the first and last value after a sort won't solve the problem.

#include <vector>
#include <stdio.h>

void
rm_minmax(int* x, int sz, std::vector<int>& v) {
    int min = x[0];
    int max = x[0];
    int Sz = sz;

    while (sz) {
        int dv = x[sz-1];
        if (dv < min) min = dv;
        if (dv > max) max = dv;
        sz--;
    }

    for (int i=0; i < Sz; i++) {
        if (x[i] != min && x[i] != max) v.push_back(x[i]);
    }
}

int
main(int argc, char** argv) {
    int foo[] = { 5, 1, 33, 22, 54, 1, 44, 54 };
    int sz = sizeof(foo)/sizeof(int);
    std::vector<int> x;
    rm_minmax(foo, sz, x);
    sz = x.size();
    for (int i=0; i < sz; i++) printf("%d\n", x[i]);

}

xcramps
+8  A: 
Maciej Hehl
This seems like the most "c++" solution to me without using vector anyway
John Burton
+1 for not making it more complicated than it needs to be.
Jay
A: 

Part of your question denotes a lack of understanding of C++ array semantics - you can't 'remove' elements from C++ arrays(since they are raw memory). You can reallocate the memory to a smaller area; you can use a vector; you can copy to a smaller array.

But you can't do foo.delete_first() where foo is an array.

Here is my solution. It gives you a new array (allocated in the heap) with the characteristics you desire. It will handle duplicate maxes/mins. My solution has more lines of code than a STL solution and I would recommend using the STL if possible.

//Returns a new'd array of type T.
//Delete when done.
// Big-O = O(std::sort(len)) + len + O(cost-of-new)
template<typename T>
T* filter(T* t, int len)
{
  T* trimmed;
  std::sort(t[0], t[len-1]); //consider that this will not compile if T is not comparable

  //Here you could use a predicate approach, but let's write it out...
  int num_mins = 1; //t[0] is always min
  int num_maxes = 1; //t[len-1] is always max
  for(int i = 0; i < len; i++)
  { 
     if(t[i] == t[0])
       num_mins++;
     if(t[i] == t[len-1]) 
       num_maxes++;
  }

  trimmed = new T[len - (num_mins + num_maxes)];
  return trimmed
}
Paul Nathan
Why not use `std::vector`?
GMan
The OP seemed to prefer arrays. Also, I wasn't sure what the standard libraries did in the case of duplicates.
Paul Nathan
+3  A: 
GMan
+2  A: 

I got into solving this and the discussion with Moron in the question comments above spawned the following. The code is heavily modified but is based on this answer by Rayhan.

Compile it and call it with an input file of numbers like ./a.out < /tmp/numbers or pipe it some numbers like echo 1 5 2 10 -2 0 | ./a.out

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

template<class T, class U>
U copy_without_min_max(T in_begin, T in_end, U out)
{
    typedef typename std::iterator_traits<T>::value_type value_type;
    // min and max hold the min and max values found so far in the loop.
    value_type min, max;
    // small and big hold the values from the current pair being evaluated.
    value_type small, big;

    typename std::iterator_traits<T>::difference_type len = std::distance(in_begin, in_end);
    // in_stop is either the end of input or one less if length is odd.
    // This is needed so that in_begin will equal in_stop while advancing 2 at a time.
    T in_stop(in_end);
    T in_next(in_begin);
    ++in_next;
    // evaluate the first pair to find initial min,max values.
    if ( *in_begin < *in_next ){
        min = *in_begin;
        max = *in_next;
    } else {
        min = *in_next;
        max = *in_begin;
    }
    if ( len % 2 != 0 ) { // if len is odd
        --in_stop;
    }
    std::advance(in_begin, 2);

    // Advance two elements at a time tracking min and max as we go.
    // Whenever a previous min or max is evicted, output it to the destination.
    // Whenever a min or max is confirmed, output the element to the destination.
    while( in_begin != in_stop ) {
        in_next = in_begin;
        ++in_next;
        if ( *in_begin < *in_next ) { // one comparison
            small = *in_begin;
            big = *in_next;
        } else {
            small = *in_next;
            big = *in_begin;
        }
        if ( min > small ) { // one comparison
            *out++ = min;
            min = small;
        } else {
            *out++ = small;
        }
        if ( max < big ) { // one comparison
            *out++ = max;
            max = big;
        } else {
            *out++ = big;
        }
        std::advance(in_begin, 2);
    }
    // Special case for odd number of elements.
    // Output either the last element or min or max, depending.
    if ( in_begin != in_end ) {
        if ( *in_begin > min && *in_begin < max ) {
            *out++ = *in_begin++;
        } else if ( *in_begin < min ) {
            *out++ = min;
        } else if( *in_begin > max ) {
            *out++ = max;
        }
    }
    return out;
}

int main()
{
    std::vector<int> in;
    std::copy(
        std::istream_iterator<int>(std::cin),
        std::istream_iterator<int>(),
        std::back_inserter(in)
    );
    copy_without_min_max(
        in.begin(),
        in.end(),
        std::ostream_iterator<int>(std::cout, " ")
    );
    std::cout << std::endl;

    return 0;
}
Zan Lynx
For some reason, I'm really finding it hard to follow your algorithm. Would you mind commenting what each of the variables is used for?
Paul Nathan
@Paul: Added comments for you.
Zan Lynx