Trying to Remove Vector Element

[smitsky]

Hi. I'm trying to implement a disk scheduling algorithm using a vector. I am able to find the smallest element of the vector with my findMin() function:

int computer::findMin( vector<int> v )
{
    int minIndex = 0;

    for( int i = 1; i < v.size( ); i++ )
        if( v[ minIndex ] > v[ i ] )
            minIndex = i;
    return v[ minIndex ];
}

...and I am able to find what position in the vector the smallest element is in with my findPos() function:

int computer::findPos( vector<int> v )
{
    int minIndex = 0;

    for( int i = 1; i < v.size( ); i++ )
        if( v[ minIndex ] > v[ i ] )
            minIndex = i;
    return minIndex;
}

...but I'm not sure how to find the next successive smallest elements.

Any help/ideas would be appreciated. Thanks.

[mike_2000_17]

First of all, if you are just inspecting the vector, you should pass it by const-reference instead of by value, to avoid an unnecessary copy, i.e., use this:

int computer::findMin( const vector<int>& v )
{
    int minIndex = 0;
    for( int i = 1; i < v.size( ); i++ )
        if( v[ minIndex ] > v[ i ] )
            minIndex = i;
    return v[ minIndex ];
}

(and the same for findPos())

As for finding the next smallest element, well, that depends on what exactly you want to do. Do you want to find the N smallest elements? Or do you want to just find the second smallest element?

If you know the smallest element, you can always find the next smallest element by passing it to the function and finding the minimum that is greater than that last minimum value. Here is a good start (not completely correct):

int computer::findMin( const vector<int>& v, int lastMinValue )
{
    int minIndex = 0;
    for( int i = 1; i < v.size( ); i++ )
        if( ( v[ i ] > lastMinValue ) &&
            ( v[ minIndex ] > v[ i ] ) )
            minIndex = i;
    return v[ minIndex ];
}

If you want to find the N smallest elements in one pass, you need to keep a record of those N elements as you go along. Typically, you would put the N first elements into the record, and then, each time you find an element that is less than the greatest of those N elements, you remove the greatest element and add the new element to that record. This is normally done with a priority-queue (or heap).

[smitsky]

Thanks Mike.

I think I'm trying to find each successive smallest element. I'm trying to get a clear picture of what I'm supposed to do. I've never tried to implement scheduling for disk queues, and I'm trying to figure out the approach.

I'm studying operating systems, and am kind of lost.

[smitsky]

I think I can use a vector for what I'm trying to do, but I may very well need a heap.

[vijayan121]

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

int main()
{
    std::vector<int> seq { 4, 9, 2, 8, 1, 3, 0, 6, 7, 5} ;
    const auto begin = std::begin(seq) ;
    const auto end = std::end(seq) ;

    std::cout << "smallest element: " 
              << *std::min_element( begin, end ) << '\n' ; 

    std::cout << "position of smallest element: " 
              << std::min_element( begin, end ) - begin << '\n' ; 

    constexpr std::size_t n = 5 ;
    std::nth_element( begin, begin+n,  end ) ;
    std::cout << "the smallest " << n << " elements are: " ;
    for( std::size_t i = 0 ; i < n ; ++i ) 
        std::cout << seq[i] << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/b55083d3ad0bec4c

[smitsky]

Thanks, but this code does not compile and I don't understand it.

[Alberto Bucur]

Hi,
Why dont try to sort your vector in ascending mode ?
After that the first element is the smallest, the second is the next smallest.

[mike_2000_17]

Why dont try to sort your vector in ascending mode ?
After that the first element is the smallest, the second is the next smallest.

Because sorting an entire array just to obtain the N smallest elements is very wasteful. And especially in the context that the OP seems to be referring to (file-system indexing), that vector is probably very dynamic, and probably much bigger than the number of N smallest elements required. Keeping this vector sorted at all times would be very bad.

One solution, as presented by vijayan121, is to use the nth_element algorithm which partitions the vector such that the value that would appear at the Nth position in a sorted vector will appear at the Nth position in the partition and all the lesser elements will come before it, and all the greater elements after it. Because this does not sort the entire vector, i.e. the two sub-sequences on either side of the Nth element are not sorted, this operation can be done in linear-time O(S) (if S is total size), which is much better than sorting, which is O(S log(S)). If you want the N smallest elements to be sorted, you can sort that sub-sequence after you call nth_element.

The reason that vijayan121's code does not compile for you is probably because it uses C++11 features, which your compiler may or may not support, and are not turned on by default (you need the -std=c++11 option). Here is a C++98 version:

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

int main()
{
    int seq[] = { 4, 9, 2, 8, 1, 3, 0, 6, 7, 5};
    int* begin = seq;
    int* end   = seq + sizeof(seq) / sizeof(int);

    std::cout << "smallest element: " 
              << *std::min_element( begin, end ) << '\n' ; 

    std::cout << "position of smallest element: " 
              << std::min_element( begin, end ) - begin << '\n' ; 

    const std::size_t n = 5;

    // Partition the array to get the first 5 elements:
    std::nth_element( begin, begin + n, end);
    std::cout << "the smallest " << n << " elements are: " ;
    for( std::size_t i = 0 ; i < n ; ++i ) 
        std::cout << seq[i] << ' ' ;

    // Sort the first 5 elements:
    std::sort( begin, begin + n );
    std::cout << "the smallest " << n << " elements in sorted order are: " ;
    for( std::size_t i = 0 ; i < n ; ++i ) 
        std::cout << seq[i] << ' ' ;

    std::cout << '\n' ;
}

The other solution that I was talking about earlier relies on using the make_heap, pop_heap and push_heap functions. This is more appropriate if you want to dynamically maintain a vector that you can frequently query for the next smallest number. The only guarantee with a heap is that the largest (or smallest) element will be placed at the start of the vector, and if you "pop" it, the next largest (or smallest) element will be moved to take its place. This may sound like a sorted vector, but it's not, because the requirements are much weaker, because a sorted vector would require that all elements are in the correct order at all times, while a heap (or priority-queue) only require the first element to be maintained. This leads to significant performance improvements when you are frequently adding any elements and removing largest (or smallest) elements from the vector because the heap structure is a lot cheaper to maintain than an entirely sorted vector. I don't necessarily want to provide an example for this, because this depends a lot more on the practical context in which you need to use it, which is something that the OP simply hasn't provided enough details about (all we know is that it relates to file-systems, that's not enough).