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