Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > move element in vector

Reply
Thread Tools

move element in vector

 
 
William Payne
Guest
Posts: n/a
 
      08-30-2004
(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


 
Reply With Quote
 
 
 
 
Mike Wahler
Guest
Posts: n/a
 
      08-30-2004
"William Payne" <(E-Mail Removed)> wrote in message
news:ch07un$ppr$(E-Mail Removed)...
> 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


 
Reply With Quote
 
 
 
 
=?ISO-8859-2?Q?Mateusz_=A3oskot?=
Guest
Posts: n/a
 
      08-30-2004
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
 
Reply With Quote
 
=?ISO-8859-1?Q?Tobias_G=FCntner?=
Guest
Posts: n/a
 
      08-30-2004
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:stream_iterator<int>(std::cout, "\n"));

return 0;
}


--
Regards,
Tobias
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      08-30-2004
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

 
Reply With Quote
 
Howard Hinnant
Guest
Posts: n/a
 
      08-30-2004
In article <ch07un$ppr$(E-Mail Removed)>,
"William Payne" <(E-Mail Removed)> 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
 
Reply With Quote
 
William Payne
Guest
Posts: n/a
 
      08-31-2004

"William Payne" <(E-Mail Removed)> wrote in message
news:ch07un$ppr$(E-Mail Removed)...
> (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


 
Reply With Quote
 
William Payne
Guest
Posts: n/a
 
      08-31-2004

"William Payne" <(E-Mail Removed)> wrote in message
news:ch1npl$8he$(E-Mail Removed)...
>
> "William Payne" <(E-Mail Removed)> wrote in message
> news:ch07un$ppr$(E-Mail Removed)...
>> (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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Move value from one form element to another, hidden element viaJavaScript OccasionalFlyer Javascript 6 07-29-2009 03:33 AM
const vector<A> vs vector<const A> vs const vector<const A> Javier C++ 2 09-04-2007 08:46 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
how the vector is created, how to pass vector to webservices method apachesoap:Vector Rushikesh Joshi Perl Misc 0 07-10-2004 01:04 PM



Advertisments