move element in vector

Discussion in 'C++' started by William Payne, Aug 30, 2004.

  1. (This post is related to "recent files menu"-post below. If I should have
    kept this in that thread, I apologise.)
    Hello, I have a function that adds a std::string to a std::vector. New
    entries are added at the front (index 0) of the vector. If the vector
    contains a certain amount of elements, the element at the back is removed
    when a new one is added. If one tries to add a string already stored in the
    vector, that string is supposed to move to the front, pushing everything
    else before it down one notch. Here's my solution:

    void CircularContainer::insert(const string& s)
    {
    vector<string>::const_iterator itr =
    find(m_elements.begin(), m_elements.end(), s);

    if(itr != m_elements.end())
    {
    vector<string> temp_array;

    temp_array.push_back(*itr);

    for(size_t i = 0; i < m_elements.size(); ++i)
    {
    if(m_elements != *itr)
    {
    temp_array.push_back(m_elements);
    }
    }

    m_elements = temp_array;
    }
    else
    {
    m_elements.insert(m_elements.begin(), s);

    if(m_elements.size() > m_max_size)
    {
    m_elements.pop_back();
    }
    }
    }

    My questions is about the code that deals with the case where the string was
    already found in the vector:

    if(itr != m_elements.end())
    {
    vector<string> temp_array;

    temp_array.push_back(*itr);

    for(size_t i = 0; i < m_elements.size(); ++i)
    {
    if(m_elements != *itr)
    {
    temp_array.push_back(m_elements);
    }
    }
    }

    Is there a better way to move the element to the top, maybe using some
    function in the standard library I don't know about? Creating a completely
    new vector and copying each element in the correct to that one seems so
    brute-forceish.

    / WP
     
    William Payne, Aug 30, 2004
    #1
    1. Advertising

  2. William Payne

    Mike Wahler Guest

    "William Payne" <> wrote in message
    news:ch07un$ppr$...
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.


    Don't use a vector. Use a (de)queue or a list.

    -Mike
     
    Mike Wahler, Aug 30, 2004
    #2
    1. Advertising

  3. On 8/30/2004 11:59 PM, William Payne wrote:
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.


    It seems to be a kind of Most Recently Used solution ;-)
    I have my own one and I developed that using double linked list.
    I think dequeue will work well too.

    Greets

    --

    Mateusz £oskot
    mateusz at loskot dot net
     
    =?ISO-8859-2?Q?Mateusz_=A3oskot?=, Aug 30, 2004
    #3
  4. William Payne wrote:
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.


    That depends on the container...
    IMO you could use rotate:

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

    int main()
    {
    const std::size_t max_size = 5;
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    int newItem = 2;

    std::vector<int>::iterator found =
    std::find(v.begin(), v.end(), newItem);

    if(found == v.end())
    {
    if(v.size() >= max_size)
    v.pop_back();
    v.insert(v.begin(), newItem);
    }
    else
    {
    std::rotate(v.begin(), found, found + 1);
    }

    std::copy(v.begin(), v.end(),
    std::eek:stream_iterator<int>(std::cout, "\n"));

    return 0;
    }


    --
    Regards,
    Tobias
     
    =?ISO-8859-1?Q?Tobias_G=FCntner?=, Aug 30, 2004
    #4
  5. William Payne

    Kai-Uwe Bux Guest

    William Payne wrote:

    > (This post is related to "recent files menu"-post below. If I should have
    > kept this in that thread, I apologise.)
    > Hello, I have a function that adds a std::string to a std::vector. New
    > entries are added at the front (index 0) of the vector. If the vector
    > contains a certain amount of elements, the element at the back is removed
    > when a new one is added. If one tries to add a string already stored in
    > the vector, that string is supposed to move to the front, pushing
    > everything else before it down one notch. Here's my solution:
    >
    > void CircularContainer::insert(const string& s)
    > {
    > vector<string>::const_iterator itr =
    > find(m_elements.begin(), m_elements.end(), s);
    >
    > if(itr != m_elements.end())
    > {
    > vector<string> temp_array;
    >
    > temp_array.push_back(*itr);
    >
    > for(size_t i = 0; i < m_elements.size(); ++i)
    > {
    > if(m_elements != *itr)
    > {
    > temp_array.push_back(m_elements);
    > }
    > }
    >
    > m_elements = temp_array;
    > }
    > else
    > {
    > m_elements.insert(m_elements.begin(), s);
    >
    > if(m_elements.size() > m_max_size)
    > {
    > m_elements.pop_back();
    > }
    > }
    > }
    >
    > My questions is about the code that deals with the case where the string
    > was already found in the vector:
    >
    > if(itr != m_elements.end())
    > {
    > vector<string> temp_array;
    >
    > temp_array.push_back(*itr);
    >
    > for(size_t i = 0; i < m_elements.size(); ++i)
    > {
    > if(m_elements != *itr)
    > {
    > temp_array.push_back(m_elements);
    > }
    > }
    > }
    >
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.



    What about using std::list<> instead of std::vector<>. Here is a version
    that is templated on a container type, so that you can do experiments as to
    see what works best:


    #include <algorithm>

    template < typename T, template < typename S > class container >
    class SelfOrganizingCache {
    public:
    typedef T value_type;
    typedef container< value_type > sequence_type;
    typedef typename sequence_type::size_type size_type;
    typedef typename sequence_type::difference_type difference_type;
    typedef typename sequence_type::const_iterator const_iterator;
    typedef typename sequence_type::const_reverse_iterator
    const_reverse_iterator;

    private:

    sequence_type the_sequence;
    size_type the_size;
    size_type the_capacity;

    void push_item ( const value_type & item ) {
    the_sequence.insert( the_sequence.begin(), item );
    ++ the_size;
    }

    void pop ( void ) {
    the_sequence.pop_back();
    --the_size;
    }

    public:

    SelfOrganizingCache ( size_type capacity )
    : the_sequence ()
    , the_size ( 0 )
    , the_capacity ( capacity )
    {}

    ~SelfOrganizingCache ( void ) {}

    void push ( const value_type & item ) {
    typename sequence_type::iterator item_pos
    = std::find( the_sequence.begin(), the_sequence.end(), item );
    if ( item_pos != the_sequence.end() ) {
    the_sequence.erase( item_pos );
    -- the_size;
    }
    push_item( item );
    if ( the_size > the_capacity ) {
    pop();
    }
    }

    void resize ( size_type capacity ) {
    the_capacity = capacity;
    while ( the_size > the_capacity ) {
    pop();
    }
    }

    size_type size ( void ) {
    return( the_size );
    }

    size_type capacity ( void ) {
    return( the_capacity );
    }

    const_iterator begin ( void ) const {
    return( the_sequence.begin() );
    }

    const_iterator end ( void ) const {
    return( the_sequence.end() );
    }

    const_reverse_iterator rbegin ( void ) const {
    return( the_sequence.rbegin() );
    }

    const_reverse_iterator rend ( void ) const {
    return( the_sequence.rend() );
    }

    }; // SelfOrganizingCache

    /*
    Testing push:
    */

    class RandomNumberGenerator {
    public:

    RandomNumberGenerator ( unsigned long int seed )
    {
    std::srand( seed );
    }

    RandomNumberGenerator ( void )
    {}

    unsigned long lower ( void ) const {
    return ( 0 );
    }

    unsigned long upper ( void ) const {
    return ( RAND_MAX );
    }

    unsigned long operator() ( void ) {
    return( std::rand() );
    }

    unsigned long int operator() ( unsigned long int bound ) {
    unsigned long int_width = RAND_MAX / bound;
    unsigned long max_valid = int_width * bound;
    unsigned long seed;
    do {
    seed = std::rand();
    } while ( seed >= max_valid );
    return( seed / int_width );
    }

    }; // RandomNumberGenerator

    #include <iostream>
    #include <list> // reccommended
    #include <vector>
    #include <deque>

    int main ( void ) {
    typedef SelfOrganizingCache< unsigned long, std::vector > Cache;
    Cache c ( 10 );
    RandomNumberGenerator R ( 12344 );
    for ( unsigned long i = 0; i < 100; ++i ) {
    unsigned long l = R( 15 );
    std::cout << "pushing " << l << " :";
    c.push( l );
    for ( Cache::const_iterator iter = c.begin();
    iter != c.end();
    ++ iter ) {
    std::cout << " " << *iter;
    }
    std::cout << "\n";
    }
    }



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 31, 2004
    #5
  6. In article <ch07un$ppr$>,
    "William Payne" <> wrote:

    > My questions is about the code that deals with the case where the string was
    > already found in the vector:
    >
    > if(itr != m_elements.end())
    > {
    > vector<string> temp_array;
    >
    > temp_array.push_back(*itr);
    >
    > for(size_t i = 0; i < m_elements.size(); ++i)
    > {
    > if(m_elements != *itr)
    > {
    > temp_array.push_back(m_elements);
    > }
    > }
    > }
    >
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.


    <nod> You only need to make temporary space for the found string, well
    actually not even that since it is already stored in s. You don't need
    a temporary vector. How 'bout this:

    if(itr != m_elements.end())
    *--std::copy_backward(m_elements.begin(), itr, itr+1) = s;
    else
    ...

    Saves the temp vector. And saves disturbing at all any strings beyond
    itr. And should also work fine if you switch to list or deque. If you
    switch to list, you might want to investigate splice instead of
    copy_backward as it would probably increase performance. But it is not
    a given that you should switch. Measure first.

    If by any chance you use Metrowerks CodeWarrior, Metrowerks::cdeque is
    another excellent container for this application (it is a contiguous
    memory circular buffer). It would optimize the push_front/pop_back
    branch of your logic.

    -Howard
     
    Howard Hinnant, Aug 31, 2004
    #6
  7. "William Payne" <> wrote in message
    news:ch07un$ppr$...
    > (This post is related to "recent files menu"-post below. If I should have
    > kept this in that thread, I apologise.)
    > Hello, I have a function that adds a std::string to a std::vector. New
    > entries are added at the front (index 0) of the vector. If the vector
    > contains a certain amount of elements, the element at the back is removed
    > when a new one is added. If one tries to add a string already stored in
    > the vector, that string is supposed to move to the front, pushing
    > everything else before it down one notch. Here's my solution:
    >
    > void CircularContainer::insert(const string& s)
    > {
    > vector<string>::const_iterator itr =
    > find(m_elements.begin(), m_elements.end(), s);
    >
    > if(itr != m_elements.end())
    > {
    > vector<string> temp_array;
    >
    > temp_array.push_back(*itr);
    >
    > for(size_t i = 0; i < m_elements.size(); ++i)
    > {
    > if(m_elements != *itr)
    > {
    > temp_array.push_back(m_elements);
    > }
    > }
    >
    > m_elements = temp_array;
    > }
    > else
    > {
    > m_elements.insert(m_elements.begin(), s);
    >
    > if(m_elements.size() > m_max_size)
    > {
    > m_elements.pop_back();
    > }
    > }
    > }
    >
    > My questions is about the code that deals with the case where the string
    > was already found in the vector:
    >
    > if(itr != m_elements.end())
    > {
    > vector<string> temp_array;
    >
    > temp_array.push_back(*itr);
    >
    > for(size_t i = 0; i < m_elements.size(); ++i)
    > {
    > if(m_elements != *itr)
    > {
    > temp_array.push_back(m_elements);
    > }
    > }
    > }
    >
    > Is there a better way to move the element to the top, maybe using some
    > function in the standard library I don't know about? Creating a completely
    > new vector and copying each element in the correct to that one seems so
    > brute-forceish.
    >
    > / WP
    >

    Thanks for all the replies. I ended up trying the following code:

    vector<string>::iterator itr =
    find(m_elements.begin(), m_elements.end(), s);

    if(itr != m_elements.end() && itr != m_elements.begin())
    {
    /* Copy element to the front. */
    m_elements.insert(m_elements.begin(), *itr);

    /* Erase the the element at the old position. */
    m_elements.erase(itr);
    }

    Then I tried inserting the string "three" when m_elements contained
    (ascending index order):
    five
    four
    three
    two

    I expected the result to be:
    three
    five
    four
    two

    But I got:
    three
    five
    three
    two

    Why?? I don't understand...clearly erase() isn't working as I thought it
    would work.

    / WP
     
    William Payne, Aug 31, 2004
    #7
  8. "William Payne" <> wrote in message
    news:ch1npl$8he$...
    >
    > "William Payne" <> wrote in message
    > news:ch07un$ppr$...
    >> (This post is related to "recent files menu"-post below. If I should have
    >> kept this in that thread, I apologise.)
    >> Hello, I have a function that adds a std::string to a std::vector. New
    >> entries are added at the front (index 0) of the vector. If the vector
    >> contains a certain amount of elements, the element at the back is removed
    >> when a new one is added. If one tries to add a string already stored in
    >> the vector, that string is supposed to move to the front, pushing
    >> everything else before it down one notch. Here's my solution:
    >>
    >> void CircularContainer::insert(const string& s)
    >> {
    >> vector<string>::const_iterator itr =
    >> find(m_elements.begin(), m_elements.end(), s);
    >>
    >> if(itr != m_elements.end())
    >> {
    >> vector<string> temp_array;
    >>
    >> temp_array.push_back(*itr);
    >>
    >> for(size_t i = 0; i < m_elements.size(); ++i)
    >> {
    >> if(m_elements != *itr)
    >> {
    >> temp_array.push_back(m_elements);
    >> }
    >> }
    >>
    >> m_elements = temp_array;
    >> }
    >> else
    >> {
    >> m_elements.insert(m_elements.begin(), s);
    >>
    >> if(m_elements.size() > m_max_size)
    >> {
    >> m_elements.pop_back();
    >> }
    >> }
    >> }
    >>
    >> My questions is about the code that deals with the case where the string
    >> was already found in the vector:
    >>
    >> if(itr != m_elements.end())
    >> {
    >> vector<string> temp_array;
    >>
    >> temp_array.push_back(*itr);
    >>
    >> for(size_t i = 0; i < m_elements.size(); ++i)
    >> {
    >> if(m_elements != *itr)
    >> {
    >> temp_array.push_back(m_elements);
    >> }
    >> }
    >> }
    >>
    >> Is there a better way to move the element to the top, maybe using some
    >> function in the standard library I don't know about? Creating a
    >> completely new vector and copying each element in the correct to that one
    >> seems so brute-forceish.
    >>
    >> / WP
    >>

    > Thanks for all the replies. I ended up trying the following code:
    >
    > vector<string>::iterator itr =
    > find(m_elements.begin(), m_elements.end(), s);
    >
    > if(itr != m_elements.end() && itr != m_elements.begin())
    > {
    > /* Copy element to the front. */
    > m_elements.insert(m_elements.begin(), *itr);
    >
    > /* Erase the the element at the old position. */
    > m_elements.erase(itr);
    > }
    >
    > Then I tried inserting the string "three" when m_elements contained
    > (ascending index order):
    > five
    > four
    > three
    > two
    >
    > I expected the result to be:
    > three
    > five
    > four
    > two
    >
    > But I got:
    > three
    > five
    > three
    > two
    >
    > Why?? I don't understand...clearly erase() isn't working as I thought it
    > would work.
    >
    > / WP
    >


    Bah, never mind! I forgot to increment the iterator after performing the
    insertion. Now it works great.

    / WP
     
    William Payne, Aug 31, 2004
    #8
    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. pmatos
    Replies:
    6
    Views:
    24,037
  2. Replies:
    8
    Views:
    1,987
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    603
    James Kanze
    Sep 4, 2007
  4. Rushikesh Joshi
    Replies:
    0
    Views:
    387
    Rushikesh Joshi
    Jul 10, 2004
  5. OccasionalFlyer
    Replies:
    6
    Views:
    258
    Garrett Smith
    Jul 29, 2009
Loading...

Share This Page