Link to home
Start Free TrialLog in
Avatar of cliff_m
cliff_m

asked on

Move an item in a list (string list) to the end

Hi,

I have a question regarding list manipulation in C++. I have a list of related filenames, like this:

text.f
text.c
text.a
text.b
test.e

I would like to be able to find the filename with the extension .c and move it to the end, like so:

text.f
text.a
text.b
test.e
test.c

I don't care about sorting, I just want the the last item in the list to be the .c file. I know this has got to be easy, I am just not sure whether I should be using swap, sort, splice etc.

Can someone come up with an example? I have started one below:

(btw - looking for a platform independent solution)

#include <list>
#include <string>

std::list<std::string> files;
files.push_back("text.f");
files.push_back("text.c");
files.push_back("text.a");
files.push_back("text.b");
files.push_back("test.e");

for(std::list<std::string>::const_iterator itr=files.begin(); itr != files.end(); itr++)
{
      // determine if this is the file of interest
      
      // what to do here
}

Avatar of efn
efn

When you find the element of interest, save the value, then remove it from the list with the erase function.  Then add it to the end with push_back.  I don't think there is a function that will do both in one operation.

Calling erase will invalidate the iterator, so at that point you need either to break out of the for loop or set itr to a valid iterator so the rest of the loop can run.

--efn
If you don't care about if it's already in the list, then you can use remove and then push_back as efn suggested:
std::list<std::string> files;
files.push_back("text.f");
files.push_back("text.c");
files.push_back("text.a");
files.push_back("text.b");
files.push_back("text.e");

std::string file_to_find = "text.b";

files.remove(file_to_find);
files.push_back(file_to_find);
std::copy(files.begin(), files.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

If you do need to know if it's already in the list, you can use find to find out first, and then erase and push_back:
std::list<std::string> files;
files.push_back("text.f");
files.push_back("text.c");
files.push_back("text.a");
files.push_back("text.b");
files.push_back("text.e");

std::string file_to_find = "text.b";

std::list<std::string>::iterator iter = std::find(files.begin(), files.end(), file_to_find);
if(iter != files.end())
{
  files.erase(iter);
  files.push_back(file_to_find);
}
std::copy(files.begin(), files.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
ASKER CERTIFIED SOLUTION
Avatar of burcarpat
burcarpat

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ooops, forgot to paste the comments:

the idea is simple:  you need to transform the list such that the one value ending with 'c' is gonna be at the end.  explicit erasing and copying is correct and there is nothing wrong with it but what you really need is to use the power of stl.  here, std::partition is ideal for the problem at hand.  basically, it will move all the elements that satisfies the predicate in the 'front' part of the list and everything else that fails will go in the 'back'.  i believe, internally, std::partition probably performs only swaps

if you want to retain the relative order of the other elements, use std::stable_partition instead

-- ba
For what it's worth, here is a sample that's uses std::swap.
[you can never have too much sample code]

#include <list>
#include <string>
#include <algorithm>

bool EndsWithC ( const std::string &sItem )
{
    return (*sItem.rbegin( ) == 'c');
}

int main ( )
{
    std::list<std::string> files;
    files.push_back("text.f");
    files.push_back("text.c");
    files.push_back("text.a");
    files.push_back("text.b");
    files.push_back("test.e");

    std::list<std::string>::reverse_iterator iter =
        std::find_if ( files.rbegin( ), files.rend(  ),  EndsWithC);

    if (files.rbegin( ) != iter)
    {
        std::swap ( *iter, *files.rbegin( ) );  //*** using reverse_iterator avoids --files.end( )
    }
}


std::partition is better suited to the job, as it handles more than one matching instance. One note though, the predicate can does not have to be implemented as a struct with operator() as shown - though it does illustrate some of the less used features of C++.

std::partition(files.rbegin( ), files.rend( ), EndsWithC); //*** using rbegin and rend avoids !EndsWithC


burcarpat, I _really_ like this:
>> std::copy(files.begin(), files.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
actually that snippet, mnashadka wrote first.  i think i first saw it in one of those efficient c++, effective c++, etc. books

also, i personally always use functors instead of functions as functors do have certain advantages ( not for this simple case, though ).  yet, it's a habit and thus i use them even they are not required

-- ba
It's a shame that functors are not more oft used.

Come to think of it, <algorithm> and <functional> are not as widely used as they should be. But that's digressing from the question.
In the spirit of generic programming for the helluvit you could do burcarpat's as follows....

-------8<--------
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <functional>

template <class T> struct end_not_equal_to : public std::binary_function<T,T::value_type,bool> {
      bool operator()(const T& container,const T::value_type& v) const
      {
            return *container.rbegin() != v;
      }
};

int main()
{
      std::list<std::string> files;
      files.push_back("text.f");
      files.push_back("text.c");
      files.push_back("text.a");
      files.push_back("text.b");
      files.push_back("test.e");

      std::partition(files.begin(),files.end(),std::bind2nd(end_not_equal_to<std::string>(),'c'));
      std::copy(files.begin(),files.end(),std::ostream_iterator<std::string>(std::cout,"\n"));
}
-------8<--------
go rstaveley, go rstaveley, go rstaveley
Avatar of cliff_m

ASKER

So many good answers, don't know which one to give the points to. The first two answer are more in line with what I would have come up with on my own and definitly answers my question, but I really liked burcarpat's answer and rstaveley's enhancement. In my code I ended up using rstaveley's version, with appropriate comments indicating it came from an experts-exchange question.

I would really like to get to the level where I could use and create templates. I never really "got it" when templates were presented in class.

Thank you for all of the answers. I think that burcarpat's answer is more what I was hoping for, and that rstaveley polished this up.
Avatar of cliff_m

ASKER

Apparently Visual Studio .NET wants you to use the typename. Here is the new template declaration(?)

template <typename T> struct end_not_equal_to : public
std::binary_function<T, typename T::value_type, bool>
{
      bool operator()(const T& container, const typename T::value_type& v) const
      {
            return *container.rbegin() != v;
      }
};
It compiles OK here with my version of VC7 without the typename qualification (as it does with GCC 3.2), but it seems fair enough that the compiler should benefit from a hint that T::value_type is a type. Are you using a newer version of VC?

--------8<--------
c:\test>cl /EHsc rbegin.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.00.9466 for 80x86
Copyright (C) Microsoft Corporation 1984-2001. All rights reserved.

test.cpp
Microsoft (R) Incremental Linker Version 7.00.9466
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:test.exe
test.obj
--------8<--------
Avatar of cliff_m

ASKER

Apparently so. I did not do anything extra to my setup. Product is named "Microsoft Visual Studio .NET 2003"

C:\Local\Test>cl /EHsc main.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86
Copyright (C) Microsoft Corporation 1984-2002. All rights reserved.

main.cpp
Microsoft (R) Incremental Linker Version 7.10.3077
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:main.exe
Avatar of cliff_m

ASKER

more info from looking up error message:

'name' : dependent name is not a type
The typename keyword is required if a dependent name is to be treated as a type. This is a breaking change in the Visual C++ .NET 2003 compiler, made in order to conform to the ISO C++ standard.
See Summary of Compile-Time Breaking Changes for more information.
For code that works the same in all versions of Visual C++, add typename to the declaration.
The following sample generates C4346:
// C4346.cpp
// compile with: /WX /LD
template<class T>
struct C {
   T::X* x;   // C4346
   // try the following line instead
   // typename T::X* x;
};
The following samples shows other examples where the typename keyword is required:
// C4346b.cpp
// compile with: /LD /W1
template<class T>
const typename T::X& f(typename T::Z* p);   // Required in both places

template<class T, int N>
struct L{};

template<class T>
struct M : public L<typename T::Type, T::Value>
{   // required on type argument, not on non-type argument
   typedef typename T::X   Type;
   Type f();   // OK: "Type" is a type-specifer
   typename T::X g();   // typename required
   operator typename T::Z();   // typename required    
};
and this,
// C4346c.cpp
// compile with: /LD /WX
struct Y {
   typedef int Y_t;
};

template<class T>
struct A {
   typedef Y A_t;
};

template<class T>
struct B {
   typedef /*typename*/ A<T>::A_t B_t;   // C4346 typename needed here
   typedef /*typename*/ B_t::Y_t  B_t2;   // typename also needed here
};
typename is required as per the c++ standard.  many compilers will work without typename and some ( msvc6 ) will actually complain if there is a typename but the standard requires the use of typename to prevent any interpretation problems.  as far as i can remember, msvc 7.0 is ok with not having typename ( i don't have 7.0 installed so i can't check ) but 7.1 correctly requires the keyword

-- ba
That's a very good error message. I must look for an upgrade in my MSDN disks. I've not been doing any MS work for a long time, and I suspect that I'm running an older version.

Off topic (and I apologise for taking this liberty), but can you do me a favour and try out the following test code (previously posted as http:/Programming/Programming_Languages/Cplusplus/Q_20774820.html#9605246) with your version of VC:

--------8<--------
#include <iostream>
#include <memory>

int main()
{
        // Put some nonsense into the free store and free it up
        int *tmp = new int[1024];
        std::memset(tmp,123,sizeof(int)*1024);
        delete []tmp;

        // Allocate and assign the default value to an int in the free store
        // new language feature supported by GCC 3.2, but not 2.98
        // not supported by VC7 or VC6
        int *y = new int();

        // Allocate, but don't assign
        int *z = new int;

        std::cout << "Address of new int() is: " << reinterpret_cast<void*>(y) << '\n';
        std::cout << "Value pointed to is: " << *y << '\n';

        std::cout << "\nAddress of new int is: " << reinterpret_cast<void*>(z) << '\n';
        std::cout << "Value pointed to is: " << *z << '\n';
}
--------8<--------

I was surprised that my version of VC7 wasn't standards compliant, when it failed to initialise the new int() as zero. I was wondering, if that's something which Microsoft has fixed in VC7.1. [It'll take me ages to find those MSDN disks!]
msvc7.0 is only about 91% compliant.  msvc7.1 is pretty good with 99%, i believe
-- ba
Avatar of cliff_m

ASKER

Sure no problem, you have answered or participated in several of my questions, least I can do.

<debug>

Address of new int() is: 06B82498
Value pointed to is: 0

Address of new int is: 06B82790
Value pointed to is: -842150451
Press any key to continue

<release> (don't expect a difference, but just to be sure...)

Address of new int() is: 06B643A0
Value pointed to is: 0

Address of new int is: 06B643B0
Value pointed to is: 112591224
Press any key to continue

Thanks, cliff_m. That test result supports burcarpat's comment too. 9% non-compliance makes VC7.0 seem like a bit of a maverick. I'll definitely upgrade 7.0 -> 7.1.
Just so you know, 7.0 was only 87% compliant, and 7.1 is 98% (according to a Visual Studio ad in C++ Users Journal).
Is there a league table on-line somewhere? I'm curious to know how they come up with the compliance percentages. I would have thought that an altogether different language might score a percentage point or two with regards to being compliant. 13% non-compliance for VC7.0 seems to be very damning... that scoring must have left VC6.0 not many percentage points above QuickBasic ;-)

For what it is worth I've upgraded at last (took me ages!) and I can back up cliff_m's findings above. [It took me most of my time to figure out that the VC7.1 MSDN disk is labelled as "Visual Studio .NET 2003 Enterprise Architect".]

I just double-checked the original code on GCC 3.2 and 2.96 and found that the typename qualification was needed (as well as the include file <iterator> for burcarpat's ostream_iterator). I'm not sure what I was smoking when I reckoned that it was OK on GCC 3.2 without the typename.

If VC7.1 scores 98%, what score does GCC 3.2 get?
actually, i was quoting an old boost regression test.  boost is generally a good indicator ( although they specifically say they are not ;) ).  they do put compiler specific fixes which makes the tests not direct measures of conformance ( hence, the slightly higher number for msvc 7.0 ) but imho the tests still give a good idea.  i just checked their latest test and it shows 84% for msvc 7.0 and 99% for msvc 7.1 ( probably because newer additions don't bother with introducing fixes for 7.0 )

for an official list of missing features from msvc 7.1, see,

    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/vclrfnonstandardbehavior.asp

-- ba
> some of the known places where the Visual C++ implementation of C++ does not agree with the C++ standard

*some* - so much for glasnost, eh?
I couldn't find any links on that.  According to the ad, VS 6.0 was 81% compliant, but of course that was based on their own tests (as was the 98%).  I saw another link that claimed that 6.0 was only about 60% compliant, so I'm sure it really depends upon what they were looking for.  But 81% from their own skewed analysis seems very low to me.
conformance is never really a full-proof thing.  you have to test the thing using yet another software and thus bugs ( intentional or not! ) are still an issue.  typically, you have to stick with your own experience.  my experience has been, msvc6 sucks big time; gcc 3.3, intel 7.1 and msvc 7.1 are good for almost anything you would wanna throw at them.  right now, the industry seems to agree on that gcc and msvc are the most conformant compilers ( and intel is definitely the performance king )

-- ba
> intel is definitely the performance king

Intel 7.1 claims to generate code that runs up to 30% faster than GCC 3.2 (ref http://www.intel.com/software/products/compilers/clin/). Is this another bogus bogus percentage? I think I prefer the burcarpat "sucks big time" .... "good for almost anything you would wanna throw at them" scale for appraisal. Everything from C compilers to coffee machines should be indexed on that scale :-)
;)

intel 7.1 executes one of my really heavy scientific codes ( mostly integer arithmetic ) around 20% faster than gcc 3.3.  when switched to floating-point arithmetic, the difference decreases to 10% but i heard other people getting exact opposite results ( i.e. floats better than ints ).  yet, overall, intel is always faster.  there is a good article on this issue in the latest ddj

-- ba

Of course Intel will always be faster, they designed the hardware and therefore know how to squeeze out every clock cycle.  gcc is designed to run on a lot of different types of hardware, and therefore the optimization is mostly limited to rearranging code (loop unrolling, math inlining, etc.).  They can't take advantage of the way that certain hardware pipelines, for example.

But I have to disagree with burcarpat about the industry saying that msvc 7.1 is one of the most conformant compilers.  No one that I know says that.  They're much closer than they used to be, but Borland has been as good or better for years, and MS has introduced many new non-conformant options and behaviors to allow "Managed C++" to work.  And even a lot of things that they added to make msvc 7.1 compliant are turned off by default (new throwing exceptions, rtti, etc.).  I don't want to bash MS or anything, but there is a lot to be desired from their software.
> "gcc is designed to run on a lot of different types of hardware..."

as far as i know, gcc does pull some intel specific tricks ( intel is just too big to ignore completely ).  it's just, intel is naturally much more proficient with their own platform.  all in all, for scientific coding on intel platforms, intel c++ is #1


> "But I have to disagree with burcarpat about the industry saying that msvc 7.1 is one of the most conformant compilers.  No one that I know says that.  They're much closer than they used to be, but Borland has been as good or better for years..."

bcc is a very good compiler.  unfortunately, it's template support is quite dated now.  i personally stopped using bcc with boost almost a year ago, which is really sad 'cause i have been using borland products since the good old days of turbo pascal.  it's optimizations are not great either ( which is critical to me as i am dealing with scientific code )

msvc 7.1, on the other hand, can really take care of almost everything.  it must be the sutter effect: 7.1 is much better than 7.0 ( which is of course at least 10 times better 6sp5 ).  still, nothing beats intel when it comes to performance and gcc when it's about portability so i don't use msvc 7.1 in my daily work but i compile stuff on it just to see if it can and believe me, it never failed even once to this date


> "MS has introduced many new non-conformant options and behaviors to allow "Managed C++" to work."

bcc supports all the borland additions to support c++b.  there is nothing wrong with adding keywords if you can turn them off


> "I don't want to bash MS or anything, but there is a lot to be desired from their software."

well, i tend to disagree.  visual studio.net is definitely a top notch software.  i use it with intel ( and for gcc, i use dev-cpp ).  now, of course, borland introduced builder x and i will migrate to that as that's the ultimate cross-platform solution ;) but still .net is an incredible ide

...

all in all, i can at least vouch for msvc when it comes to template support.  it does handle stuff that borland can't.  other areas, i wouldn't know 'cause there are some features of the standard that is not commonly used in generic programming but can be quite important for classic oo

p.s.: there is an article in the latest ddj that talks about this issue.  if i remember i correctly, the author admits msvc 7.1 finally caught up with the standard.  he even mentions msvc finding some non-conformant code that escaped gcc

-- ba