move element in vector

W

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 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
 
M

Mike Wahler

William Payne said:
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
 
?

=?ISO-8859-2?Q?Mateusz_=A3oskot?=

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
 
?

=?ISO-8859-1?Q?Tobias_G=FCntner?=

William said:
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;
}
 
K

Kai-Uwe Bux

William said:
(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
 
H

Howard Hinnant

William Payne said:
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
 
W

William Payne

William Payne said:
(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
 
W

William Payne

William Payne said:
William Payne said:
(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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top