24

It's been a while since I programmed in C++, and after coming from python, I feel soooo in a straight jacket, ok I'm not gonna rant.

I have a couple of functions that act as "pipes", accepting a list as input, returning another list as output (based on the input),

this is in concept, but in practice, I'm using std::vector to represent the list, is that acceptable?

further more, I'm not using any pointers, so I'm using std::vector<SomeType> the_list(some_size); as the variable, and returning it directly, i.e. return the_list;

P.S. So far it's all ok, the project size is small and this doesn't seem to affect performance, but I still want to get some input/advice on this, because I feel like I'm writing python in C++.

4
  • How are you accessing the data in the lists? If you don't need random access and contiguous memory and your doing a lot of inserting a removing data a linked list might be better. Commented Feb 5, 2009 at 7:55
  • Note linked lists (e.g. std::list) have a higher memory overhead per element and generally only out-perform vector in the rarest of use cases. Commented Feb 5, 2009 at 8:57
  • I actually need arbitrary access in my current particular case .. but I want to let the question be general, so a linked list sounds like a good suggestion Commented Feb 5, 2009 at 11:23
  • Back from C# now. Many, many a +1 fo the 'straight jacket'! :D Commented Feb 14, 2015 at 19:02

7 Answers 7

20

The only thing I can see is that your forcing a copy of the list you return. It would be more efficient to do something like:

  void DoSomething(const std::vector<SomeType>& in, std::vector<SomeType>& out)
  {
  ...
  // no need to return anything, just modify out
  }

Because you pass in the list you want to return, you avoid the extra copy.

Edit: This is an old reply. If you can use a modern C++ compiler with move semantics, you don't need to worry about this. Of course, this answer still applies if the object you are returning DOES NOT have move semantics.

Sign up to request clarification or add additional context in comments.

5 Comments

This is correct, copying a vector can be bad, but only if you have MASSIVE vectors and you're copying them A LOT.
What is a massive vector? We don't know how large SomeType is or how long the vector is. Using refs and const refs is good practice.
Actually, most if not all half-decent C++ compilers support RVO (return value optimisation) which should take care of the "unnecessary" copy by simply transforming the code to pass in a reference to the returned container. It's one of the few optimisations that is present in almost every compiler.
c++1x will move return values to their destination.returning a vector then just is equivalent to a pointer swap operation ideally. for c++1x, i would then take the parameters by values,and let them be move constructed (using their move constructor) from temporaries,modify them, and move them forward
@Timo Geusch: Still, would you trust it?
14

If you really need a new list, I would simply return it. Return value optimization will take care of no needless copies in most cases, and your code stays very clear.
That being said, taking lists and returning other lists is indeed python programming in C++.

A, for C++, more suitable paradigm would be to create functions that take a range of iterators and alter the underlying collection.

e.g.

void DoSomething(iterator const & from, iterator const & to);

(with iterator possibly being a template, depending on your needs)

Chaining operations is then a matter of calling consecutive methods on begin(), end(). If you don't want to alter the input, you'd make a copy yourself first.

std::vector theOutput(inputVector);

This all comes from the C++ "don't pay for what you don't need" philosophy, you'd only create copies where you actually want to keep the originals.

3 Comments

The thing is, I'm creating the output list inside the function, and its size in relation to the input list is somewhat arbitrary
There's no reason why iterators can't be used to insert / remove elements. But if you're conceptually creating something completely different, why not use e.g. a third std::back_inserter iterator or something similar?
Agreed. For instance, the function template std::remove_copy uses this 3-arg approach to "create" an output whose size is somewhat arbitrary. It's dependency injection: rather than creating a std::vector (or whatever), it's up to the caller to provide an object to receive the output.
5

I'd use the generic approach:

template <typename InIt, typename OutIt>
void DoMagic(InIt first, InIt last, OutIt out)
{
  for(; first != last; ++first) {
    if(IsCorrectIngredient(*first)) {
      *out = DoMoreMagic(*first);
      ++out;
    }
  }
}

Now you can call it

std::vector<MagicIngredients> ingredients;
std::vector<MagicResults> result;

DoMagic(ingredients.begin(), ingredients.end(), std::back_inserter(results));

You can easily change containers used without changing the algorithm used, also it is efficient there's no overhead in returning containers.

1 Comment

Yes. This is definitely the way to do it, especially if you're "piping" things.
1

If you want to be really hardcore, you could use boost::tuple.

tuple<int, int, double> add_multiply_divide(int a, int b) {
  return make_tuple(a+b, a*b, double(a)/double(b));
}

But since it seems all your objects are of a single, non-polymorphic type, then the std::vector is all well and fine. If your types were polymorphic (inherited classes of a base class) then you'd need a vector of pointers, and you'd need to remember to delete all the allocated objects before throwing away your vector.

Comments

1

Using a std::vector is the preferably way in many situations. Its guaranteed to use consecutive memory and is therefor pleasant for the L1 cache.

You should be aware of what happends when your return type is std::vector. What happens under the hood is that the std::vector is recursive copied, so if SomeType's copy constructor is expensive the "return statement" may be a lengthy and time consuming operation.

If you are searching and inserting a lot in your list you could look at std::set to get logarithmic time complexity instead of linear. (std::vectors insert is constant until its capacity is exceeded).

You are saying that you have many "pipe functions"... sounds like an excellent scenario for std::transform.

5 Comments

vector actually does a lazy copy, and just shares the contents of the vector, if you really want to copy it you must explicitly call std::copy. So passing a vector in return isn't heavier than normal.
Are you sure vector does a lazy copy. I wasn't aware of that and a little googling seems to indicate it doesn't. Although I could be entirely wrong. I don't work with the STL much.
Well I'm not 100% sure, because I think its implementation based, however if you allocate a vector from a vector on the stack, and the then deallocate the vector, the stack vector gets blown away.
No, you're just making it up, Robert
Robert, the JTC1/SC22/WG21 - The C++ Standards Committee says something else. Please read the standard before making assumptions about the behaviour of a certain functionality.
0

Another problem with returning a list of objects (opposed to working on one or two lists in place, as BigSandwich pointed out), is if your objects have complex copy constructors, those will called for each element in the container.

If you have 1000 objects each referencing a hunk of memory, and they copy that memory on Object a, b; a=b; that's 1000 memcopys for you, just for returning them contained in a container. If you still want to return a container directly, think about pointers in this case.

Comments

0

It works very simple.

list<int> foo(void)
{
    list<int> l; 
    // do something
    return l;
}

Now receiving data:

list<int> lst=foo();

Is fully optimal because compiler know to optimize constructor of lst well. and would not cause copies.

Other method, more portable:

list<int> lst;
// do anything you want with list
lst.swap(foo());

What happens: foo already optimized so there is no problem to return the value. When you call swap you set value of lst to new, and thus do not copy it. Now old value of lst is "swapped" and destructed.

This is the efficient way to do the job.

1 Comment

Visual Studio 2015 underlines list in red wavy line and says "identifier list is undefined"

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.