CODEWITHSUNDEEP
c++vector
Grant H.
Grant H.

Reputation: 3717

Do I need to sort a vector<int> if they were added to the vector in order?

Do I need to sort my vector if the items were read in from a file sequentially that was already sorted? I don't want to incur the performance penalty if it's unnecessary. For reference, this is what I'm using to build it, and each item is in order as it's being read in.

Edited after @dribeas' comment

std::vector<int> split(const std::string &s, char delim) {
    std::vector<int> elems;
    std::stringstream ss(s);
    std::string item;
    while(std::getline(ss, item, delim)) {
        elems.push_back(static_cast<int>(atoi(item.c_str())));
    }
    return elems;
}

Upvotes: 3

Views: 416

Answers (3)

paxdiablo
paxdiablo

Reputation: 881163

Provided the vector was empty when you started (that's not clear from your original sample code) and the items were added in the order you want, no, you do not need to sort, because push_back pushes items on to the back (end) of the vector:

Adds a new element at the end of the vector, after its current last element.

Following your edit, the possibility of the list being non-empty to start with is now gone. This section still stands for the original question where that was a possibility.

If the vector wasn't empty to begin with, the stuff that was in there may be out of order even if you added the new stuff in order.

If you want to ensure it's sorted, but avoid sorting unless absolutely necessary, you can do that as a post-step after the addition, something like:

std::vector<int> &split (const std::string &s, char sep, std::vector<int> &vec)
{
    std::stringstream ss (s);
    std::string item;
    while (std::getline (ss, item, sep))
        vec.push_back (static_cast<int> (atoi (item.c_str ())));

    bool sorted = true;
    for (int i = vec.size() - 1; (i > 0) && sorted; i--)
        sorted = (vec[i] >= vec[i-1]);
    if (!sorted) {
        // Sort it here.
    }

    return vec;
}

This will be a relatively fast scan of the elements to ascertain whether or not they're sorted (and only until it finds the first out of order group).

If not sorted, it will sort them with your favourite sort algorithm (batteries not included), otherwise it will just return.

However, it may still be best to assume that the data may not arrive in the order you want. You can still use a similar method to only sort when necessary, with something like:

std::vector<int> split (const std::string &s, char delim) {
    std::vector<int> elems;
    std::stringstream ss (s);
    std::string item;
    int lastOne = std::numeric_limits<int>::min ();
    bool isSorted = true;

    while (std::getline(ss, item, delim)) {
        int thisOne = atoi (item.c_str ());
        if (thisOne < lastOne) isSorted = false;
        elems.push_back (static_cast<int> (thisOne));
        lastOne = thisOne;
    }

    if (!isSorted) {
        // Sort it here.
    }

    return elems;
}

In that case, each element is checked against the last one to ensure it's at least as large. If not, the vector is flagged for sorting.

With that, there's a minimal cost in checking but it gives you the ability to handle data that doesn't follow the rules.

Upvotes: 3

Chris Subagio
Chris Subagio

Reputation: 6329

If you're asking whether a std::vector will preserve the order in which you push items onto it, then yes. That is very much part of the contract.

Upvotes: 4

Borealid
Borealid

Reputation: 98459

No, you don't need to sort the vector. push_back adds elements to the end explicitly.

Note that your API is taking in elems and also returning it (by reference). What happens to any content the vector already contains?

Upvotes: 5

Related Questions