How do I remove the smallest and largest element in an array in a manner that's appropriate to C++?

Question

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++.

Answer 1

If the numbers had to remain in an array of ints and the order didn't matter, I would do it this way:

void MoveHiLoToEnd(int orig[], int size)
{
    int* last = orig + size - 1;
    int* maxp = std::max_element(orig, orig + size);
    std::iter_swap(maxp, last);
    int* minp = std::min_element(orig, orig + size - 1);
    std::iter_swap(minp, last - 1);

    //now the original array contains max and min elements moved.
    //to the end. You can ignore them or copy elements except
    //those last two to a new array, if really necessary.
}

The signature

int* MoveHiLoToEnd(int* begin, int* end);

is more in C++ library style and it could be changed to a template

template<typename ForwardIter>
ForwardIter RemoveHiLo(ForwardIter begin, ForwardIter end);

returning the iterator to the old min element (past the new truncated collection), but I doubt it's worth it. That would require different (less convenient I think) parameters in the call.

EDIT

Sorry template idea is bad. Things get complicated. You would have to require bidirectional iterator (which makes the template less universal than it could be with forward ones. for min and max_element forward is enough)

template<typename BidirectionalIterator>
BidirectionalIterator RemoveHiLo(BidirectionalIterator begin, BidirectionalIterator end);

or nonstandard input parameters, because you need iterator to the last element.

Answer 2

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;
}

Answer 3

There are two operations you need to perform: find the min and max, and then remove the min and max. By recognizing these steps and remember the single-responsibility principle, you maintain clean code.

The first operation is missing in C++03. As it stands, without making your own function the only way is to go through the range twice, one with min_element and max_element. This is algorithmically unnecessary.

C++0x recognizes this defect and adds minmax_element (and minmax). If you have a compiler that supports C++0x, just use std::minmax_element defined in <algorithm>. If not, use Boost's or steal Boost's/write your own.

We can now complete the first operation:

int array[] = {4, 7, 6, 5, 9, 4, 3, 1, 11};

// see footnote for begin and end
std::pair<int*, int*> mm = minmax_element(begin(array), end(array));

With pointers (or iterators) to the elements, we now remove them. With a statically-sized array, the typically solution is to move them to the end, ala:

// and take care your array has enough elements!
std::swap(*mm.first, end(array) - 2);
std::swap(*mm.second, end(array) - 1);

Then you just treat the array two elements shorter; this is O(1). Another solution, which maintains order, is to copy/shift all the elements down by one; this is O(N).

And that's it. You can wrap the above into some form of erase_minmax function.

_{*begin and end just make things a bit easier, they are:}

template <typename T, size_t N>
T* begin(T (&pArray)[N])
{
    return pArray;
}

template <typename T, size_t N>
T* end(T (&pArray)[N])
{
    return pArray + N;
}

Answer 4

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.

Answer 5

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]);

}

Answer 6

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;
}

Answer 7

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));
}

Answer 8

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
}