A container suitable for a "recent files menu"

[William Payne]

Hello, have you seen a recent files menu in a GUI application? In many GUI
applications there's a menu the displays the most recent files that has been
opened by the program. Say such a menu has four entries and the most recent
file is displayed on top and the oldest at the bottom. New entries are added
at the top, pushing the oldest of the list. I wrote a class which I've named
CircularContainer (please help me think of a better name!) that implements a
data structure suited to handling the entries in a recent files menu
(basically it stores std::strings). Given the code below, is it ready to be
used or could it use improving/bug fixing? The code (written in standard
C++):

circular_container.hpp:
#ifndef CIRCULAR_CONTAINER_HPP
#define CIRCULAR_CONTAINER_HPP

#include <cstddef> /* size_t */
#include <cstdio> /* sprintf */
#include <stdexcept>
#include <string>
#include <vector>

/* CircularContainer
* When constructed, the user specifies the max number of *
* elements the container can hold. New elements are added *
* at the beginning of the array. When the container is full *
* and a new element is added, the last one is removed. This *
* makes the CircularContainer a FIFO-type container? Circu- *
* larContainer is ideal for use in implementing Recent Files *
* menus. */

class CircularContainer
{
public:
CircularContainer(std::size_t max_size)
:
m_max_size(max_size)
{
; /* Do nothing. */
}

virtual ~CircularContainer()
{
; /* Do nothing. */
}

void insert(const std::string& s);

std::string get(std::size_t index) const;

std::size_t size() const
{
return m_elements.size();
}

std::size_t max_size() const
{
return m_max_size;
}

void clear();

private:
std::vector<std::string> m_elements;
std::size_t m_max_size;
};

#endif /* #ifndef CIRCULAR_CONTAINER_HPP */

circular_container.cpp:
#include "circular_container.hpp"

using std::sprintf;
using std::string;
using std::vector;
using std::size_t;
using std::runtime_error;

void CircularContainer::insert(const string& s)
{
m_elements.insert(m_elements.begin(), s);

if(m_elements.size() > m_max_size)
{
m_elements.pop_back();
}
}

string CircularContainer::get(size_t index) const
{
char error_message[64];

sprintf(error_message, "Invalid index %i", index);

if(index >= m_elements.size())
{
throw runtime_error(error_message);
}

return m_elements[index];
}

void CircularContainer::clear()
{
m_elements.erase(m_elements.begin(), m_elements.end());
}


Thanks for any replies!

/ WP

 

[David Hilsee]

Hello, have you seen a recent files menu in a GUI application? In many GUI
applications there's a menu the displays the most recent files that has been
opened by the program. Say such a menu has four entries and the most recent
file is displayed on top and the oldest at the bottom. New entries are added
at the top, pushing the oldest of the list. I wrote a class which I've named
CircularContainer (please help me think of a better name!) that implements a
data structure suited to handling the entries in a recent files menu
(basically it stores std::strings). Given the code below, is it ready to be
used or could it use improving/bug fixing? The code (written in standard
C++):

circular_container.hpp:
#ifndef CIRCULAR_CONTAINER_HPP
#define CIRCULAR_CONTAINER_HPP

#include <cstddef> /* size_t */
#include <cstdio> /* sprintf */
#include <stdexcept>
#include <string>
#include <vector>

/* CircularContainer
* When constructed, the user specifies the max number of *
* elements the container can hold. New elements are added *
* at the beginning of the array. When the container is full *
* and a new element is added, the last one is removed. This *
* makes the CircularContainer a FIFO-type container? Circu- *
* larContainer is ideal for use in implementing Recent Files *
* menus. */

class CircularContainer
{
public:
CircularContainer(std::size_t max_size)
:
m_max_size(max_size)
{
; /* Do nothing. */
}

You could add a call to reserve() here if you wanted to allocate the
vector's storage ahead of time.

circular_container.cpp:
#include "circular_container.hpp"

using std::sprintf;
using std::string;
using std::vector;
using std::size_t;
using std::runtime_error;

void CircularContainer::insert(const string& s)
{
m_elements.insert(m_elements.begin(), s);

if(m_elements.size() > m_max_size)
{
m_elements.pop_back();
}
}

The best containers for this type of usage are std::deque and std::list, not
std::vector. However, since this container is unlikely to hold many
elements, the performance difference will probably be negligible.

string CircularContainer::get(size_t index) const
{
char error_message[64];

sprintf(error_message, "Invalid index %i", index);

if(index >= m_elements.size())
{
throw runtime_error(error_message);
}

return m_elements[index];
}

You might want to use something besides sprintf (say, a stringstream), even
though it probably will do no harm in this case. Also, you may want to
avoid constructing the error string until it has been determined that the
exception should be thrown. Lastly, consider using std:ut_of_range
instead of std::runtime_error, because that is what containers use for their
bounds checking. In fact, consider replacing the implementation of this
function with one line:

return m_elements.at(index);

void CircularContainer::clear()
{
m_elements.erase(m_elements.begin(), m_elements.end());
}

This could be written as

m_elements.clear();

 

[Ivan Vecerina]

Hello, have you seen a recent files menu in a GUI application? In many GUI
applications there's a menu the displays the most recent files that has
been opened by the program. Say such a menu has four entries and the most
recent file is displayed on top and the oldest at the bottom. New entries
are added at the top, pushing the oldest of the list. I wrote a class
which I've named CircularContainer (please help me think of a better
name!) that implements a data structure suited to handling the entries in
a recent files menu (basically it stores std::strings). Given the code
below, is it ready to be used or could it use improving/bug fixing?

The key question I would ask is: do you really need to create a new
container class to provide the functionality that you need?

What is the advantage in having a class instead of providing
a single non-member function such as:

typedef std::vector<std::string> HistoryList;

//template<class HistoryList> // <- could make this a template instead
void insertHistoryItem( HistoryList& container
, HistoryList::value_type const& newItem
, int maxSize = 10 )
{
container.insert( container.begin(), newItem );

if(container.size() > maxSize )
{
container.pop_back();
}
}

The benefits of this approach are:
- No need to add a bunch of forwarding functions to reproduce
the original container interface.
- Greater maintainability and genericity (the function can be
converted into a template, and be applied to other containers).
- Fewer classes/code, easier integration with 3rd-party code, ...


Cheers,
Ivan

 

[David Hilsee]

message

What is the advantage in having a class instead of providing
a single non-member function such as:

typedef std::vector<std::string> HistoryList;

//template<class HistoryList> // <- could make this a template instead
void insertHistoryItem( HistoryList& container
, HistoryList::value_type const& newItem
, int maxSize = 10 )
{
container.insert( container.begin(), newItem );

if(container.size() > maxSize )
{
container.pop_back();
}
}

The benefits of this approach are:
- No need to add a bunch of forwarding functions to reproduce
the original container interface.
- Greater maintainability and genericity (the function can be
converted into a template, and be applied to other containers).
- Fewer classes/code, easier integration with 3rd-party code, ...

The only downside is that someone could accidentally change the maximum size
of the container, or insert elements into the wrong place. That may or may
not be a problem, depending on what you're doing. To provide easier
integration with third-party code, one could provide a getter that returns a
const reference to the container, or, even better, a copy of it.

 

[Ivan Vecerina]

in
message

The only downside is that someone could accidentally change the maximum
size
of the container, or insert elements into the wrong place. That may or
may
not be a problem, depending on what you're doing. To provide easier
integration with third-party code, one could provide a getter that returns
a
const reference to the container, or, even better, a copy of it.

Agreed. The level of abstraction that is lost by removing the class
can be provided by another class that contains the document list -- i.e.
a kind of DocumentManager that will maintain the list while it
handles document handling events (open/close/...). This document
manager will somehow provide "the outside" with read-access to the list.
IMO the abstraction of the container itself probably isn't
reusable enough to justify the addition of a dedicated class.
But of course YMMV.

Kind regards,
Ivan

 

[Kai-Uwe Bux]

Hello, have you seen a recent files menu in a GUI application? In many
GUI applications there's a menu the displays the most recent files
that has been opened by the program. Say such a menu has four entries
and the most recent file is displayed on top and the oldest at the
bottom. New entries are added at the top, pushing the oldest of the list.

[snip]

void CircularContainer::insert(const string& s)
{
m_elements.insert(m_elements.begin(), s);

if(m_elements.size() > m_max_size)
{
m_elements.pop_back();
}
}

This will allow the same file to be listed multiple times in the history.
Do you want that, or would you rather have that entry just move to the top?


Best

Kai-Uwe Bux

 

[William Payne]

Hello, have you seen a recent files menu in a GUI application? In many
GUI applications there's a menu the displays the most recent files
that has been opened by the program. Say such a menu has four entries
and the most recent file is displayed on top and the oldest at the
bottom. New entries are added at the top, pushing the oldest of the list.

[snip]

void CircularContainer::insert(const string& s)
{
m_elements.insert(m_elements.begin(), s);

if(m_elements.size() > m_max_size)
{
m_elements.pop_back();
}
}

This will allow the same file to be listed multiple times in the history.
Do you want that, or would you rather have that entry just move to the
top?


Best

Kai-Uwe Bux

Good catch! If an entry already exists it should definetly be moved to the
top, I will implement that. I also realised I need to store the path of the
file along with the name I want to display. Since I may add additional
requirements I will make the class templated.

Now, anyone got a better name than CircularContainer??

/ WP

 

[Kai-Uwe Bux]

[snip]
void CircularContainer::insert(const string& s)
{
m_elements.insert(m_elements.begin(), s);

if(m_elements.size() > m_max_size)
{
m_elements.pop_back();
}
}

This will allow the same file to be listed multiple times in the history.
Do you want that, or would you rather have that entry just move to the
top?


Best

Kai-Uwe Bux

Good catch! If an entry already exists it should definetly be moved to the
top, I will implement that. I also realised I need to store the path of
the file along with the name I want to display. Since I may add additional
requirements I will make the class templated.

You could actually implement it as an adaptor to an underlying container
type, very much the way std::stack and std::queue are implemented.

Now, anyone got a better name than CircularContainer??

Well, the technique of moving the most recently retrieved item to the front
of a list has been known for a long time as a "self organizing file" or
"self organizing list" (see Knuth: TAOCP Vol III 2nd ed., Section 6.1,
pages 401ff). Since for your container, you want a limited number of
entries, the least recently used dropping off the end, I would suggest

SelfOrganizingCache


Best

Kai-Uwe Bux