How to replace std::vector by linked list?

Question

I have used std::vector for making my algorithm. I would like to replace the vectors by linked lists.

In order to do so, I was thinking of using the std::list, but I have no idea how to do this, for example I have tried following example for finding a value within a vector/list:

void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2)
{
  if (input_vector[0] >= value) { // too small
    rv1 = 0; rv2 = 0; return;
  }
  int index = (int)input_vector.size() - 1;
  if (input_vector[index] <= value) { // too big
    rv1 = index; rv2 = index; return;
  }
  // somewhere inside
  index = 0;
  while (input_vector[index] <= value) {
    index++;
  }
  rv1 = index - 1; rv2 = index; return;
}

void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2)
{
  if (*input_list.begin() >= value) { // too small
    rv1 = 0; rv2 = 0; return;
  }
  if (*input_list.end() <= value) { // too big
    rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return;
  }
  // somewhere inside
  int index = 0; int temp = *input_list.begin();
  while (temp <= value) {
    temp = *input_list.next(); index++;
  }
  rv1 = index - 1; rv2 = index; return;
}

This seems not to work, as the member function next() is not existing. However I remember that browsing through a linked list is done by going to the beginning, and moving further to the next element until the a certain point is reached. I have seen that there is a way to get this done by using an interator in a for-loop, but I wonder what's wrong with my approach? I was under the impression that a std::list was a standard implementation of a double-directional linked list, or am I wrong and in that case, what std class is the implementation of a linked list (it does not need to be a double-directional linked list)?

the same with like all containers in the stl: You navigate them mostly with iterators. It's a bit getting used to if you come from other languages but it's pretty neat because it's consistent everywhere. Is there any reason btw. why you switch to a list? Vectors are in most cases better. — Hayt, Sep 08 '16 at 07:55
And if to index with integers (not `std::list` though), make it `size_t`, not `int`. — LogicStuff, Sep 08 '16 at 08:10

score 2 · Accepted Answer · answered Sep 08 '16 at 08:02

2

The standard way to iterate through containers is like this:

for(std::list<int>::iterator it = input_list.begin();
    it != input_list.end();
    it++)
{
    ....
}

This also works for vectors,maps,deque,etc. The Iterator concept is consistently implemented throughout the STL so it's best to get used to this concepts.

There are also iterator operations like std::distance and std::advance etc. for the different types of iterators (I suggest you read up on them and their advantages/limitations)

If you have C++ 11 available you can also use this syntax (may not be useful for your problem though.)

for(const auto& value : input_list)
{
   ...
}

This also works throughout the STL container.

answered Sep 08 '16 at 08:02

Hayt

5,210
30
37

An additional question : I had chosen for vectors because it's very easy to get the n-th element of it, but working with lists implies that an iterator is needed, but I don't understand this: it seems that, while working with an iterator `it`, if you do `it++` n times then you will get to the n-th element. Why does `it+n` not work? Isn't that the same? – Dominique Sep 08 '16 at 09:09
1

the ++ operator is overloaded and creates this behavior. You can do what you want with `std::advance` iterators have different behavior depending on what kind of iterators they are. vectors have random-access-iterators that's why you can use indexes. Lists don't, that's why you have to advance it n times. – Hayt Sep 08 '16 at 09:14
2

However, when in doubt, use `++it` instead of `it++`: It might avoid copying the iterator. http://stackoverflow.com/a/24904/5293824 – kubanrob Sep 08 '16 at 09:23
@kubanrob is right here. I left this out intentionally to not confuse too much and make it look like a typical for-loop in most programming languages. but `++it` is usually a better practice. – Hayt Sep 08 '16 at 09:26

score 1 · Answer 2 · answered Sep 08 '16 at 09:06

This should work for vector, list, deque, and set (assuming the contents are sorted).

template <class T>
void find_values_in_container(const T& container, int value, int &rv1, int &rv2)
{
  rv1 = rv2 = 0;  // Initialize
  if (container.empty() || container.front() >= value)
  {
    return;
  }
  for (const auto& v : container)
  {
     rv2++;
     if (v > value)
     {
         break;
     }
     rv1++;
  }
  return;
}

How to replace std::vector by linked list?

2 Answers2