Thread: 'recyclable' list

  1. #1
    Registered User
    Join Date
    Aug 2016
    Posts
    3

    'recyclable' list

    hi folks.

    i'm wondering if anyone here can tell me whether a particular data type
    exists. while i have code that works currently, i feel that it's spending
    too much time dynamically allocating data, and the data type i'm
    looking for would alleviate the necessity for this. i know i could create
    one myself easily, but i'm just wondering if one like this exists since i
    haven't come across one before

    it's kind of hard to describe what i want, so i'll provide some pseudo
    code with comments. the data type i'm looking for is called
    'recyclable_list' in the code:

    Code:
    {
      recyclable_list<int> rl;
    ​ ​ 
      // put some data in the list  
      for (int ii = 0; ii < 10; ++ii)
        rl.push_back(ii);​​
    
      rl.print(); // would print 10 elements
    
      rl.clear();
      // this doesn't clear memory. instead it should just mark
      // rl as being cleared. ie, the 10 elements that have already
      // been assigned have not been deleted, but rl.size() would
      // still say 0. there should probably be a member called
      // something like total_size that would be 10
    
      rl.print(); // wouldn't print anything
    ​ ​ 
      // push some more data in
      for (int ii = 0; ii < 5; ++ii)
        rl.push_back(ii); 
        // no new memory is actually allocated here since 5 < 10
     
      rl.print(); // would bring five elements
    
      // push some more data in
      for (int ii = 0; ii < 10; ++ii)
        rl.push_back(ii); 
        // since i didn't clear before this loop, eventually rl will  
        // grow to a length of 15
    
      rl.print(); // would bring fifteen elements
    }
    // the allocated memory is only deallocated when rl goes out
    // of scope
    because i'm sure the total size is never going to grow very large i'm not
    worried about possible memory issues.

    NOTE: it doesn't have to be a list. i'm happy with any array/dynamic array/list/etc solution that might exist.
    Last edited by andcomma; 08-28-2016 at 02:44 PM.

  2. #2
    Registered User
    Join Date
    Aug 2016
    Posts
    3
    i'm still interested to know if this is a standard kind of data structure. if not, i think this should suffice:

    Code:
    template<typename ty>
    class agglomerative_list {
    private:
        std::vector<ty> buf;
    
        size_t sz = 0;
    
    
    public:
    
        /*
         * Constructors
         */
    
        agglomerative_list() {
        }
    
        agglomerative_list(const size_t &length)
                : sz(0), buf(length) {
        }
    
        agglomerative_list(const agglomerative_list &al)
                : sz(al.sz), buf(al.buf) {
        }
    
        agglomerative_list(const std::initializer_list<ty> &list)
                : sz(list.size()), buf(list) {
        }
    
    
        /*
         * Add data
         */
    
        void push_back(const ty &val) {
          if (sz >= buf.size())
            buf.push_back(val);
    
          else
            buf[sz] = val;
    
          ++sz;
        }
    
    
        /*
         * Reset the view into the list
         */
    
        void reset() {
          sz = 0;
        }
    
    
        /*
         * Size
         */
    
        size_t size() const {
          return sz;
        }
    
        size_t total_size() const {
          return buf.size();
        }
    
    
        /*
         * Random access
         */
    
        ty &at(const size_t &pos) {
          assert(pos < sz);
    
          return buf[pos];
        }
    
        const ty &at(const size_t &pos) const {
          assert(pos < sz);
    
          return buf[pos];
        }
    
    
        /*
         * Iteration
         */
    
        typedef typename std::vector<ty>::iterator iterator;
        typedef typename std::vector<ty>::const_iterator const_iterator;
    
    
        iterator begin() {
          return buf.begin();
        }
    
        iterator end() {
          return buf.begin() + sz;
        }
    
    
        const_iterator begin() const {
          return buf.begin();
        }
    
        const_iterator end() const {
          return buf.begin() + sz;
        }
    };
    with example usage

    Code:
    crf::agglomerative_list<int> al;
    for (int ii = 0; ii < 10; ++ii)
      al.push_back(ii);
    
    std::cout<< "al (" << al.size() << ", " << al.total_size() << "): [";
    for( auto &el: al)
      std::cout<< el << " ";
    std::cout<< "]\n";
    
    al.reset();
    
    std::cout<< "al (" << al.size() << ", " << al.total_size() << "): [";
    for( auto &el: al)
      std::cout<< el << " ";
    std::cout<< "]\n";
    
    for (int ii = 0; ii < 5; ++ii)
      al.push_back(ii);
    
    std::cout<< "al (" << al.size() << ", " << al.total_size() << "): [";
    for( auto &el: al)
      std::cout<< el << " ";
    std::cout<< "]\n";
    
    for (int ii = 0; ii < 10; ++ii)
      al.push_back(ii);
    
    std::cout<< "al (" << al.size() << ", " << al.total_size() << "): [";
    for( auto &el: al)
      std::cout<< el << " ";
    std::cout<< "]\n";
    from which i get the following output

    al (10, 10): [0 1 2 3 4 5 6 7 8 9 ]
    al (0, 10): []
    al (5, 10): [0 1 2 3 4 ]
    al (15, 15): [0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 ]

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    This is fine as long as you are storing things as simple as integers.
    It will create tricky problems when the objects need cleanup (i.e. destructors need to be called.)
    That is why std::vector's clear method calls all the destructors.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,849
    Since implementations of std::vector's clear member function typically do not deallocate memory after destroying the elements (hence the shrink_to_fit member function, though even that is advisory), it sounds like std::vector will suffice for your needs.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Shouldn't this be possible to implement by hand using placement new and manually calling destructors? If you're not going to expose std::vector's methods, I don't see much point in using it for an internal implementation (I think the overhead outweighs the rather simple array manipulations).

    This might also be a really good exercise at implementing a custom container in C++ which is an amazing learning exercise (especially if you make it iterable).

    Edit: Ah, looks like someone already beat me to implementing it XD

  6. #6
    Registered User
    Join Date
    Aug 2016
    Posts
    3
    Quote Originally Posted by manasij7479
    This is fine as long as you are storing things as simple as integers.
    It will create tricky problems when the objects need cleanup (i.e. destructors need to be called.)
    That is why std::vector's clear method calls all the destructors.
    these are sensible things to consider, and ill need to think a bit more
    before i will be convinced that it's safe. i do think it should be however.

    ---

    Quote Originally Posted by laserlight
    Since implementations of std::vector's clear member function typically do not deallocate memory after destroying the elements (hence the shrink_to_fit member function, though even that is advisory), it sounds like std::vector will suffice for your needs.
    very interesting.

    let me go into greater detail since i simplified my example significantly,
    and in reflection probably misrepresented an important feature

    my code will generate arbitrary (but deterministic) graphs whenever
    data is presented to my algorithm. every node in the graph will require
    allocation of six mathematical vectors, and every edge will require
    allocation of two mathematical matrices. the shape of these
    vectors/matrices are always the same. now. say i get my first data
    point and say that it requires me to allocate 10 nodes and 14 edges.
    when i'm done with this data point and acquire a new data point, i
    would prefer to return the previously allocated nodes and edges
    (unchanged) and claim them to be 'uninitialised', so i wouldn't have to
    re-instantiate the (possibly) large set of vectors and matrices again.

    i don't think that std::vector::clear would facilitate what i need
    whenever i do a push_back, though, if i'm mistaken i'm happy to be
    corrected.

    ---

    Quote Originally Posted by MutantJohn View Post
    Shouldn't this be possible to implement by hand using placement new and manually calling destructors?
    absolutely. though i generally prefer not to implement something if
    there is already a good implementation. hence my asking if anyone
    knew of some object class that would do as I need.

    Quote Originally Posted by MutantJohn View Post
    If you're not going to expose std::vector's methods, I don't see much point in using it for an internal implementation (I think the overhead outweighs the rather simple array manipulations).
    agreed. though having contiguous memory of std::vector is convenient
    as allows me to implement the end() iterator method as I did in the
    code I wrote. if it was a linked list instead, for example, i would either
    need to keep track of an end pointer explicitly, or iterate the list every
    time I'm calling end().

    Quote Originally Posted by MutantJohn View Post
    This might also be a really good exercise at implementing a custom container in C++ which is an amazing learning exercise (especially if you make it iterable).
    true. though bear in mind that while i'm new here, i'm not new to C++


    Quote Originally Posted by MutantJohn View Post
    Edit: Ah, looks like someone already beat me to implementing it XD
    oh? can you point me to the implementation?
    Last edited by andcomma; 08-30-2016 at 10:09 AM.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,849
    Quote Originally Posted by andcomma
    when i'm done with this data point and acquire a new data point, i
    would prefer to return the previously allocated nodes and edges
    (unchanged) and claim them to be 'uninitialised', so i wouldn't have to
    re-instantiate the (possibly) large set of vectors and matrices again.

    i don't think that std::vector::clear would facilitate what i need
    whenever i do a push_back, though, if i'm mistaken i'm happy to be
    corrected.
    Perhaps you could experiment with your given standard library implementation by checking capacity after clear? If the capacity does not change, then a subsequent push_back after clear will not cause reallocation until capacity is due to be exceeded.

    The only thing is that because clear will destroy the objects, you will have to instantiate the objects again; what you won't need to do is to allocate space for them, unless you have more objects than previously. However, if you want them to be 'uninitialised', it seems to me that you necessarily will have to instantiate them.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Creating an iterable contiguous container in C++ is almost a relatively trivial task. In that case, your iterator is just a typedef for a pointer. The only difference between yours and the STL's vectors is that you can control the destruction of objects and the lifetime of the memory. I know this is the part where phantom would've probably warned me about object lifetimes and exceptions so I'd say, take care of exceptions or use enable_if semantics to guarantee that your container only works for nothrow constructible types.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Pointers are not iterators. They sometimes work with algorithms, but not always.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,849
    Quote Originally Posted by Elysia
    Pointers are not iterators. They sometimes work with algorithms, but not always.
    I believe that it has always been the case that pointers are random access iterators.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by Elysia View Post
    Pointers are not iterators. They sometimes work with algorithms, but not always.
    Ah, but of course! I'm certainly not attempting to conflate pointers with iterators but for a contiguous allocation, a pointer in that range satisfies RandomAccessIterator so what I was trying to say is that in this instance, the iterator would be a pointer.

    It's funny, I don't even think a language is worth using now if they don't have at least 5 different iterator types :P

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by laserlight View Post
    I believe that it has always been the case that pointers are random access iterators.
    Pointers don't have the type traits that iterators do, so they do not capture the requirements of an iterator that all algorithms can use.
    Conceptually, pointers are random access iterators, but since they don't have the necessary type traits, in practice, they fall somewhat short.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Quote Originally Posted by Elysia View Post
    Pointers don't have the type traits that iterators do, so they do not capture the requirements of an iterator that all algorithms can use.
    Conceptually, pointers are random access iterators, but since they don't have the necessary type traits, in practice, they fall somewhat short.
    I just googled it and according to this, there exists specializations of iterator traits that allow pointers to be used. It's unfortunate that seems like it couldn't be used in this context XD

    Edit:

    Okay, this code works:
    Code:
    #include <iostream>
    #include <iterator>
    #include <cassert>
    
    
    using namespace std;
    
    
    template <typename RandomAccessIterator>
    auto get_distance(
        RandomAccessIterator first,
        RandomAccessIterator last) -> int
    {
        typename std::iterator_traits<RandomAccessIterator>::difference_type n = std::distance(first, last);
        return n;
    }
    
    
    int main()
    {
        int x[3] = { 0, 1, 2 };
        int* first = x;
        int* last = first + 3;
        
        auto const n = get_distance(first, last);   
       
        std::cout << n << std::endl;
        
        return 0;
    }
    So it looks like the STL's provided specializations for iterator traits covers the cases you pointed out, Elysia. That's a good catch though. I certainly would've never thought of that.
    Last edited by MutantJohn; 08-31-2016 at 02:24 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic List Char Array & Double Linked List
    By Roadrunner2015 in forum C Programming
    Replies: 18
    Last Post: 10-20-2013, 01:31 PM
  2. linked list noob - function create new list
    By dukysta in forum C Programming
    Replies: 5
    Last Post: 07-06-2007, 08:16 AM
  3. Left justification using linked list of link list
    By hykyit in forum C Programming
    Replies: 7
    Last Post: 08-29-2005, 10:04 PM
  4. Nested for loop...search & display a list within a list
    By chadsxe in forum C++ Programming
    Replies: 13
    Last Post: 07-20-2005, 01:34 PM
  5. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM

Tags for this Thread