Is Begin() == End() for Any Empty() Vector

Is begin() == end() for any empty() vector?

Yes, that's what the standard requires it to be for empty() for any container.

§ 23.2.1 Table 96 of the C++11 standard says:

 +----------+---------------+----------------------+
 |Expression|  Return Type  | Operational Semantics|
 |----------|---------------|----------------------|
 |a.empty() |Convertible    |a.begin() == a.end()  |
 |          |to bool        |                      |
 |          |               |                      |
 +-------------------------------------------------+

Does std::find on empty vector cause undefined behaviour?

The return value of find when the element is not present is the end iterator:

[alg.find] (emphasis mine):

Let E be:

• *i == value for find,
• [...]

Returns: The first iterator i in the range [first, last) for which E is true. Returns last if no such iterator is found.

This includes the element not being present because the range is empty.

Using insert() on empty std::vector when sorting

What you are doing works fine. However it is not the most efficient way. Using std::find doesn't take advantage of the fact that the data in the vector is sorted, it visits every element until if finds the correct one.

Instead of std::find you can use std::lower_bound from the beginning because that will find your element if it exists and if not, it will find the correct place to insert a new one.

Also it will use a binary search so it will be leaps and bounds faster than std::find. Also you don't end up finding the insertion/replacemt point twice.

Something like this should do:

void insert_or_replace(std::vector<Book>& books, Book const& b)
{
    std::vector<Book>::iterator it;

    it = std::lower_bound(books.begin(), books.end(), b);

    if(it != books.end() && *it == b)
        *it = b;
    else
        books.insert(it, b);
}

Is it legal to use the insert member function to insert a range into an empty vector?

Yes, it's perfectly legal. From cppreference:

Causes reallocation if the new size() is greater than the old capacity(). If the new size() is greater than capacity(),

---

when myvec is empty, is the above different from the following?

No, because when a vector is empty, vector::begin() == vector::end(). So they are both same.

Difference between std::vector::empty and std::empty

Difference between std::vector::empty and std::empty

The difference between Container::empty member function and std::empty free function (template) is the same as difference between Container::size,std::size, Container::data,std::data, Container::begin,std::begin and Container::end,std::end.

In all of these cases for any standard container, the free function (such as std::empty) simply calls the corresponding member function. The purpose for the existence of the free function is to provide a uniform interface between containers (and also std::initializer_list) and arrays. Arrays cannot have member functions like the class templates can have, so they have specialised overload for these free functions.

If you are writing code with a templated container type, then you should be using the free function in order to be able to support array as the templated type. If the type isn't templated, then there is no difference between the choice of using member function or the free function other than the convenience of potential refactoring into a template (or just plain array).

What iterator does vector::erase() return if passed an empty range?

This is specified in [sequence.reqmts]:

The iterator returned by a.erase(q1, q2) points to the element pointed to by q2 prior to any elements being erased. If no such element exists, a.end() is returned.

_{(Note: I linked the C++17 final working draft, but this wording exists since at least C++98, see comment by @Peter)}

So we should have it1 == v.begin() and it2 == v.end().

Live test:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v{1, 2, 3, 4};
    auto it1 = v.erase(v.begin(), v.begin());
    auto it2 = v.erase(v.end(), v.end());
    std::cout << std::distance(v.begin(), it1) << std::endl;
    std::cout << std::distance(v.begin(), it2) << std::endl;
}

Output:

0
4

To clarify this behavior, I have updated the cppreference documentation, which is now:

iterator erase( const_iterator pos );
iterator erase( const_iterator first, const_iterator last );

Return Value

Iterator following the last removed element.

If pos refers to the last element, then the end() iterator is returned.

If last==end() prior to removal, then the updated end() iterator is returned.

If [first, last) is an empty range, then last is returned.

std::sort on empty vector

f.begin()+1 is out of bounds and that is the reason for the segmentation fault.

Use f.begin() for the beginning of the array.And that will be safe to use.

---

Related Topics