move element in vector

[William Payne]

(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 CircularContain er::insert(cons t 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[i] != *itr)
{
temp_array.push _back(m_element s[i]);
}
}

m_elements = temp_array;
}
else
{
m_elements.inse rt(m_elements.b egin(), s);

if(m_elements.s ize() > 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[i] != *itr)
{
temp_array.push _back(m_element s[i]);
}
}
}

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

[Mike Wahler]

Re: move element in vector

"William Payne" <mikas493_no_sp am@student.liu. se> wrote in message
news:ch07un$ppr $1@news.island. liu.se...[color=blue]
> 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.[/color]

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

-Mike

[Mateusz £oskot]

Re: move element in vector

On 8/30/2004 11:59 PM, William Payne wrote:[color=blue]
> 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.[/color]

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

[Tobias Güntner]

Re: move element in vector

William Payne wrote:[color=blue]
> 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.[/color]

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.beg in(), v.end(), newItem);

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

std::copy(v.beg in(), v.end(),
std::ostream_it erator<int>(std ::cout, "\n"));

return 0;
}


--
Regards,
Tobias

[Kai-Uwe Bux]

Re: move element in vector

William Payne wrote:
[color=blue]
> (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 CircularContain er::insert(cons t 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[i] != *itr)
> {
> temp_array.push _back(m_element s[i]);
> }
> }
>
> m_elements = temp_array;
> }
> else
> {
> m_elements.inse rt(m_elements.b egin(), s);
>
> if(m_elements.s ize() > 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[i] != *itr)
> {
> temp_array.push _back(m_element s[i]);
> }
> }
> }
>
> 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.[/color]


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 SelfOrganizingC ache {
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_i terator
const_reverse_i terator;

private:

sequence_type the_sequence;
size_type the_size;
size_type the_capacity;

void push_item ( const value_type & item ) {
the_sequence.in sert( the_sequence.be gin(), item );
++ the_size;
}

void pop ( void ) {
the_sequence.po p_back();
--the_size;
}

public:

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

~SelfOrganizing Cache ( void ) {}

void push ( const value_type & item ) {
typename sequence_type:: iterator item_pos
= std::find( the_sequence.be gin(), the_sequence.en d(), item );
if ( item_pos != the_sequence.en d() ) {
the_sequence.er ase( 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.be gin() );
}

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

const_reverse_i terator rbegin ( void ) const {
return( the_sequence.rb egin() );
}

const_reverse_i terator rend ( void ) const {
return( the_sequence.re nd() );
}

}; // SelfOrganizingC ache

/*
Testing push:
*/

class RandomNumberGen erator {
public:

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

RandomNumberGen erator ( 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 );
}

}; // RandomNumberGen erator

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

int main ( void ) {
typedef SelfOrganizingC ache< unsigned long, std::vector > Cache;
Cache c ( 10 );
RandomNumberGen erator 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_it erator iter = c.begin();
iter != c.end();
++ iter ) {
std::cout << " " << *iter;
}
std::cout << "\n";
}
}



Best

Kai-Uwe Bux

[Howard Hinnant]

Re: move element in vector

In article <ch07un$ppr$1@n ews.island.liu. se>,
"William Payne" <mikas493_no_sp am@student.liu. se> wrote:
[color=blue]
> 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[i] != *itr)
> {
> temp_array.push _back(m_element s[i]);
> }
> }
> }
>
> 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.[/color]

<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_backw ard(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::cde que 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

[William Payne]

Re: move element in vector


"William Payne" <mikas493_no_sp am@student.liu. se> wrote in message
news:ch07un$ppr $1@news.island. liu.se...[color=blue]
> (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 CircularContain er::insert(cons t 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[i] != *itr)
> {
> temp_array.push _back(m_element s[i]);
> }
> }
>
> m_elements = temp_array;
> }
> else
> {
> m_elements.inse rt(m_elements.b egin(), s);
>
> if(m_elements.s ize() > 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[i] != *itr)
> {
> temp_array.push _back(m_element s[i]);
> }
> }
> }
>
> 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
>[/color]
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.begi n())
{
/* Copy element to the front. */
m_elements.inse rt(m_elements.b egin(), *itr);

/* Erase the the element at the old position. */
m_elements.eras e(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...cl early erase() isn't working as I thought it
would work.

/ WP

[William Payne]

Re: move element in vector


"William Payne" <mikas493_no_sp am@student.liu. se> wrote in message
news:ch1npl$8he $1@news.island. liu.se...[color=blue]
>
> "William Payne" <mikas493_no_sp am@student.liu. se> wrote in message
> news:ch07un$ppr $1@news.island. liu.se...[color=green]
>> (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 CircularContain er::insert(cons t 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[i] != *itr)
>> {
>> temp_array.push _back(m_element s[i]);
>> }
>> }
>>
>> m_elements = temp_array;
>> }
>> else
>> {
>> m_elements.inse rt(m_elements.b egin(), s);
>>
>> if(m_elements.s ize() > 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[i] != *itr)
>> {
>> temp_array.push _back(m_element s[i]);
>> }
>> }
>> }
>>
>> 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
>>[/color]
> 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.begi n())
> {
> /* Copy element to the front. */
> m_elements.inse rt(m_elements.b egin(), *itr);
>
> /* Erase the the element at the old position. */
> m_elements.eras e(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...cl early erase() isn't working as I thought it
> would work.
>
> / WP
>[/color]

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

/ WP