Inserting in a deque (C++ STL)

graemef · 05-08-2007, 11:29 PM

Recently I have been coding in C++ STL. I have a deque where most of the time I want to insert at the end but occasionally I want to insert elements "almost" at the end. So I was looking to use the insert() function and use a reverse iterator. The code will compile with a normal iterator but not with a reverse iterator, is this normal? I thought that the reverse_iterator was just a specialisation of iterator.
I can get the code to work but this approach is not as efficient as I would like, since I know that the data will be added at or towards the end of the list.

This code compiles, but approached the structure from the "wrong" direction...

Code:

      std::deque<StoredLine*>::iterator iter;
      for (iter = markedLines.begin()
          ;iter != markedLines.end()
          ;iter++)
      {
         if ((*iter)->lineNo() == sl->lineNo())
         {
            (*iter)->rep();
            break;
         }
         if ((*iter)->lineNo() > sl->lineNo())
         {
            if (action == '+')
               sl->add();
            else
               sl->sub();
               markedLines.insert(iter,sl);
            break;
         }
      }

This upsets the compiler...

Code:

      std::deque<StoredLine*>::reverse_iterator iter;
      for (iter = markedLines.rbegin()
          ;iter != markedLines.rend()
          ;iter++)
      {
         if ((*iter)->lineNo() == sl->lineNo())
         {
            (*iter)->rep();
            break;
         }
         if ((*iter)->lineNo() > sl->lineNo())
         {
            if (action == '+')
               sl->add();
            else
               sl->sub();
               markedLines.insert(iter,sl);  // <<< compile error
            break;
         }
      }

The compiler states:

access.cpp:62: error: no matching function for call to ‘std::deque<StoredLine*, std::allocator<StoredLine*> >::insert(std::reverse_iterator<std::_Deque_iterator<StoredLine*, StoredLine*&, StoredLine**> >&, StoredLine*&)’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/deque.tcc:90: note: candidates are: typename std::deque<_Tp, _Alloc>::iterator std::deque<_Tp, _Alloc>::insert(typename std::_Deque_base<_Tp, _Alloc>::iterator, const _Tp&) [with _Tp = StoredLine*, _Alloc = std::allocator<StoredLine*>]
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_deque.h:1112: note: void std::deque<_Tp, _Alloc>::insert(typename std::_Deque_base<_Tp, _Alloc>::iterator, size_t, const _Tp&) [with _Tp = StoredLine*, _Alloc = std::allocator<StoredLine*>]
access.cpp:66: error: no match for ‘operator==’ in ‘iter == std::deque<_Tp, _Alloc>::end() [with _Tp = StoredLine*, _Alloc = std::allocator<StoredLine*>]()’

Thanks,

graeme.

nadroj · 05-09-2007, 12:59 AM

i havent done much (what i would call 'actual') programming such as this so i cant give you an example or comments from experiences, but i give you this quote (which you may or may not have seen) as i think its relevant:

Quote:

Each of the container classes is associated with a type of iterator, and each of the STL algorithms uses a certain type of iterator.

http://www.cppreference.com/iterators.html

edit: would calling rend allow you to do this? (since that is actually of type 'iterator', it appears)

dmail · 05-09-2007, 04:33 AM

Hmm I've never tried this?

You could reverse the iterator

Code:

      std::deque<StoredLine*>::iterator iter;
      for (iter = --markedLines.end()
          ;iter != markedLines.begin()-1
          //this maybe better as being checked to end() as end is just an invalid iterator(i seem to recall)
          ;--iter)
      {
         if ((*iter)->lineNo() == sl->lineNo())
         {
            (*iter)->rep();
            break;
         }
//should this be ((*iter)->lineNo() < sl->lineNo())
         if ((*iter)->lineNo() > sl->lineNo())
         {
            if (action == '+')
               sl->add();
            else
               sl->sub();
               markedLines.insert(iter,sl);
            break;
         }
      }

or create a iterator from the reverse iterator

Code:

      std::deque<StoredLine*>::reverse_iterator iter;
      for (iter = markedLines.rbegin()
          ;iter != markedLines.rend()
          ;iter++)
      {
         if ((*iter)->lineNo() == sl->lineNo())
         {
            (*iter)->rep();
            break;
         }
         if ((*iter)->lineNo() > sl->lineNo())
         {
            if (action == '+')
               sl->add();
            else
               sl->sub();
               //&*iter will create a bi direction iterator 
               markedLines.insert(&*iter,sl);
            break;
         }
      }

graemef · 05-09-2007, 05:45 PM

Hi Everyone,

Thanks for the input...

nadroj, thanks for the link. I'm now back to trusty dial-up and so I don't spend as much time searching the net as I would like. I have been to the site you mentioned before but not while investigating this problem. The quote kind of reinforced what I was thinking, it's just that the few texts I have with me are a little skimpy in this area of C++ ( I guess I need to try and get a STL tome but I normally use QT, it's just that for this project I didn't want to use any external libraries)

dmail, I tried many ways of trying to convert a reverse_iterator to an iterator without any joy and I had also tried what you suggested in the first listing but only got seg-faults. However, your suggestion spurred me on to again. The code you gave was slightly different to my attempt but it also seg-faults, but I was able to modify it to get it working. Apparently it doesn't like --markedLines.end(), or even the more explicit, --(markedLines.end()).

However, I was able to extend your idea to get the following:

Code:

std::deque<StoredLine*>::iterator iter;
      for (iter = markedLines.end()
          ;iter != markedLines.begin()
          ;)
      {
         iter--;
         if ((*iter)->lineNo() == sl->lineNo())
         {
            (*iter)->rep();
            break;
         }
         if ((*iter)->lineNo() > sl->lineNo())
         {
            if (action == '+')
               sl->add();
            else
               sl->sub();
               markedLines.insert(iter,sl);
            break;
         }
      }

It works and so I'm now a happy bunny. Thanks everyone.

graeme

graemef · 05-09-2007, 05:52 PM

Having just read a little more in C++ in a Nutshell I have found the following quote:

Quote:

Reverse iterators share a problem with const_iterators, namely that several members, such as insert and erase, do not take an iterator template parameter but require the exact iterator type, as declared in the container class.

So there it is in black and white I need to use the iterator for insertion. Once again thanks to everyone.

dmail · 05-09-2007, 06:00 PM

I don't have time to check at the moment but im pretty sure --end() is valid and if its not then end()- 1 is. Im also pretty sure &*iter is valid.
The following seems to confirm this:

http://www.sgi.com/tech/stl/ReverseIterator.html

Quote:

[3] Note the implications of this remark. The variable rfirst is initialized as reverse_iterator<...> rfirst(V.end());. The value obtained when it is dereferenced, however, is *(V.end() - 1). This is a general property: the fundamental identity of reverse iterators is &*(reverse_iterator(i)) == &*(i - 1). This code sample shows why this identity is important: if [f, l) is a valid range, then it allows [reverse_iterator(l), reverse_iterator(f)) to be a valid range as well. Note that the iterator l is not part of the range, but it is required to be dereferenceable or past-the-end. There is no requirement that any such iterator precedes f.

Anyway glad you go it working.

tuxdev · 05-09-2007, 06:13 PM

There's some red flags in the code
1. Always use preincrement or predecrement unless there is a reason not to
2. Both break statements do nothing
3. The insert statement is not part of the else clause
4. Iterating and mutating a collection simultaneously is potentially problematic

dmail · 05-09-2007, 07:15 PM

Quote:

2. Both break statements do nothing
3. The insert statement is not part of the else clause
4. Iterating and mutating a collection simultaneously is potentially problematic

tuxdev from me viewing this code (and from knowing graemef from this board)I suspect only one line is getting inserted here. The line is checked to see if its a replication if so nothing is done to the queue, or if its found its home it is either an addition or subtraction and then inserted. The break statements do work, they break out of the loop thats why I say one line is getting inserted.

Thought I could be completely wrong

tuxdev · 05-09-2007, 09:28 PM

I'll retract the "both breaks do nothing", cause I forgot what a for loop was for a moment there. Since it's breaking as soon as it does insert, it's relatively safe too.

But that the insert is not part of the else even though the indentation implies it is is still a problem.

I'd recode it like

Code:

std::deque<StoredLine*>::iterator iter = markedLines.end();
std::deque<StoredLine*>::iterator begin = markedLines.begin();
while((*iter)->lineNo() < sl->lineNo() && iter != begin)
{
   --iter;
}
if((*iter)->lineNo() == sl->lineNo())
{
   (*iter)->rep();
}
if((*iter)->lineNo() > sl->lineNo())
{
   if (action == '+')
   {
      sl->add();
   }
   else
   {
      sl->sub();
   }
   markedLines.insert(iter,sl);
}

graemef · 05-10-2007, 01:06 AM

The insert is not meant to be part of the else, as I was playing around with various possibilities the indentation got messed up, which is actually a good argument for those braces! I actually want to remove the if - else by rewriting the add() and sub() methods.

I realise that changing the collection and still using the iterator is a recipe for future heartache. Here I use the iterator only to find out where to insert it in the deque, but I should probably add an comment just for future safeguard.

graemef · 05-10-2007, 01:22 AM

&*iter gave me the following error:

access.cpp:63: error: no matching function for call to ‘std::deque<StoredLine*, std::allocator<StoredLine*> >::insert(StoredLine**, StoredLine*&)’

And all versions that I tried of iter = --(markedLines.end()) or iter = markedLines.end()-1 caused a segfault as soon at the iter was used. By the way markedLines is passed into this method as a reference, not certain if that makes a difference though.

graemef · 05-10-2007, 01:34 AM

Quote:

Originally Posted by tuxdev

1. Always use preincrement or predecrement unless there is a reason not to

Okay I have to ask, why?

tuxdev · 05-10-2007, 09:38 AM

It's an idiomatic optimization. Pre*crement operators don't have to make a copy like Post*crement operators do.

I don't think that markedLines is a reference is the problem.

Anyway, my latest attempt is

Code:

class StoredLineNumberComparator
{
      StoredLine *sl;
   public:
      StoredLineNumberComparator(StoredLine *sl) : sl(sl) {}
      bool operator () (StoredLine *iter)
      {
         return iter->lineNo() < sl->lineNo();
      }
};

   std::deque<StoredLine*>::iterator iter = std::find_if(markedLines.rbegin(), markedLines.rend(), StoredLineNumberComparator(sl)).base();
   if((*iter)->lineNo() == sl->lineNo())
   {
      (*iter)->rep();
   }
   if((*iter)->lineNo() > sl->lineNo())
   {
      if (action == '+')
      {
         sl->add();
      }
      else
      {
         sl->sub();
      }
      markedLines.insert(iter,sl);
   }

base() can be called on a reverse_iterator to get an iterator!

graemef · 05-10-2007, 08:53 PM

I'm not convinced by the optimisation argument, if it is a trivial increment then it will result in trivial assembly which will not result in any additional statements. If it is non trivial then the order probably is important.

Anyway, I had missed the base() method. Just what I needed. So I now have the following.

Code:

         std::deque<StoredLine*>::reverse_iterator iter;
         for (iter = markedLines.rbegin()
            ;iter != markedLines.rend()
            ;iter++)
         {
            if ((*iter)->lineNo() == sl->lineNo())
            {
               (*iter)->action(newAction);
               break;
            }
            if ((*iter)->lineNo() < sl->lineNo())
            {
               sl->action(newAction);
               // use base() to "cast" the reverse_iterator into an iterator
               markedLines.insert(iter.base(),sl);
               break;
            }
         } // end of stepping through the deque on the reverse iterator

So thanks for showing me the base() method, I feel that it makes the code a little cleaner.

tuxdev · 05-11-2007, 08:29 AM

For non-built-in types, it is never trivial and the compiler can't optimize the postincrement into a preincrement for you, even though you really don't care. Since programs have a tendency to use the increment operators a lot, using preincrement instead of postincrement along with other idiomatic optimizations can make a difference.

Directly relevant Guru of the Week:
http://www.gotw.ca/gotw/002.htm
http://www.gotw.ca/gotw/003.htm