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