Removing a vector element using std::swap and std::vector::resize.

Discussion in 'C++' started by Jason Heyes, Jan 15, 2006.

  1. Jason Heyes

    Jason Heyes Guest

    Does the STL have a function like this one?

    template <typename T>
    void remove(std::vector<T> &v, std::vector<T>::size_type index)
    {
    std::swap(v[index], v.back());
    v.resize(index);
    }

    Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
    what size of vector you are removing from and no matter where the removed
    element is located.
    Jason Heyes, Jan 15, 2006
    #1
    1. Advertising

  2. * Jason Heyes:
    > Does the STL have a function like this one?
    >
    > template <typename T>
    > void remove(std::vector<T> &v, std::vector<T>::size_type index)
    > {
    > std::swap(v[index], v.back());
    > v.resize(index);
    > }
    >
    > Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
    > what size of vector you are removing from and no matter where the removed
    > element is located.


    Possibly you meant

    v.resize( v.size() - 1 );

    And possibly, when you write "the STL" you mean the C++ standard library,
    not the STL.

    Regarding whether there is such a function, do read the documentation.

    Cheers,

    - Alf

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Jan 15, 2006
    #2
    1. Advertising

  3. Jason Heyes

    Calum Grant Guest

    Jason Heyes wrote:
    > Does the STL have a function like this one?
    >
    > template <typename T>
    > void remove(std::vector<T> &v, std::vector<T>::size_type index)
    > {
    > std::swap(v[index], v.back());
    > v.resize(index);


    Do you mean v.pop_back()?

    > }
    >
    > Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
    > what size of vector you are removing from and no matter where the removed
    > element is located.
    >


    I suggest you try using that function to see what happens! I don't
    think it works quite the same as erase...
    Calum Grant, Jan 15, 2006
    #3
  4. On Sun, 15 Jan 2006 14:14:21 GMT, Calum Grant
    <> wrote:

    >> template <typename T>
    >> void remove(std::vector<T> &v, std::vector<T>::size_type index)
    >> {
    >> std::swap(v[index], v.back());
    >> v.resize(index);

    >
    >Do you mean v.pop_back()?


    He means v.back() -- how could he mean anything else?

    >> }
    >>
    >> Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
    >> what size of vector you are removing from and no matter where the removed
    >> element is located.
    >>

    >
    >I suggest you try using that function to see what happens! I don't
    >think it works quite the same as erase...


    True, it doesn't work the same. But as long as the remaining elements
    don't have to be in any specific order, I suppose it would be much
    faster than calling (v.size()-index) times T::eek:perator=(). Indeed,
    this would perform in O(1) time for any given type T, whereas
    v.erase() could only do O(n) at best (where n == v.size()-index).

    As an aside, it should work for v.front() as well as v.back() (or *it
    for any iterator it of v where it != v.end()). As it is, there should
    be a little more sanity-checking; e.g., v cannot be empty, and
    v.back() should point to a different element than v[index].

    --
    Bob Hairgrove
    Bob Hairgrove, Jan 15, 2006
    #4
  5. On Sun, 15 Jan 2006 17:16:07 +0100, Bob Hairgrove
    <> wrote:

    [snip]

    PS -- what Alf said, re: v.resize(v.size()-1);

    --
    Bob Hairgrove
    Bob Hairgrove, Jan 15, 2006
    #5
  6. Jason Heyes

    Calum Grant Guest

    Bob Hairgrove wrote:
    > On Sun, 15 Jan 2006 14:14:21 GMT, Calum Grant
    > <> wrote:
    >
    >
    >>>template <typename T>
    >>>void remove(std::vector<T> &v, std::vector<T>::size_type index)
    >>>{
    >>> std::swap(v[index], v.back());
    >>> v.resize(index);

    >>
    >>Do you mean v.pop_back()?

    >
    >
    > He means v.back() -- how could he mean anything else?


    I mean, v.pop_back() instead of v.resize(index) -- how could I mean
    anything else ;-)

    Personally I prefer v.pop_back() to v.resize(v.size()-1).

    >
    >>>}
    >>>
    >>>Unlike std::vector::erase, it calls T::eek:perator= only three times no matter
    >>>what size of vector you are removing from and no matter where the removed
    >>>element is located.
    >>>

    >>
    >>I suggest you try using that function to see what happens! I don't
    >>think it works quite the same as erase...

    >
    >
    > True, it doesn't work the same. But as long as the remaining elements
    > don't have to be in any specific order, I suppose it would be much
    > faster than calling (v.size()-index) times T::eek:perator=(). Indeed,
    > this would perform in O(1) time for any given type T, whereas
    > v.erase() could only do O(n) at best (where n == v.size()-index).
    >
    > As an aside, it should work for v.front() as well as v.back() (or *it
    > for any iterator it of v where it != v.end()). As it is, there should
    > be a little more sanity-checking; e.g., v cannot be empty, and
    > v.back() should point to a different element than v[index].


    It certainly wouldn't work if you used v.front(). Doing a
    resize()/pop_back() would erase the wrong element.

    Your suggestion might work on a std::deque however. This does have an
    efficient pop_front() function.

    The algorithm would certainly work if index == size()-1. std::swap
    works to swap an item with itself. I would follow the general precedent
    of the standard library - the caller is responsible for ensuring the
    validity of the iterator.




    > --
    > Bob Hairgrove
    >
    Calum Grant, Jan 15, 2006
    #6
  7. On Sun, 15 Jan 2006 17:35:29 GMT, Calum Grant
    <> wrote:

    >> He means v.back() -- how could he mean anything else?

    >
    >I mean, v.pop_back() instead of v.resize(index) -- how could I mean
    >anything else ;-)
    >
    >Personally I prefer v.pop_back() to v.resize(v.size()-1).


    LOL ... my bad ... sorry about the FUD!

    Thought you meant "pop_back() instead of back()". Well, I guess that
    was more than a little stupid of me.

    --
    Bob Hairgrove
    Bob Hairgrove, Jan 15, 2006
    #7
  8. Jason Heyes

    red floyd Guest

    Calum Grant wrote:
    > Jason Heyes wrote:
    >> Does the STL have a function like this one?
    >>
    >> template <typename T>
    >> void remove(std::vector<T> &v, std::vector<T>::size_type index)
    >> {
    >> std::swap(v[index], v.back());
    >> v.resize(index);

    >
    > Do you mean v.pop_back()?
    >
    >> }
    >>
    >> Unlike std::vector::erase, it calls T::eek:perator= only three times no
    >> matter what size of vector you are removing from and no matter where
    >> the removed element is located.

    >
    > I suggest you try using that function to see what happens! I don't
    > think it works quite the same as erase...
    >


    1. should use v.at(index) instead of v[indexx]
    2. Is not safe for empty vector (but item 1 takes care of that).
    red floyd, Jan 15, 2006
    #8
  9. "Jason Heyes" <> wrote in message
    news:43c9b069$0$19068$...
    > Does the STL have a function like this one?


    > template <typename T>
    > void remove(std::vector<T> &v, std::vector<T>::size_type index)
    > {
    > std::swap(v[index], v.back());
    > v.resize(index);
    > }


    > Unlike std::vector::erase, it calls T::eek:perator= only three times no
    > matter what size of vector you are removing from and no matter where the
    > removed element is located.


    Even though the example above is incorrect (v.resize(index) should be
    v.resize(v.size()-1) or, better yet, v.pop_back()), it's hard to imagine
    that this operation would be useful enough to merit a standard function to
    implement it.

    For one thing, it's only two statements. For another, it doesn't preserve
    the ordering of the vector elements, which rather limits its usefulness.
    For a third, most of the operations on vectors use iterators, not indices.

    Can you show us an example of where such a function would be useful?
    Andrew Koenig, Jan 15, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. vsgdp
    Replies:
    2
    Views:
    381
    Alipha
    Oct 15, 2005
  2. vsgdp

    std::vector::resize ,

    vsgdp, Oct 18, 2005, in forum: C++
    Replies:
    10
    Views:
    936
    Jim Langston
    Oct 19, 2005
  3. Niels Dekker (no reply address)

    What swap is called when using std::swap?

    Niels Dekker (no reply address), Jul 19, 2006, in forum: C++
    Replies:
    4
    Views:
    972
    Niels Dekker (no reply address)
    Jul 20, 2006
  4. Simon
    Replies:
    2
    Views:
    477
    Simon
    May 31, 2009
  5. Replies:
    2
    Views:
    1,243
    Adrienne
    Feb 13, 2005
Loading...

Share This Page