1

Assuming we have a sorted descending vector, like:

vector<int> array {26,  21,  13,  11,  8,  3,  2}.

I would like to insert a new and different element to the ones already present, so that descending sort of vector is kept.

Example flow:

  • I want to insert element 22, basically added at index 1, thus vector would be: 26, 22, 21, 13, 11, 8, 3, 2
  • I want to insert element 17, basically added at index 3, thus vector would be: 26, 22, 21, 17, 13, 11, 8, 3, 2
  • I want to insert element 1, basically added at a new index, thus vector would be: 26, 22, 21, 17, 13, 11, 8, 3, 2, 1
  • I want to insert element 43, basically added at index 0, thus vector would be: 43, 26, 22, 21,  17, 13, 11, 8, 3, 2, 1

A fast sample implementation in C++ would be:

#include<iostream> 
#include<vector>
#include <chrono>
using namespace std;
using namespace std::chrono;

int get_Index_Insert(const vector<int>& array, int lengthArray, int insertValue)
{
    int whereInsert = lengthArray;
    for (int i = 0; i < lengthArray; i++)
    {
        if (array[i] < insertValue)
        {
            whereInsert = i;
            break;
        }
    }
    return whereInsert;
}

int get_Index_Insert2(const vector<int>& array, int lengthArray, int insertValue)
{
    int whereInsert = lengthArray;

    // Break out early if these cases:
    if (lengthArray == 0 || (array[lengthArray - 1] > insertValue))
        return whereInsert;
    
    // Otherwise do your binary magic:
    int low = 0;
    int high = lengthArray - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (array[mid] > insertValue)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    whereInsert = high + 1;
    return whereInsert;
}

vector<int> insert_Value(const vector<int>& arrayInput, int insertValue)
{
    vector<int> arrayOutput;
    int lenghtArray = arrayInput.size();

    // At what index to add? 
    int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue);

    // Add it now: 
    for (int i = 0; i < whereInsert; i++)
        arrayOutput.push_back(arrayInput[i]);
    arrayOutput.push_back(insertValue);
    for (int i = whereInsert + 1; i < lenghtArray + 1; i++)
        arrayOutput.push_back(arrayInput[i - 1]);
    return arrayOutput;
}

vector<int> insert_Value2(const vector<int>& arrayInput, int insertValue)
{
    vector<int> arrayOutput;
    int lenghtArray = arrayInput.size();

    // At what index to add? 
    int whereInsert = get_Index_Insert2(arrayInput, lenghtArray, insertValue);

    // Add it now: 
    for (int i = 0; i < whereInsert; i++)
        arrayOutput.push_back(arrayInput[i]);
    arrayOutput.push_back(insertValue);
    for (int i = whereInsert + 1; i < lenghtArray + 1; i++)
        arrayOutput.push_back(arrayInput[i - 1]);
    return arrayOutput;
}

int main()
{
    {
        // START TIME
        auto start = high_resolution_clock::now();
        vector<int> array{ 26,  21,  13,  11,  8,  3,  2 };
        array = insert_Value(array, 22);
        array = insert_Value(array, 17);
        array = insert_Value(array, 1);
        array = insert_Value(array, 43);
        auto stop = high_resolution_clock::now();
        // END TIME

        // Show time:
        auto duration = duration_cast<microseconds>(stop - start);
        cout << "Time taken by function 1, linear search: " << duration.count() << " microseconds" << endl;

        for (int i = 0; i < array.size(); i++)
            cout << array[i] << " ";

        cout << endl;
    }

    {
        // START TIME
        auto start = high_resolution_clock::now();
        vector<int> array{ 26,  21,  13,  11,  8,  3,  2 };
        array = insert_Value2(array, 22);
        array = insert_Value2(array, 17);
        array = insert_Value2(array, 1);
        array = insert_Value2(array, 43);   
        auto stop = high_resolution_clock::now();
        // END TIME

        // Show time:
        auto duration = duration_cast<microseconds>(stop - start);
        cout << "Time taken by function 2, binary search: " << duration.count() << " microseconds" << endl;

        for (int i = 0; i < array.size(); i++)
            cout << array[i] << " ";

        cout << endl;
    }

    cout << endl << endl << endl;
    return 0;
}

Other info that may help in deciding recommended method:

  • I cannot use anything else than class vector from STL; (only using it as a holder + it's push_back function, nothing else as helper function from it);
  • I will not have more than a 1000 elements ever in the vector.

Is there any way better to do it than above? in less complexity involved? Any source material I may have missed and that might help is very much appreciated also.

EDIT: After some more investigations and using binary search method while seeking index position for actual element insertion (thanks to the debates from comments), edited my above sample a bit, testing execution time of a "get_Index_Insert2(...) function using early returns and binary search.

Times received (microseconds), after 3 runs:

Time taken by function 1, linear search: 60 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 33 microseconds
43 26 22 21 17 13 11 8 3 2 1

Time taken by function 1, linear search: 61 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 34 microseconds
43 26 22 21 17 13 11 8 3 2 1

Time taken by function 1, linear search: 61 microseconds
43 26 22 21 17 13 11 8 3 2 1
Time taken by function 2, binary search: 34 microseconds
43 26 22 21 17 13 11 8 3 2 1
neaAlex
  • 206
  • 3
  • 15
  • Another Possible Approach (Assuming this Vector behaves similar to an array) would be that I would just add an element to the array and then use one of them sorting algorithms like bubble sort. (This Method Maybe Slow depending on the no of elements) – mrtechtroid Apr 05 '22 at 08:06
  • 3
    @mrtechtroid You’ll definitely want to use insertion sort instead of bubble sort. It first this use-case perfectly — the hint is in the name. ;-) – Konrad Rudolph Apr 05 '22 at 08:07
  • 3
    Both of your functions are much less efficient than necessary. If you were using the C++ standard library, this would be a two-liner: call [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound) (with an appropriate comparator, i.e. `std::greater<>`) to find the insertion position, and then use the `insert` method to insert the new value. Now you say you can’t use the standard library, so your goal should be to rewrite `std::lower_bound` from scratch, which is fairly straightforward using binary search. Or, as mentioned, write your own insertion sort. – Konrad Rudolph Apr 05 '22 at 08:12
  • @KonradRudolph hey! searched a bit about binary insertion sort: https://www.geeksforgeeks.org/binary-insertion-sort/ so this would look like the one I need? – neaAlex Apr 05 '22 at 08:18
  • @neaAlex [This answer](https://stackoverflow.com/a/24650627/2610810) has a better implementation of insertion sort – Caleth Apr 05 '22 at 08:21
  • For your insert sorted, you'd just be doing one step having `push_back`ed the element to insert – Caleth Apr 05 '22 at 08:27
  • @KonradRudolph added a binary search method for index position at least; I think the complexity is reduced a bit with that one, though will check more when possible. – neaAlex Apr 15 '22 at 15:55

3 Answers3

1

Instead of creating a new vector you can use the insert function to put the new value into the existing list at the desired index. See https://en.cppreference.com/w/cpp/container/vector/insert

void insert_Value(const vector<int>& arrayInput, int insertValue) 
{ 
    int lenghtArray = arrayInput.size(); 
    // At what index to add? 
    int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue);
    arrayInput.insert(whereInsert, insertValue);
}
Torben Schramme
  • 2,104
  • 1
  • 16
  • 28
  • In this case `arrayInput` should not be a `const vector&`. – mch Apr 05 '22 at 08:12
  • might want to take the `const` off `arrayInput` – Caleth Apr 05 '22 at 08:14
  • Interesting function, indeed. Still, what if I will go for a more on-hands approach implementation, rather than using implemented insertions already? Would like to review the insert approach in-depth. Will edit a bit the condition section of the question. Should have been specific. – neaAlex Apr 05 '22 at 08:14
  • @neaAlex it depends what you want to achieve. If you're learning and want to understand in-depth how things work, then it would be better not to use ``vector`` at all, but write your own data structure. But when you want performance and well-tested solid functions, always try to use the available methods. There is no direct way to manipulate the internal data structures of ``vector`` to protect yourself from breaking it accidently. So either you can use dedicated methodes like ``insert`` or you write your own method that does the same, but with worse performance. – Torben Schramme Apr 05 '22 at 16:41
  • @TorbenSchramme agree; scope would be to learn; vector used it merely as a simple holder; putting aside my proposed conditions, learned a lot about STL and some of its helper functions from this post's answers, from all of you; thank you! – neaAlex Apr 06 '22 at 06:13
1
#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
std::vector<int>::const_iterator get_Index_Insert(const vector<int>& array ,int insertValue) {
    return std::find_if(array.cbegin(),array.cend(),[insertValue](int aValue) { return aValue < insertValue;});
 }

void insert_Value(vector<int>& arrayInput, int insertValue, std::vector<int>::const_iterator aIt)
{
arrayInput.insert(aIt,insertValue);
}
int main()
{
    vector<int> array{26, 21, 13, 11, 8, 3, 2 };
    auto myIt = get_Index_Insert(array,22);
    insert_Value(array,22,myIt);
    for (int i = 0; i < array.size(); i++)
        cout << array[i] << " ";
    cout << endl << endl << endl;
    return 0;
}

This is only an idea, then it can be enhanced

GTA
  • 253
  • 4
  • 13
  • Why `std::find_if` instead of `std::find`? Anyway, OP specified that they can’t use the standard library. – Konrad Rudolph Apr 05 '22 at 08:22
  • Sorry I not read with attention the conditions. Yes because we need to find a simple value also find is ok ... also better because std::vector has a member function find ... I used find_if only for routine because find_if permits to specify a more complex logic – GTA Apr 05 '22 at 08:27
1

You don't need to pass the size of the vector, std::vector already have a member function size().

I think you overcomplicated things. You just have to iterate over the vector and compare each element with the value you want to insert. If the comparison evaluates to false, then you found where to insert the new element.

You may implement the function the following way:

template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
    bool inserted(false);
    for(typename std::vector<val_t>::iterator it = vec.begin(); !inserted && (it != vec.end()); ++it)
    {
        if(!comp(*it, val))
        {
            vec.insert(it, val);
            inserted = true;
        }
    }
    if(!inserted)
        vec.push_back(val);
}

It takes the vector, the value to instert and the comparison function you want.

For your use case, it may be used like this:

int main()
{
    std::vector<int> v {26,  21,  13,  11,  8,  3,  2};

    insert_ordered(v, 22, std::greater<int>());
    insert_ordered(v, 17, std::greater<int>());
    insert_ordered(v, 1, std::greater<int>());
    insert_ordered(v, 43, std::greater<int>());

    for(const int & i : v)
        std::cout << i << ' ';

    return 0;
}

Output:

43 26 22 21 17 13 11 8 3 2 1

Live example

If, for some reason, you can't use std::greater, you can define your own comparator like this:

auto desc_comp = [](const int & lhs, const int & rhs)
{
    return lhs > rhs;
};

And use it like this:

insert_ordered(v, 22, desc_comp);

Edit:

If you don't mind having several exit points in the function, it can be simplified as:

template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
    for(typename std::vector<val_t>::iterator it = vec.begin(); it != vec.end(); ++it)
    {
        if(!comp(*it, val))
        {
            vec.insert(it, val);
            return;
        }
    }
    vec.push_back(val);
}
Fareanor
  • 5,900
  • 2
  • 11
  • 37
  • 1
    Speaking of overcomplicating things, you don’t need the `inserted` variable. Just early-exit after inserting. And of course this solution is still less efficient than using binary search to find the insertion position. – Konrad Rudolph Apr 05 '22 at 08:24
  • @KonradRudolph Yes of course, I could directly return instead of using the `inserted` flag but it's a habit I have to prefer having a single exit point :) – Fareanor Apr 05 '22 at 08:26
  • 1
    It’s a fairly bad habit, you should break it sooner rather than later: single-exit often makes code more complex (e.g. here) and has no advantage in languages like C++. – Konrad Rudolph Apr 05 '22 at 08:29
  • @KonradRudolph I edited the answer accordingly. I understand your point but I still tend to believe that having a single exit point makes code more understandable/maintainable (but I agree that it makes it a bit more complex). – Fareanor Apr 05 '22 at 08:31
  • By the way, in the first version of the function, it also exits when the element is inserted (look at the end condition), so the _"sooner rather than later"_ part is not really relevant here IMHO. – Fareanor Apr 05 '22 at 08:41
  • @Fareanor comprehensive response using various STL approaches; thanks a lot and do have an up-vote! will investigate still the binary insertion sort method (as suggested by Konrad in main post comments) and try to implement from scratch bits from it – neaAlex Apr 05 '22 at 08:42
  • @neaAlex You're welcome ! :) If you really want to implement your own `lower_bound` function as suggested in comments, you may be interested to have a look at the reference about [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound). There is proposed a possible implementation of the function. That being said, I'm not sure the performances difference is significant (or if it does worth the effort). Anyway, if the performances of my solution are not enough for you, I hope this can help you. – Fareanor Apr 05 '22 at 08:47
  • @Fareanor I meant that you should break *the bad habit of using single-exit* sooner rather than later, not that you should break the loop sooner. — Surely you can see that your first code is *vastly* (and gratuitously) more complex than the second code? Complexity can be objectively quantified, this isn’t just a matter of opinion. – Konrad Rudolph Apr 05 '22 at 08:55
  • @KonradRudolph Oh I did not understand ! My bad. But yes, I agree it makes things a bit more complicated ("_vastly_" seems a bit exaggerated ^^), but shorter code doesn't necessarily mean clearer code. For maintainability purposes, I really do prefer to have a single exit point than having to check everywhere where the function may or may not exit (but in that specific case, I admit it's not really relevant though). – Fareanor Apr 05 '22 at 09:00
  • _"Complexity can be objectively quantified, this isn’t just a matter of opinion."_ Indeed. But in this case, it somewhat is. For example, the binary search will perform worse if the element we want to insert is at the beginning of the vector. I know O(log(n)) is better than O(n). But in this case, it is O(n) at worse case. I was not exposing an opinion, I was just stating that the performance difference from the improvement may not worth the effort (depending on the OP's requirements of course). It is up to the OP to know what meets his/her needs. – Fareanor Apr 05 '22 at 09:07