By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,660 Members | 1,961 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,660 IT Pros & Developers. It's quick & easy.

move element in vector

P: n/a
(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[i] != *itr)
{
temp_array.push_back(m_elements[i]);
}
}

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[i] != *itr)
{
temp_array.push_back(m_elements[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
Jul 22 '05 #1
Share this Question
Share on Google+
7 Replies


P: n/a
"William Payne" <mi**************@student.liu.se> wrote in message
news:ch**********@news.island.liu.se...
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
Jul 22 '05 #2

P: n/a
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
Jul 22 '05 #3

P: n/a
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::ostream_iterator<int>(std::cout, "\n"));

return 0;
}
--
Regards,
Tobias
Jul 22 '05 #4

P: n/a
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[i] != *itr)
{
temp_array.push_back(m_elements[i]);
}
}

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[i] != *itr)
{
temp_array.push_back(m_elements[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.

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

Jul 22 '05 #5

P: n/a
In article <ch**********@news.island.liu.se>,
"William Payne" <mi**************@student.liu.se> 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[i] != *itr)
{
temp_array.push_back(m_elements[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.


<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
Jul 22 '05 #6

P: n/a

"William Payne" <mi**************@student.liu.se> wrote in message
news:ch**********@news.island.liu.se...
(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[i] != *itr)
{
temp_array.push_back(m_elements[i]);
}
}

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[i] != *itr)
{
temp_array.push_back(m_elements[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

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
Jul 22 '05 #7

P: n/a

"William Payne" <mi**************@student.liu.se> wrote in message
news:ch**********@news.island.liu.se...

"William Payne" <mi**************@student.liu.se> wrote in message
news:ch**********@news.island.liu.se...
(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[i] != *itr)
{
temp_array.push_back(m_elements[i]);
}
}

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[i] != *itr)
{
temp_array.push_back(m_elements[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

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
Jul 22 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.