C++ STL algorithms to add element in list

Question

I want to know if anyone has a quick way for adding an element to a std::list<T*> if the element is not already in it.

It's a generic function and I can not use loops so something like this

template <class T>
bool Class<T>::addElement(const T* element)
{
    for (list<T*>::iterator it = list_.begin(); it != list_.end(); it++)
    {
        if (element == *it)
            return false;
    }
    list_.push_back(element);
    return true;
}

Is not ok because of the loop. Does anyone have ideas?

Hint: use `std::map`. It may be implemented using link fields. It doesn't insert duplicates. — Thomas Matthews, Mar 12 '16 at 21:40
Was obligated to use list even if map is probably better ! And @PiotrNycz, could you show a little bit more about how to use any_of in that case? Never used the any_of algorithm before.. — wayland700, Mar 12 '16 at 21:50
@PiotrNycz - he just compares pointers, no special comparator needed. And it's not obvious he needs preserve order of inserted elements, there is a chance he don't need list. — user2807083, Mar 12 '16 at 21:51
@PiotrNycz Because `std::find()` is more direct. Writing `std::any_of(list_.begin(), list_.end(), [element](const T* v){return v == element;})` is quite a bit more verbose than just `std::find(list_.begin(), list_.end(), element)` — Barry, Mar 12 '16 at 21:52
`if (std::any_of(list_.begin(), list_.end(), [element](auto v) { return v == element;})) return false; ` instead of for-loop... — PiotrNycz, Mar 12 '16 at 21:52
List is a constraint of the problem in this case, but it's interesting to hear you guys talk about the different STL containers. And ohh, the any_of algorithm would use a loop? Not using loops is also a constraint of the problem — wayland700, Mar 12 '16 at 21:52
You should precise why you can't use a loop. Do you want to avoid explicitely writing a loop, or do you need to avoid a loop-based search from happening, even behind the scene in the implementation, because this would be too slow? — galinette, Mar 12 '16 at 22:03
@Barry - This argument I know - I hoped you have something else. If you do not like lambda - can use `std::any_of(a.begin(), a.end(), std::bind(std::equal_to<>{}, element, _1)` or you can use `boost` any_of... Anyway at first glance using `any_of` looks like overkill - but this is exactly what OP wants to check - if any of elements in the list is equal to element - readability is better with any_of. Possible also any_of can be specialized for `list` so - STD library is free to have better performance here... — PiotrNycz, Mar 12 '16 at 22:04

score 3 · Accepted Answer · edited May 23 '17 at 12:15

3

Why is what you have "not ok"? Looks perfectly fine and readable to me (modulo missing typename).

If you really don't want to use a loop, you can accomplish the same by using the algorithm to does precisely that loop: std::find:

template <class T>
bool Class<T>::addElement(const T* element)
{
    if (std::find(list_.begin(), list_.end(), element) != list_.end()) {
        return false;
    }

    list_.push_back(element);
    return true;
}

edited May 23 '17 at 12:15

Community

1
1

answered Mar 12 '16 at 21:40

Barry

286,269
29
621
977

Find was what I was looking for thank you ! I edited the vec_ name, sorry for the mistake and could not use loop because it's a condition for an exercise. – wayland700 Mar 12 '16 at 21:47

galinette · Answer 2 · 2016-03-12T22:05:28.750

0

If you can add other members to your class, you could add an index such as a std::unordered_set. That container stores a list of unique values, and can be searched for specific values in O(1) complexity, which implies that no full-loop search is done by the implementation for checking if the value already exists. It will stay fast even if you have a lot of values already stored.

With std::list, using library functions such as std::find will avoid explicitely writing a loop, but the implementation will perform the loop and this will be slow when a lot of values are already stored (O(n) complexity)

edited Mar 12 '16 at 22:05

answered Mar 12 '16 at 21:53

galinette

8,896
2
36
87

3

Isn't the set complexity going to be O(log n)? – PYA Mar 12 '16 at 21:55
Additionally, what if the ordering of the elements in the container is significant? – Barry Mar 12 '16 at 21:56
I understand the loop already implemented in the set, but yes I am limited to list for this one. Thank you for the comment ! – wayland700 Mar 12 '16 at 21:56
@Prith : damn, you're right. Why isn't this specified to be O(1) and implemented with a hash??? – galinette Mar 12 '16 at 21:58
@galinette Because it's specified as a tree to maintain ordering. The hashtable is called `std::unordered_set<>`. – Barry Mar 12 '16 at 21:59
I think set uses a BST which may or may not be balanced (not sure). – PYA Mar 12 '16 at 21:59
@Barry : you can combine two containers if insertion ordering is important. There is no standard container which both have insertion ordering and faster than O(n) lookup anyway. – galinette Mar 12 '16 at 22:02
@Barry : my knowledge of stl containers was too old, I remembered an unordered `std::set` and an ordered `std::ordered_set`... – galinette Mar 12 '16 at 22:04

score -1 · Answer 3 · answered Mar 12 '16 at 22:04

You can use intrusive list instead of the std::list. In this case each element in the list keeps its node data, so you can just query that data to find out if the element is already in the list. The disadvantage is that all elements in this list must be able to provide such data, and you can't put in such lists, for example, integer or boolean elements.

If you still need the std::list and/or the elements can be of any type, then the only way of fast queryng whether the element already exists in the list is to use an index. The indexes can be stored in separate std::unordered_set for fast lookups. You can use for indexes either the list's values "as is" or calculate the indexes using any custom function.

C++ STL algorithms to add element in list

3 Answers3