A container suitable for a "recent files menu"

Discussion in 'C++' started by William Payne, Aug 30, 2004.

  1. 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
    William Payne, Aug 30, 2004
    #1
    1. Advertising

  2. William Payne

    David Hilsee Guest

    "William Payne" <> wrote in message
    news:cgu025$7ov$...
    > 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.

    <snip>
    > 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::eek: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();

    --
    David Hilsee
    David Hilsee, Aug 30, 2004
    #2
    1. Advertising

  3. "William Payne" <> wrote in message
    news:cgu025$7ov$...
    > 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
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Brainbench MVP for C++ <> http://www.brainbench.com
    Ivan Vecerina, Aug 30, 2004
    #3
  4. William Payne

    David Hilsee Guest

    "Ivan Vecerina" <> wrote in
    message news:cgv785$prv$...
    <snip>
    > 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.

    --
    David Hilsee
    David Hilsee, Aug 30, 2004
    #4
  5. "David Hilsee" <> wrote in message
    news:...
    > "Ivan Vecerina" <> wrote
    > in
    > message news:cgv785$prv$...
    > <snip>
    >> What is the advantage in having a class instead of providing
    >> a single non-member function such as:

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


    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
    --
    http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
    Ivan Vecerina, Aug 30, 2004
    #5
  6. William Payne

    Kai-Uwe Bux Guest

    William Payne wrote:
    > 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
    Kai-Uwe Bux, Aug 30, 2004
    #6
  7. "Kai-Uwe Bux" <> wrote in message
    news:ch02a6$e02$...
    > William Payne wrote:
    >> 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
    William Payne, Aug 30, 2004
    #7
  8. William Payne

    Kai-Uwe Bux Guest

    William Payne wrote:

    >
    > "Kai-Uwe Bux" <> wrote in message
    > news:ch02a6$e02$...
    >> William Payne wrote:
    >>> [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
    Kai-Uwe Bux, Aug 30, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vivi Orunitia
    Replies:
    11
    Views:
    4,453
    Martijn Lievaart
    Feb 4, 2004
  2. Maitre Bart
    Replies:
    2
    Views:
    515
    Maitre Bart
    Feb 11, 2004
  3. Steven T. Hatton
    Replies:
    4
    Views:
    3,877
    Rob Williscroft
    Dec 5, 2004
  4. pc
    Replies:
    2
    Views:
    348
    Allan Bruce
    Mar 31, 2005
  5. Replies:
    4
    Views:
    788
    Daniel T.
    Feb 16, 2006
Loading...

Share This Page